算法复杂度
在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()，则T(n)=O(
)
2.若f(n)=O(),则T(n)=O(
),g随意
3.若对某个常数c>0,有f(n)=(
),且对某个常数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()
O(1)：常数阶;O(logn):对数阶;指数阶:O()
O(1)>O(logn)>O(n)>O(nlogn)>O(n^2)>O(2^n)>O(n!)
网友评论