logo标签列表

存储数据和计算平均值的数据结构

data-structuresaverage
4
在这个问题中，我们需要一个数据结构来支持保留无限数量的Y轴平行向量。
每个节点包含位置（X轴值）和高度（Y轴值）。我们可以假设在同一位置没有两个向量。
请提供一个有效的数据结构，支持以下操作：
1. init((x1,y1)(x2,y2)(x3,y3)...(xn,yn)) - 数据结构将包含所有n个向量，其中向量#i的位置是xi，向量#i的高度是yi。 我们还知道x1 < x2 < x3 < ... < xn（y未知）- 平均复杂度为O（n）。
2. insert(x,y) - 添加位置为x，高度为y的向量。- 平摊平均复杂度为O（logn）。
3. update(x,y) - 更新第x个向量的高度为y。- 最坏情况下复杂度为O（logn）。
4. average_around(x) - 返回x周围logn个邻居的高度平均值。- 平均复杂度为O（1）。
空间复杂度：O（n）。
插入和更新的复杂度让我考虑使用带有二分查找的树或列表。 - dutt
1
当我看到复杂性要求时，我认为答案是使用哈希表+跳表。 - SyntaxError
我非常确定地说，地球上没有任何数据结构可以存储“无限数量”的任何东西:p。但是说真的，我会选择跳表。 - Drew
@user1168623 出于好奇，您如何在O(1)时间内计算log(n)个邻居的平均值？ - phimuemue
1个回答
2

我无法提供完整的答案，但这可能是指向正确方向的提示。

基本思路:

  • 假设你已经计算出了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周围的平均值。因此，我认为您必须以某种方式预先计算并存储此平均值。所以，我会在一个节点中存储以下内容：

  • x值
  • y值
  • 周围的平均值

请注意，如果您拥有此结构，则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) 个邻居 - 您该如何处理此问题？）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接