复杂度

常量阶O(1)、线性阶O(n)、平方阶O(n²)、多项式阶O(nk)、对数阶O(log n)、指数阶O(2n)

1>log n>n>n²>2n

O(1):
{语句;}

O(n):
for() {语句;}

O(n²):
for() for() {语句;}

for(i = 2; i <= n; ++i)
for(j = 2; j <= i-1; ++j)
{语句;}
i=2 j{} 0次
i=3 j{2} 1次
i=4 j{2,3} 2次
i=5 j{2,4} 3次
…
i=n j{2,n-1} n-2次

0+1+2+3+…+(n-2) = (0+(n-2)) * (n – 2 + 1) / 2 = (n-1)(n-2)/2

如：冒泡法(最坏的情况下的时间复杂度)

O(nk):
for()*k {语句;}

O(log n):

O(2n):

打赏

Post Views: 545