如果一个算法的时间复杂度可表示成下面的公式,试计算其复杂度. (2)T(n)=T(」n/2」)+T(「n/2「)+1;
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)单调也就足够了
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
