jim*_*imo 12 algorithm complexity-theory big-o data-structures
因此,我知道效率取决于解决方案中使用的算法和数据结构.但是,我真的不知道算法的顺序如何比处理器的速度更重要？
Nik*_*nka 17
典型的个人电脑可以做到10^8 calculations per second.
而世界上最快的超级计算机也是如此10^16 calculations per second.
因此,假设您现在在笔记本电脑/台式机上运行了O(n)算法.并且O(n ^ 2)算法同时在世界上最快的超级计算机上运行.如果n = 10 ^ 10,
PC上的运行时间= 10 ^ 10/10 ^ 8 = 100 seconds.
超级计算机上的运行时间= 10 ^ 20/10 ^ 16 = 10000 seconds.
因此,显然笔记本电脑的性能远远超过了超级计算机.并且使用更好的算法实际上要快100倍.
我们寻找更好算法的另一个原因是可扩展性问题.根据摩尔定律,计算能力每18个月翻一番.因此,即使超级计算机今天能够以极快的速度处理大量输入,也可能无法在问题规模增加了许多倍的情况下这样做,而计算能力在未来18个月内只会翻倍.
我们来看一个例子:
您有一个订单为O(n ^ 3)的算法.您正在处理器上运行该算法,该处理器可以在100毫秒内处理n = 10.
如果n变为10000,则该处理器需要1158天.
获得两倍于处理器的处理器只能将其减少到579天.
即使你能够以十倍的速度获得处理器,它仍然需要几个月的时间.
但是用O(n ^ 2)的顺序替换该算法并在原始处理器上运行该算法会将所需时间减少到2.8小时.