Linux SHA1의 시간 복잡도는 선형입니까? 이는 2GB 파일의 해시 길이가 1GB 파일의 두 배라는 것을 의미합니까?
答え1
예. 선형 시간 외에 SHA-1, SHA2, SHA3 또는 기타 암호화 해시 함수를 구현하는 합리적인 방법은 없습니다. 부선형 시간은 입력의 모든 비트에 따라 출력이 달라지기 때문에 불가능하며, 선형 시간 구현은 간단하므로 구현에 선형 시간 이상이 걸릴 이유가 없습니다.
일반적인 해시 함수는 병렬화할 수 없지만 병렬화할 수 있더라도 점근적 복잡성은 변경되지 않습니다. 병렬화는 실행 시간에 1/p로 하한이 지정된 상수를 곱합니다. 여기서 p는 프로세서 수입니다. "큰 오" 복잡도 클래스(O(1/p · f(n)) = O(f(n)))를 변경하지 마십시오.
이론적으로는 선형 시간에 계산할 수 없는(또는 계산할 수 없다고 알려진) 해시 함수를 설계하는 것이 가능하지만 이 설계의 이점은 모르겠습니다.