‘runtime 2’哈希函数的运行时复杂性是多少？

Question

假设您希望为任意输入的blake2字节计算n哈希函数。我想知道运行时的情况，特别是：

1. 规模的运行时是否与输入长度成线性关系，即blake2的运行时是否可以被估计为O(n)？
2. 考虑到现代处理器(例如在英特尔-i7上)密码操作是多么的优化，landau在这里是明智的吗？

Answer 1

Blake2接受输入(在任何一个变体中)，在固定大小的块中处理它，如果需要的话，将最后一个块填充为零。处理操作是在固定时间内进行的(它需要一定的周期，由于输入大小是固定的，所以大O表示法没有意义)。初始化和最后确定步骤也需要一定的时间。因此，整个操作需要O(n)时间。