我想知道 SHA-2 的空间和时间复杂度是多少。我试着环顾四周,并没有真正得到一个直接的答案。谁能帮我吗?非常感谢!
最佳答案
例如,让我们考虑 SHA-256 。
根据给出的算法描述 here ,主要步骤是:
h1,..,h8
(前 32
素数 8
的平方根的小数部分的前 2..19
位)。 k1,...,k64
(前 32
素数 64
的立方根的小数部分的前 2..311
位)。 由于它们的数量是固定的,因此它们初始化所需的时间复杂度和空间复杂度是恒定的。
512
- 位部分,对于每个 512
- 位部分执行以下操作:3.1 通过使用恒定数量的按位和算术运算,在
1536
次迭代中计算 48
- 位数。可以在两者之间使用几个临时变量。3.2 设置额外的
8
变量 a1,...,a8
等于 h1,...,h8
3.3 通过使用固定数量的变量并执行固定数量的按位和算术运算,在循环中不断更新 a1,...,a8
64
次。3.4 将
a1,...,a8
添加到 h1,...,h8
h1,...,h8
。如上所示,1) 和 2) 的时间和空间复杂度为 O(1)。然后,对于从 4.1) 到 4.4) 的每个独立步骤,它们也是固定的。唯一不恒定的是输入消息的大小,因此 4) 整体的时间复杂度为 O(n)。空间复杂度是 O(1),因为总是使用固定数量的临时变量,并且
1536
- 3) 中使用的位变量可以在每次迭代中重复使用。其他基于 SHA-2 的算法,如 SHA-512 或 SHA-384 。它们的复杂度主要是相同的 3 迭代数,因为它们的复杂度为 3)。
其中,时间复杂度为O(n),空间复杂度为O(1)。
关于algorithm - SHA-2 的空间和时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47557136/