77问答网
所有问题
如果一个算法的时间复杂度可表示成下面的公式,试计算其复杂度. (2)T(n)=T(」n/2」)+T(「n/2「)+1;
如题所述
举报该问题
推荐答案 2012-09-11
先考虑简化的情形
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)单调也就足够了
温馨提示:答案为网友推荐,仅供参考
当前网址:
http://77.wendadaohang.com/zd/WNIIppYII.html
相似回答
大家正在搜
相关问题
一个算法的时间复杂度为(n3+n2log2n+14n)/n2...
如果一个算法的时间复杂度可表示为:T(n)=2T([n/2]...
如果一个算法的时间复杂度可表示为:T(n)=T([n/2])...
某算法的计算时间可用T(n)=2T(n/2)+n表示,求时间...
如何计算时间复杂度
时间复杂度怎么计算?
算法导论里面的大师解法是什么 用大师解法计算下面递归表达式的...
怎么估算一个算法的时间复杂度