Big(O)机器是否依赖？

Question

我对Big(O)符号感到困惑.Big(O)机器是独立的还是机器独立的？(在我们运行算法的计算机中的机器)在i3处理器和i7处理器中使用快速排序对1000个数字进行排序是否相同？在计算时间复杂度时,为什么我们不考虑机器及其处理器速度？我是这个东西的初学者.

Answer 1

Big-O是衡量可扩展性的标准,而不是速度.它显示了当您将数据量加倍时对时间和内存的影响 - 它是执行的两倍还是四倍？

无论您使用i7还是i3,双倍都是双倍的.无论线性算法是快还是慢,double都是double.

这也有许多人忽视的另一个含义.O(n^3)诸如O(n)对于给定的简单算法可以更快的复杂算法n的低于特定限制.例:

loop n times:
    loop n times:
        loop n times:
            sleep 1 second

是O(n^3),因为它有3个嵌套循环.

loop n times:
    sleep 10 seconds

是O(n)的,因为它只有一个循环.因为n = 10第一个程序执行1000秒,而第二个程序只执行100个.所以,O(n)这很好!人们很想说.但是,如果你有n = 2,第一个复杂的程序只在8秒内执行,而第二个,更简单的程序执行20个!即便如此n = 3,第一个在27秒内执行,第二个在30秒内执行.因此,虽然n较低,但复杂的程序可能胜过较简单的程序.只是随着n上升,复杂程序变得更快(如果有意义)比简单程序慢得多.因为n = 1000,简单的代码已经上升到10000秒,但复杂的代码现在是1000000000秒!

此外,这清楚地表明复杂性不依赖于处理器.第二个是第二个.

编辑:此外,您可能想要阅读这个问题,其中Big-O在许多非常高质量的答案中进行了解释.