complexity-theory - 如何估计复杂的算法设施需求？

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 * ipersec

在蟒蛇中：

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

前任

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

所以计算它需要 1.4 ^ 18 年

因此拥有 100 万个 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 收藏，那么打破钥匙持有人比打破钥匙容易得多。