如果一个算法的时间复杂度可表示为：T(n)=T([n/2])+1，请问它的复杂度是多少？
展开全部
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)
更多追问追答
追问
这是一个公式吗？
追答
这不就是一步步迭代
本回答被提问者采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
