复杂度

2020-02-04 本文已影响0人芒果奶油卷

算法复杂度

在RAM模型中，算法的运行时间与算法需要执行的指令操作次数成正比，记为T(n)

BigO:存在常数c和函数f(n)，使得当n>=c时,T(n)<=f(n),表示为T(n)=O(f(n))

常数项可忽略,低次项可忽略

令a>=1和b>1是常数,f(n)是一个函数,T(n)是定义在非负数整数上的递归式:

T(n)=aT(n/b)+f(n)

其中将n/b解释为n/b的向上取整或者向下取整,那么T(n)有如下渐近界:

1.若对某个常数c>0有f(n)=O( $n^{\log_b(a-c) }$ )，则T(n)=O( $n^{\log_b a }$ )

2.若f(n)=O( $n^{\log_b a }$ ),则T(n)=O( $n^{\log_b a \log_g n}$ ),g随意

3.若对某个常数c>0,有f(n)= $\Omega$ ( $n^{\log_b (a+b) }$ ),且对某个常数c<1和所有足够大的n有af(n/b) 小于 cf(n),则T(n) = O(f(n)).

例如.快排:T(n)=2T(n/2)+O(n),对比主定理T(n)=aT(n/b)+f(n),

则a=2,b=2,f(n)=O(n),符合第二条,则平均复杂度O(nlogn),最坏为O( $n^2$ )

O(1)：常数阶;O(logn):对数阶;指数阶:O( $2^n$ )

O(1)>O(logn)>O(n)>O(nlogn)>O(n^2)>O(2^n)>O(n!)