Linux SHA1 時間複雜度

Linux SHA1 的時間複雜度是線性的嗎？這意味著 2GB 文件的雜湊值是 1GB 文件的兩倍？

是的。除了線性時間之外，沒有任何明智的方法可以實現 SHA-1、SHA2、SHA3 或任何其他加密雜湊函式。由於輸出取決於輸入的每一位，因此不可能有次線性時間，並且線性時間實現很簡單，因此沒有理由讓實現花費超過線性時間。

常見的雜湊函式不可並行化，但即使它們是可並行化的，這也不會改變漸近複雜度：並行化將執行時間乘以一個下限為 1/p 的常數，其中 p 是處理器的數量，它不會改變“大哦”複雜度類 (O(1/p · f(n)) = O(f(n)))。

理論上，可以設計一個不能（或不知道）線上性時間內可計算的雜湊函式，但我不知道這樣的設計會有什麼優勢。

引用自：https://unix.stackexchange.com/questions/635057