早教吧作业答案频道 -->数学-->
如果一个算法的时间复杂度可表示成下面的公式,试计算其复杂度.(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)单调也就足够了
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)单调也就足够了
看了 如果一个算法的时间复杂度可表...的网友还看了以下:
小虎计算乘法时,将其中的一个乘数12错看成了21,结果得到的积比正确的积多405.正确的积应该是多 2020-04-27 …
小马虎在计算乘法时,把其中一个乘数19看成了9,结果得到的积,比正确的少了270,正确的积是多少? 2020-04-27 …
三道四年级数学题!1、丁丁做三位数乘以两位数的题目时,把乘数的个位数字2当作7,乘得的结果是209 2020-05-13 …
小虎计算乘法时,将其中一个乘数十二错看成二十一,结果得到的积比正确多四百零五,正确的积应该是多少 2020-05-21 …
小明在计算一道小数乘法时,把其中一个小数的十分位上的3当8去乘了,结果是26.88,正确积是22. 2020-06-07 …
小明做乘法时,把其中一个乘数32看成23,结果得到的积比正确的积少981,正确的答案是多少? 2020-06-11 …
一个学生做两个两位数乘法时,把其中的一个乘数的个位数字9误看成7,得出的成绩是756,正确的成绩是 2020-06-27 …
明明在计算加法时,把其中一个加数268看成286了,结果算出来的答案是504,当然就错了!你能帮助 2020-07-19 …
丁丁在计算一道乘法时,把其中一个因数4.5错看成5.4,乘得的积比正确答案多百分之几 2020-07-19 …
在“伏安法测电阻”的实验中,常用的方法有“电流表内接法”和“电流表外接法”两种.由于电流表和电压表电 2020-12-31 …