大 O 增长层次结构？

Question

我试图找出下面列出的这个增长层次结构的位置O(sqrt(n))和适合。这一章太混乱了，我不知道如何解决这个问题。任何建议将不胜感激。O(n2 log n)

O(1)
O(log log n)
O(log n)
O(log2 n)
O(n)
O(n log n)
O(n2)
O(n3)
O(2n)
O(n!)

Answer 1

\n
1. 复杂度(1)
\n
2. O(log(log(n)))
\n
3. O(logn)
\n
4. O(log\xe2\x82\x82 n)
\n
5. O(sqrt(n)) （由于 sqrt(n) = n ^1/2）
\n
6. 在）
\n
7. O(n log n)
\n
8. O(n\xc2\xb2)
\n
9. O(n\xc2\xb2 log n) （n\xc2\xb2 + 任何大于 n\xc2\xb2 的值。log n 小于 n ¹⁺¹）
\n
10. O(n\xc2\xb3)
\n
11. O(2\xe2\x81\xbf)
\n
12. 在！）
\n

\n

Answer 2

首先，第二个，O(n ² *log ₁₀ n)，很容易算出来。如果您注意到，n ²比 log ₁₀ n具有更大的权重，因为它呈指数增长，而 log 将收敛于 x 轴上最大数字的位数。所以这个方程将产生大于 n ²但小于 n ^{3 的值}。

最后，第一个，O(sqrt(n)), log(n) < sqrt(n) for all n > 0. 这是证明。

附加信息

下图从左到右和从上到下绘制了所有 12 个方程。

使用以下代码，我能够绘制所有 12 个函数。

from matplotlib.pyplot import figure,plot,savefig,subplot,tight_layout,title,text
from numpy import linspace,log10,log2,sqrt
from scipy.misc import factorial

def plotEq(loc, lbl, n, eq):
    subplot(4,3,loc)
    plot(n,eq)
    text(60,.025,r'$\mu=100,\ \sigma=15$')
    title(lbl)

n = linspace(2,100,500)
figure()

plotEq(1, 'log10(log10(n))', n, log10(log10(n)))
plotEq(2, '1', n, n**0)
plotEq(3, 'log10(n)', n, log10(n))
plotEq(4, 'log2(n)', n, log2(n))
plotEq(5, 'sqrt(n)', n, sqrt(n)) # Here
plotEq(6, 'n', n, n)
plotEq(7, 'n*log10(n)', n, n*log10(n))
plotEq(8, 'n**2', n, n**2)
plotEq(9, '(n**2)*log10(n)', n, (n**2)*log10(n)) # Here
plotEq(10, 'n**3', n, n**3)
plotEq(11, '2**n', n, 2**n)
plotEq(12, 'n!', n, factorial(n))

tight_layout()
savefig("plot_subplots.png")