关于第284题快乐游戏鸡的疑惑

2017-05-17 22:41:30 By zx2003

vfk的官方题解提供了一种单调队列合并的做法（解法5-2），但给的复杂度式子是O(n+qlogn)，也就是说预处理时间是O(n)。我不太理解。然后我想了一种构造方法：对于n个点的树，根的左儿子是一条长为n/2-1的链，右儿子则递归处理。然后每个点的w值赋成其深度。这样，根据xllend3大爷的代码，每次合并至少是O(轻儿子的单调队列长度之和）。所以，对于这种树，我们有f(n)=f(n/2)+n/2=f(n/2)+O(n),所以f(n)=O(nlogn) 那么，为什么预处理时间是O(n)，我错在哪里？

cnyali_lk

f(n)=f(n/2)+n/2=f(n/4)+n/2+n/4=....=n/2+n/4+n/8+.....=n f(n)=O(n) （听听就好）

2017-05-17 22:46:19
回复

zhouyi

$f(n) = f(\frac n 2) + O(n) = O(n)$

2017-05-18 19:28:10
回复

immortalCO

每个节点的单调队列（应该是单调栈？）长度是 O(最深的深度) 的，因为同一个深度的节点只会在单调栈中保存一个最大的而长链剖分后，每一条长链都只会在顶端被遍历一次（这里等价于 for 一边单调栈，单调栈的大小不超过最深的深度 = 长链长度），而每个点属于且仅属于一条长链，因此每条长链的长度之和是 N，因此总复杂度是 O(N)。 // 并不需要用什么 T(n) = ... 的分析啊。。。

2017-05-22 07:17:28
回复

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

zx2003的博客

博客

关于第284题快乐游戏鸡的疑惑

评论

发表评论