大(O)机器依赖吗？

Question

我真的很困惑于大(O)表示法。大(O)机器依赖还是机器独立？(从这个意义上说，我们运行算法的计算机)在i3处理器和i7处理器中使用快速排序对1000个数字进行排序是否是相同的？在计算时间复杂度时，我们为什么不考虑机器及其处理器的速度呢？我是这方面的新手。

Answer 1

大O是衡量可伸缩性的尺度，而不是速度。它向你展示了它对时间和内存的影响，例如，当数据量增加一倍时--它是执行量的两倍，还是翻两番？

无论您使用i7还是i3，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秒！

此外，这也清楚地表明复杂性不依赖于处理器。一秒就是一秒。

编辑:另外，您可能需要阅读this question，其中的Big在许多非常高质量的答案中得到了解释。

Answer 2

大(O)表示法是计算一个算法的复杂性的方法，因此它将运行所需的相对时间。对于相同的数据，相同的算法将在更快的处理器上运行得更快，但仍然需要同样数量的操作。它被用来评价不同算法的相对效率，以达到相同的效果。

Answer 3

大O符号在任何方面都不依赖于体系结构，它是一个数学construct.It，它是算法复杂性的一个非常有限的度量，它只给出了性能随数据大小变化的大致上限。