社区讨论

关于计算时间复杂度的问题

CCharisk_FOD
学术版参与者 6已保存回复 5

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@lobs4zva
此快照首次捕获于
2023/10/30 02:03
2 年前
此快照最后确认于
2023/11/04 06:33
2 年前
查看原帖
初赛里面，这类型求时间复杂度的题怎么做？
T(n)=5T(n2)+O(n)T(n)=5T(\frac{n}{2})+O(n)
比如这个式子，我就只能求个和，算出来是：
T(n)=∑i=1⌊log⁡2n⌋[n⋅(52)i]T(n)=\sum_{i=1}^{\lfloor \log_2n \rfloor}{[n\cdot(\frac{5}{2})^i]} =23n[(52)⌊log⁡2n⌋+1−1]=\frac{2}{3}n \left[ (\frac{5}{2})^{\lfloor \log_2n\rfloor+1}-1 \right]
然后怎么推？感觉应该是趋向某个值了，但是不会算QAQ。
前几天的你谷初赛题的这个题也没做出来。。。

回复

共 5 条回复，欢迎继续交流。

正在加载回复...