algorithm - 创建线性或优于线性复杂度的累积频率表？

Question

我正在尝试解决一个算法问题，并在时间限制内解决它我需要实现一个累积频率表，其创建需要线性或优于线性时间？我的输入只是整数；因此，我的频率表键只是整数。我想出的一个简单实现如下（假设累积频率表是以下代码中的哈希图。）：

read x
for key in range(x, N):
 if key in cumulative_freq_table:
  cumulative_freq_table[key] += 1

我没有学习任何与算法相关的课程，但我猜它的复杂度在 O(N^2) 左右。这可以比O（N ^ 2）更好地及时完成吗？

score 2 · Accepted Answer

离线方法

如果您乐于使用两次通行证，那么您可以这样做：

for each x:
  read x
  freq_table[x] += 1

t = 0
for key in range(0,N):
  t += freq_table[key]
  cumulative_freq_table[key] = t

这将是线性的。

线性方法的问题在于，它需要先查看所有数据，然后才能访问累积频率表。

有一些替代方法允许连续访问累积频率，但具有更高的复杂性。

例如，查看Fenwick Trees，了解对每个元素使用 O(log(N)) 操作的方法。