算法复杂度

    xiaoxiao2021-03-25  114

    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,有

    则有

    利用大师定理可以求解形如上式的时间复杂度

    lgn

    快速幂算法

    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)

    转载请注明原文地址: https://ju.6miu.com/read-17706.html

    最新回复(0)