如何估算复杂的算法设施需求？

Question

我想了解如何使用一些众所周知的启发式方法有效地估计某些复杂算法的硬件要求。
IE。我想快速估计在合理的时间内或以其他方式破解我的 TEA O(2^32) 或 XTEA O(2^115.15) 需要多少计算机能力：

拥有设施电源对于 1000 x 4GHz 四核 CPU，执行给定算法需要多少时间？
我也对 O(log N) 等算法的其他算法复杂度估计感兴趣

。 布阿

Answer 1

好吧，所以我想出了这样的事情：
简化CPU时钟与MIPS相同。

有一定数量的指令，例如。 2^115 和带有 ex 的处理器。 1GHz时钟
即：

i = 2^115.15
时钟=1GHz
ipersec=1/10e+9

秒 = i *

python 中的 ipersec:

def sec(N,cpuSpeedHz):
    instructions=math.pow(2, N)
    return instructions*(1./cpuSpeedHz)

ex

sec(115.15, math.pow(10,9)) / (365*24*60*60)
1.4614952014571389e+18

因此需要 1.4 ^ 18 年来计算它，

因此拥有 1mln 4 核 1Ghz 处理器需要：

sec(115.15, 1000000*4*math.pow(10,9)) / (365*24*60*60)
365373800364.28467

需要 3.6 ^ 11 年（~ 3600 mld 年） )

简化版：

2^115.15 = 2^32 * 2^83.15
时钟 = 2^32 ~ 4Ghz
2^83.15 =

>>> math.pow(2,83.15)/(365*24*60*60)
3.4028086845230746e+17

检查：

2^32 = 10 ^ 9.63295986
>>> sec(115.15, math.pow(2,32))/(365*24*60*60)
3.4028086845230746e+17

Answer 2

选择你喜欢的答案：

1. 超出你的承受能力
2. 对你的机器进行键盘记录会便宜得多
3. 你打算在哪里存储实现 O(2^115) 时间复杂度所需的 2^20 个明文
4. 一大堆

如果有人如果你真的想要你的 pr0n 收藏，那么打破钥匙扣比打破钥匙要容易得多。