老师我想问一个复杂度的问题，就是我在书上看到的。

来源：5-1 二分查找法（Binary Search）

慕UI4716311

2019-03-27

递推式T(n)=2T(n/2)+7,
T(n)=3T(n/3)+平均时间复杂度为1的一项，
书中给的第一个递推式平均复杂度为logn而第二个是n，我觉得两个复杂度都应该一样，为n。
书是《数据结构与算法经典问题解析》，绪论里的31和37例题

写回答

1回答

liuyubobobo

2019-03-27

已采纳

你是对的，对于这两个式子，都是O(n)的：）

T(n) = T(n/2) + 7，才是O(logn)的。

T(n) = 2T(n/2) + 7，肯定不可能是O(logn)的，是O(n)的：）

继续加油！：）

慕UI4716311

谢谢老师。

2019-03-28

共1条回复

算法与数据结构（C++版）面试/评级的算法复习技能包

课程专为：短时间内应对面试、升职测评等艰巨任务打造

11187 学习 · 1614 问题

相似问题

回答 2

回答 1

回答 2

回答 1

回答 3