保存帖子
发现
索引
热门
陶片放逐
关于
关于计算时间复杂度的问题
板块
学术版
楼主
Charisk_FOD
当前回复
5
已保存回复
5
发布时间
2021/9/17 16:05
上次更新
2023/11/4 06:33:45
查看原帖
更新帖子
被骇客
银
狼
阻止的越权访问
保存失败
关于计算时间复杂度的问题
Charisk_FOD
楼主
2021/9/17 16:05
初赛里面，这类型求时间复杂度的题怎么做？
T
(
n
)
=
5
T
(
n
2
)
+
O
(
n
)
T(n)=5T(\frac{n}{2})+O(n)
T
(
n
)
=
5
T
(
2
n
)
+
O
(
n
)
比如这个式子，我就只能求个和，算出来是：
T
(
n
)
=
∑
i
=
1
⌊
log
2
n
⌋
[
n
⋅
(
5
2
)
i
]
T(n)=\sum_{i=1}^{\lfloor \log_2n \rfloor}{[n\cdot(\frac{5}{2})^i]}
T
(
n
)
=
i
=
1
∑
⌊
l
o
g
2
n
⌋
[
n
⋅
(
2
5
)
i
]
=
2
3
n
[
(
5
2
)
⌊
log
2
n
⌋
+
1
−
1
]
=\frac{2}{3}n \left[ (\frac{5}{2})^{\lfloor \log_2n\rfloor+1}-1 \right]
=
3
2
n
[
(
2
5
)
⌊
l
o
g
2
n
⌋
+
1
−
1
]
然后怎么推？感觉应该是趋向某个值了，但是不会算QAQ。
前几天的你谷初赛题的这个题也没做出来。。。
2021/9/17 16:05
加载中...
