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

Question

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

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

我没有学过任何算法相关的类(class)，但我猜它的复杂度在 O(N^2) 左右。这能比 O(N^2) 更及时地完成吗？

Answer 1

离线方法

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

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)) 操作的方法。