效率/算法与系统规范

我们都在谈论算法的效率,它取决于输入大小 - 基本上.

运行该算法的当前计算机的系统规格如何？在Core 2 Duo 2.6 GHZ,4 GB RAM计算机或P-2,256 MB RAM计算机中运行不同的排序算法有什么不同？

我确信必须有性能差异.但是,我想知道算法和系统规范之间的真正关系......

硬件性能的提高将为您提供算法运行时间的恒定C倍.这意味着如果您的计算机A总体上比计算机B慢2倍.那么您的算法在计算机B上的速度将是原来的两倍.但是当您考虑算法的大输入值时,两倍的速度确实几乎没有差别.

在大O符号中,也就是说,与O(n)= O(c n)= O(n)相比,你会得到像O(n)这样的东西.在计算机A和计算机B上,算法的复杂性和大值的一般运行时间大致相同.

如果您使用大O表示法分析算法的运行时间,那么您将更好地了解算法的实际工作方式.当您将O(logn)算法与O(n ^ 2)进行比较时,计算机性能不会给您带来任何好处.

看一下n的一些数据值:

对于慢速计算机,我将假设每次操作1秒,对于快速计算机,我将假设2次操作.我将比较好的算法与慢速计算机与较差的算法与快速计算机.

对于n = 10:

算法1:O(logn):4次操作慢速计算机:4秒

算法2:O(n ^ 2):100次操作快速计算机:50秒

对于n = 100:

算法1:O(logn):7次操作慢速计算机:7秒

算法2:O(n ^ 2):10,000次操作快速计算机:1.4小时

差异很大

对于n = 1,000:

算法1:O(logn):10次操作慢速计算机:10秒

算法2:O(n ^ 2):1,000,000次操作快速计算机:5.8天

巨大的差异

随着n的增加,差异变得越来越大.

现在,如果您尝试在较快/较慢的计算机上运行这些算法,以获得较大的输入大小.没关系.放下O(logn)会更快.