大O运行时效率的疑点

Question

与O(n log n)相比,O(n)被认为更快吗？如果我有一个执行循环的函数,即O(n)然后在循环O(n log n)之外的合并排序那么运行时间将是O(n log n)我假设？

Answer 1

与O(n log n)相比,O(n)被认为更快吗？

不,不是直接的.Big-O表示法是关于算法的限制因素,它与算法可扩展性而不是速度有关.对于特定的数据集,您可以使用O(1)的例程,该例程比O(n ^ 2)的例程花费更长的时间 - 但前者将更好地扩展.

话虽如此,一般来说,O(n)当然会比O(n log n)更好地扩展,并且可能被认为是"更快"或"更好".

如果我有一个执行循环的函数,即O(n)a O(n log n)那么运行时间是O(n log n)我假设？

目前还不清楚你在这里说的是什么 -

如果你的意思是你有一个包含2个函数的循环,即:

Loop over N elements
    - Call O(n) function
    - Call O(n log n) function

那么整体限制因素将是O(n ^ 2 log n).

(来自评论)

我的意思是合并排序(n log n)在循环之外,所以它仍然是O(n log n)

相反,如果你说你要做的事情如下:

- Call O(n log n) function
- Loop over N elements
     - Process each element using O(1) algorithm

然后总体复杂度仍为O(n log n),因为这是限制因素.这是因为"O(n + n)"仍然是O(n).