为什么O(n log n)大于O(n)? [英] Why O(n log n) is greater than O(n)?

问题描述

我读到 O(n log n)大于 O(n)，我想知道为什么会这样吗?

例如，将 n 设为1，并求解 O(n log n)将是 O(1 log 1) = O(0).同时， O(n)将是 O(1)?

实际上与 O(n log n)>相矛盾；O(n)

解决方案

让我们首先澄清一下当前上下文中的 Big O 表示法.从(

如@ cem 所示，正确地在图像中显示为" big-O 表示所绘制函数的渐近最小上界之一，并且不引用集合 O(f(n())"

特定输入后在图像中可以看到， O(n log n)(绿线)的增长速度快于 O(n)(黄线)的增长速度.这就是为什么(在最坏的情况下) O(n)比 O(n log n)更可取的原因，因为这样可以增加输入大小和增长率前者的增长将比后者慢.

I read that O(n log n) is greater than O(n), I need to know why is it so?

For instance taking n as 1, and solving O(n log n) will be O(1 log 1) = O(0). On the same hand O(n) will be O(1)?

Which actually contradicts O(n log n) > O(n)

解决方案

Let us start by clarifying what is Big O notation in the current context. From (source) one can read:

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. (..) In computer science, big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows.

The following statement is not accurate:

For instance taking n as 1, solving O(n log n) will be O(1 log 1) = O(0). On the same hand O(n) will be O(1)?

One cannot simply perform "O(1 log 1)" since the Big O notation does not represent a function but rather a set of functions with a certain asymptotic upper-bound; as one can read from source:

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

Informally, in computer-science time-complexity and space-complexity theories, one can think of the Big O notation as a categorization of algorithms with a certain worst-case scenario concerning time and space, respectively. For instance, O(n):

An algorithm is said to take linear time/space, or O(n) time/space, if its time/space complexity is O(n). Informally, this means that the running time/space increases at most linearly with the size of the input (source).

and O(n log n) as:

An algorithm is said to run in quasilinear time/space if T(n) = O(n log^k n) for some positive constant k; linearithmic time/space is the case k = 1 (source).

Mathematically speaking the statement

I read that O(n log n) is greater than O(n) (..)

is not accurate, since as mentioned before Big O notation represents a set of functions. Hence, more accurate will be O(n log n) contains O(n). Nonetheless, typically such relaxed phrasing is normally used to quantify (for the worst-case scenario) how a set of algorithms behaves compared with another set of algorithms regarding the increase of their input sizes. To compare two classes of algorithms (e.g., O(n log n) and O(n)) instead of

For instance taking n as 1, solving O(n log n) will be O(1 log 1) = O(0). On the same hand O(n) will be O(1)?

Which actually contradicts O(n log n) > O(n)

you should analyze how both classes of algorithms behaves with the increase of their input size (i.e., n) for the worse-case scenario; analyzing n when it tends to the infinity

As @cem rightly point it out, in the image "big-O denote one of the asymptotically least upper-bounds of the plotted functions, and does not refer to the sets O(f(n))"

As you can see in the image after a certain input, O(n log n) (green line) grows faster than O(n) (yellow line). That is why (for the worst-case) O(n) is more desirable than O(n log n) because one can increase the input size, and the growth rate will increase slower with the former than with the latter.

这篇关于为什么O(n log n)大于O(n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！