代码之家 › 专栏 › 技术社区 › bua

如何估计复杂算法的设备需求?

genetic-algorithm estimation complexity-theory

0

bua · 技术社区 · 16 年前

我想了解如何使用一些众所周知的启发式方法有效地估计某些复杂算法的硬件需求。
我想尽快估计出多少 计算机电源 有必要在合理的时间内或以其他方式破解我的茶o(2^32)或xtea o(2^115.15):

拥有1000 x 4GHz四核CPU的设备功率,执行给定算法需要多少时间?
我还对其他算法的算法复杂性估计感兴趣,比如O(log n)等。

当做布亚

2 回复 | 直到 16 年前

1

2

bua 16 年前

好吧,我想到了这样的事情: 简化CPU时钟与MIPS相同。

具有例如2^115的指令量和例如1GHz时钟的处理器
这是:

i=2 ^ 115.15 时钟=1GHz IPESEC=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年

因此,拥有1兆4核1GHz处理器需要:

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

这需要3.6^11年(约3600英里/年)

简化版本:

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

2

0

msw 16 年前

选择你喜欢的答案:

如果有人真的想要你的pr0n收藏,打破钥匙持有人比它是钥匙要容易得多。