如何有以下几种等同于O（N）

Question

我读出其中下面是等同于O（N）：

O(N + P), where P < N/2 
O(N + log N) 

有人能在外行人的术语解释它是如何的是，上面的两个例子与O（N）是一样的吗？

Answer 1

我们总是采取更大的情况下加法。

在这两种情况下，N大于另一部分。

在第一种情况下P < N/2 < N

在第二种情况下log N < N

因此，复杂性是在两种情况下O(N)。

Answer 2

设f和g是定义在实数的某个子集上的两个函数。一个写入

F（X）= O（G（X））为x - >无限

当且仅当有一个正的常数M，使得对于所有x的足够大的值，绝对值的f（x）至多是M乘以g（x）的绝对值。即，F（X）= O（G（X））当且仅当存在正的实数M和的实数X0使得

| F（X）| < = M | g（x）|对于所有的x> X0

你的情况1

所以：

f(N) = N + P <= N + N/2 

我们可以设定M = 2那么：

|f(N)| <= 3/2|N| <= 2|N| (N0 could any number) 

所以：

N+p = O(N) 

在你的第二种情况，我们也可以设置M = 2和N0 = 1来满足：

|N + logN| <= 2 |N| for N > 1 

Answer 3

Big O notation通常只提供函数增长率的上限wiki。这两种情况的含义如P < N和logN < N。这样O(N + P) = O(2N) = O(N)，与O(N + log N) = O(2N) = O(N)一样。希望能回答你的问题。

Answer 4

为了便于理解，您可以假设O(n)表示复杂度为n的order，而且O表示法表示上限（或最坏情况下的复杂度）。所以，当我说O(n+p)它代表n + p的顺序。

我们假设在最坏的情况下p = n/2，那么n + n/2的顺序是什么？它仍然是O(n)，也就是线性因为常量确实构成了Big-O符号的一部分。

相似，对于O(n+logn)，因为logn永远不会大于n。所以，整体复杂性是线性的。

Answer 5

总之

如果N是一个函数，而C是一个常数：

O(N+N/2)：

If C=2, then for any N>1 : 
    (C=2)*N > N+N/2, 
    2*N>3*N/2, 
    2> 3/2 (true) 

O(N+logN)：

If C=2, then for any N>2 : 
    (C=2)*N > N+logN, 
    2*N > N+logN, 
    2>(N+logN)/N, 
    2> 1 + logN/N (limit logN/N is 0), 
    2>1+0 (true) 

反例O(N^2) ：

No C exists such that C*N > N^2 : 
    C > N^2/N, 
    C>N (contradiction). 

镗数学部分

我认为问题的根源是，在等于符号O(f(x))=O(N)并不意味着平等！通常如果x = y，那么y = x。不过请考虑O(x)=O(x^2)这是真的，但反过来是错误的：O(x^2) != O(x)！

O(f(x))是功能增长速度有多快的上限。 上限不是一个确切的值。

如果g(x)=x是上限为一些功能f(x)，然后起作用2*g(x)（和一般的任何增长高于g(x)更快）也是一个上限f(x)。

的正式定义为：为功能f(x)通过一些其他的功能g(x)，如果你选择的任何常量C然后，从一些x_0g(x)开始总是大于f(x)的约束。

f(x)=N+N/2与3*N/2=1.5*N相同。如果我们把g(x)=N和我们不断C=2然后2*g(x)=2*N快于1.5*N增长：

如果C=2和x_0=1然后任何n>(x_0=1)2*N > 1.5*N。

同样适用于N +日志（N）：

C*N>N+log(N) 
C>(N+logN)/N 
C>1+log(N)/N 
...take n_0=2 
C>1+1/2 
C>3/2=1.5 

使用C=2：2*N>N+log(N)任何N>(n_0=2)， 例如

2*3>3+log(3), 6>3+1.58=4.68 
... 
2*100>100+log(100), 200>100+6.64 
... 

现在有趣的部分是：为N & N^2没有这种持续存在。例如。 N squared生长速度比N：

C*N > N^2 
C > N^2/N 
C > N 

显然没有单一的恒定存在比可变大。想象一下这样的常量存在于C=C_0。然后从N=C_0+1开始函数N大于常数C，因此这样的常数不存在。

这为什么在计算机科学中有用？

在大多数情况下，计算精确的算法时间或空间没有意义，因为它取决于硬件速度，语言开销，算法实现细节和许多其他因素。

Big O 表示法提供了一种方法来估计哪种算法更好独立于现实世界的并发症。从一些n_0开始，很容易看出O（N）比O（N^2）好，无论在两个函数前面有哪些常数。

另一个好处是在程序只是一眼，并使用Big O性能估计算法复杂问题的能力：

for x in range(N): 
    sub-calc with O(C) 

有O(N)复杂性和

for x in range(N): 
    sub-calc with O(C_0) 
    sub-calc with O(C_1) 

还有因为“乘法的O(N)复杂通过不变的规则“。

for x in range(N): 
    sub-calc with O(N) 

通过“产品规则”具有O(N*N)=O(N^2)的复杂性。

for x in range(N): 
    sub-calc with O(C_0) 
for y in range(N): 
    sub-calc with O(C_1) 

有O(N+N)=O(2*N)=O(N)复杂的 “的定义（只取C=2*C_original）”。

for x in range(N): 
    sub-calc with O(C) 
for x in range(N): 
    sub-calc with O(N) 

具有O(N^2)复杂性，因为“增长最快的术语确定O(f(x))如果f(x)是其他函数的和”（见在数学部分的解释）。

最后的话

还有很多要Big-O比我能写在这里！例如，在一些真实世界的应用程序和算法中，有益的n_0可能如此之大，以至于具有更差复杂度的算法在真实数据上工作得更快。

CPU缓存可能会引入意外的隐藏因素，否则渐近好的算法。

等...