首页
D
931492
当前主题：自动模式
查看保存队列
搜索
社区讨论
主定理求助
南
南瓜桐
2024/09/20 20:31
学术版
参与者 3
已保存回复 9
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
当前回复
9 条
当前快照
1 份
快照标识符
@m1apcl3t
此快照首次捕获于
2024/09/20 20:33
去年
此快照最后确认于
2025/11/04 20:49
4 个月前
查看原帖
时光机
更新帖子
复制链接
复制快照链接
复制零楼 Markdown
rt，这篇博客里
https://www.luogu.com.cn/article/w3avh1ku
每项都
n
÷
2
n\div 2
n
÷
2
，总共递归
log
2
n
\log_2 n
lo
g
2
n
层：
T
(
n
)
=
Θ
(
log
n
⋅
(
n
log
n
+
n
log
(
n
2
)
+
n
log
(
n
2
2
)
+
⋯
+
n
log
(
n
2
log
2
n
)
)
)
T(n)=\Theta\left(\log n\cdot(n\log n+n\log(\frac{n}{2})+n\log(\frac{n}{2^2})+\cdots+n\log(\frac{n}{2^{\log_2 n}}))\right)
T
(
n
)
=
Θ
(
lo
g
n
⋅
(
n
lo
g
n
+
n
lo
g
(
2
n
)
+
n
lo
g
(
2
2
n
)
+
⋯
+
n
lo
g
(
2
l
o
g
2
n
n
))
)
即
T
(
n
)
=
Θ
(
n
log
2
n
)
T(n)=\Theta(n\log^2 n)
T
(
n
)
=
Θ
(
n
lo
g
2
n
)
。
这一步不是很懂，
T
(
n
)
=
Θ
(
log
n
⋅
(
n
log
n
+
n
log
(
n
2
)
+
n
log
(
n
2
2
)
+
⋯
+
n
log
(
n
2
log
2
n
)
)
)
T(n)=\Theta\left(\log n\cdot(n\log n+n\log(\frac{n}{2})+n\log(\frac{n}{2^2})+\cdots+n\log(\frac{n}{2^{\log_2 n}}))\right)
T
(
n
)
=
Θ
(
lo
g
n
⋅
(
n
lo
g
n
+
n
lo
g
(
2
n
)
+
n
lo
g
(
2
2
n
)
+
⋯
+
n
lo
g
(
2
l
o
g
2
n
n
))
)
为什么 前面logn是怎么来的，为什么不是
T
(
n
)
=
Θ
(
⋅
(
n
log
n
+
n
log
(
n
2
)
+
n
log
(
n
2
2
)
+
⋯
+
n
log
(
n
2
log
2
n
)
)
)
T(n)=\Theta\left(\cdot(n\log n+n\log(\frac{n}{2})+n\log(\frac{n}{2^2})+\cdots+n\log(\frac{n}{2^{\log_2 n}}))\right)
T
(
n
)
=
Θ
(
⋅
(
n
lo
g
n
+
n
lo
g
(
2
n
)
+
n
lo
g
(
2
2
n
)
+
⋯
+
n
lo
g
(
2
l
o
g
2
n
n
))
)
回复
共 9 条回复，欢迎继续交流。
最新优先
最早优先
搜索
正在加载回复...
相关推荐
https://www.luogu.com.cn/article/w3avh1ku