如果一个算法的时间复杂度可表示为:T(n)=T([n/2])+1,请问它的复杂度是多少?
2个回答
展开全部
T(n) = T(n/2) + 1
= T(n/2^2) + 2
= T(n/2^3) + 3
= ...
= T(n/2^(log2(n))) + log2(n)
故复杂度是Log2(n)
= T(n/2^2) + 2
= T(n/2^3) + 3
= ...
= T(n/2^(log2(n))) + log2(n)
故复杂度是Log2(n)
更多追问追答
追问
这是一个公式吗?
追答
这不就是一步步迭代
本回答被提问者采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
2011-09-03
展开全部
O(log(n)),算法导论第38页有类似问题
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询