我无法提供完整的答案,但这可能是指向正确方向的提示。
基本思路:
- 假设你已经计算出了
n
个数字a_1,...,a_n
的平均值,那么这个平均值为avg=(a_1+...+a_n)/n
。如果我们现在用b
替换a_n
,我们可以重新计算新的平均值,如下:avg'=(a_1+...+a_(n-1)+b)/n
或更简单地说,avg'=((avg*n)-a_n+b)/n
。也就是说,如果我们交换一个元素,我们可以使用原始平均值通过简单快速的操作重新计算平均值,而不需要重新迭代参与平均值的所有元素。
注意:我假设您希望在每一侧有log n
个邻居,即总共有2 log(n)
个邻居。如果您想要总共有log(n)
个邻居,您可以简单地进行调整。此外,由于log n
在大多数情况下不会是自然数,我假设您谈论的是floor(log n)
,但为了简单起见,我将仅写log n
。
我考虑的主要事情是您必须在O(1)内告诉元素x
周围的平均值。因此,我认为您必须以某种方式预先计算并存储此平均值。所以,我会在一个节点中存储以下内容:
请注意,如果您拥有此结构,则update(x,y)
严格在O(log n)内运行:如果您将元素x
更新到高度y
,则必须考虑到此更改受到影响的2log(n)
个邻居的平均值。您可以在O(1)内重新计算每个这些平均值:
假设update(x,y)
影响到一个元素b
,其平均值也需要更新。然后,只需将average(b)
乘以邻居数(如上所述为2log(n)
)。然后,我们减去元素x
的旧y-value
,并添加x
的新(更新的)y
值。此后,我们除以2log n
。这可以确保我们现在具有元素b
的更新平均值。这仅涉及一些计算,因此可以在O(1)内完成。由于我们有2log n
个邻居,所以update
的运行时间是O(2log n)=O(log n)
。
当您插入一个新元素
e
时,您必须更新所有受此新元素
e
影响的元素的平均值。这基本上就像在
update
例程中所做的那样。但是,当
log n
(或精确地说,
floor(log n)
)改变其值时,您必须小心。如果
floor(log n)
保持不变(在大多数情况下会保持不变),则可以执行类似于
update
中描述的类似操作,但是您必须“删除”一个元素的高度,并“添加”新添加元素的高度。在这些“好”的情况下,运行时间再次严格为
O(log n)
。
现在,当
floor(log n)
正在更改(递增1)时,您必须对所有元素执行更新。也就是说,您必须为
n
个元素执行O(1)操作,从而导致运行时间为
O(n)
。但是,
floor(log n)
递增1的情况非常少见(您需要将
n
的值加倍才能将
floor(log n)
递增1-假设我们谈论的是以2为底的
log
,这在计算机科学中并不罕见)。我们将这个时间表示为
c*n
或简单地
cn
。
因此,让我们考虑一系列插入:第一个插入需要更新:
c*1
,第二个插入需要更新:
2*c
。下一次发生昂贵的插入是第四个插入:
4*c
,然后是第八个插入:
8c
,第十六个插入:
16*c
。两个昂贵插入之间的距离每次加倍:
insert # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ..
cost 1c 2c 1 4c 1 1 1 8c 1 1 1 1 1 1 1 16c 1 1 ..
由于不需要进行
remove
操作,因此我们可以在没有任何“特殊情况”的情况下继续分析,并仅考虑插入序列。您会发现大多数插入成本为1,而有些则很昂贵(1、2、4、8、16、32等)。因此,如果我们总共有
m
个插入操作,则我们大约有
log m
个昂贵的插入操作和大约
m-log m
个廉价的插入操作。为简单起见,我们假设只有
m
个廉价的插入操作。
然后,我们可以计算
m
个插入操作的成本:
log m
----
\ i
m*1 + / 2
----
i=0
m*1
统计便宜操作次数,总和统计昂贵操作次数。可以证明整个过程最多为 4m
(实际上您甚至可以轻松地展示更好的估计,但对我们来说这就足够了)。
因此,我们可以看到 m
次插入操作的总成本最多为 4m
。因此,单个插入操作的成本最多为 4m/m=4
,因此是 O(1)
平摊。
所以,还有两件事情:
- 如何存储所有条目?
- 如何在 O(n) 中初始化数据结构?
我建议将所有条目存储在跳表或某些树中,以保证对数搜索操作(否则,插入和更新需要超过 O(log n) 才能找到正确位置)。请注意,数据结构必须可在 O(n) 内构建 - 假设元素按其 x-坐标排序,则这应该不是什么大问题。
要在 O(n) 中初始化数据结构,我建议从索引 log n
的元素开始,并以简单的方式计算其平均值(求和,2log n
个邻居,除以 2 log n
)。
然后将索引移动一个单位并使用 average(index-1)
计算 average(index)
:average(index)=average(index-1)*log(n)-y(index-1-log(n))+y(index+log(n))
。
也就是说,我们采用了与更新类似的方法。这意味着计算平均值的成本为 O(log n + n*1)=O(n)
。因此,我们可以在 O(n) 中计算平均值。
请注意,您必须考虑到一些我没有在此处描述的细节(例如边界情况:索引为 1 的元素两侧都没有 log(n)
个邻居 - 您该如何处理此问题?)。