来自郭航的问题
如果一个算法的时间复杂度可表示成下面的公式,试计算其复杂度.(2)T(n)=T(」n/2」)+T(「n/2「)+1;
如果一个算法的时间复杂度可表示成下面的公式,试计算其复杂度.(2)T(n)=T(」n/2」)+T(「n/2「)+1;
先考虑简化的情形
T(2n)=2T(n)+1=>T(2n)+1=2(T(n)+1)
这样当n=2^k时就转化到等比数列
T(2^k)+1=C*2^k,即T(n)=Cn-1,C是一个正常数
然后用归纳法证明不仅是2的幂,对一般的n上述结论也成立
如果只需要大O记号的话T(n)=O(n)
当然,对于很多算法复杂度分析,没必要如此细致,对n=2^k讨论完之后只要再证明T(n)单调也就足够了
大家都在问
最新问答
海冰含盐量接近淡水，...2020-12-30
三峡游山峰一下子就被...2020-12-30
二元一次方程简单的配...2020-12-30
【偏裨将校是什么意思...2020-12-30
如图秒表的读数为__...2020-12-30
____abigfi...2020-12-30
【知道本金和税后利息...2020-12-30
《一百条裙子》读后感...2020-12-30
利用矩阵解二元一次方...2020-12-30
【英语中的peasa...2020-12-30