Linux SHA1 的时间复杂度是线性的吗？这意味着 2GB 文件的哈希值比 1GB 文件长两倍？
答案1
是的。除了线性时间之外，没有任何明智的方法可以实现 SHA-1、SHA2、SHA3 或任何其他加密哈希函数。不可能有亚线性时间，因为输出取决于输入的每一位，并且线性时间实现很简单，因此实现没有理由花费超过线性时间。
常见的哈希函数不可并行化，但即使可以并行化，也不会改变渐进复杂度：并行化将运行时间乘以一个常数，该常数的下界为 1/p，其中 p 是处理器的数量，不会改变“big oh”复杂度类 (O(1/p · f(n)) = O(f(n)))。
理论上，可以设计一个不能（或不知道）在线性时间内可计算的哈希函数，但我不知道这种设计有任何优势。