常量阶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):