O(1)<O(lgn)<O(n)<O(nlgn)<O(n^2)<O(n^3)<O(2^n)
在1~5s内可以执行的变量大小
lgnnnlgnn^2n^32^n>10^910^910^810^410^330 利用大师定理(Master theorem)求解算法复杂度
如果对于常数a>0,b>1,d>=0,有
则有
利用大师定理可以求解形如上式的时间复杂度
function power(x,n) if n=1 then return x p=power(x,n/2); p=p*p; if n is odd then p=p*x return p endT(n)=T(n/2)
a=1,b=2,d=0=logb(a)=0
T(n)=O((n^d)*logn)=O(lgn)
二分法
binarysearch(a,low,high,x) if low>high then return -1 mid=(low+high)/2; if x=a[mid] then return mid if else x<a[mid] then binarysearch(a,low,mid-1,x) else binarysearch(a,mid+1,high,x) end if end
T(n)=T(n/2)
a=1,b=2,d=0=logb(a)=0
T(n)=O((n^d)*logn)=O(lgn)
指数级复杂度
Fibonacci数列递归算法复杂度
function Fib(n) if n<=1 then return n else return Fib(n-1)+Fib(n-2) end T(n)=T(n-1)+T(n-2);T(n)>O(2^(n/2))
T(n)>2*T(n-2)>2*2*T(n-4)...>2*2*2...T(0)=2^(n/2)