累积频率表具有线性还是优于线性复杂度？ [英] Cumulative frequency table with creation in linear or better than linear complexity?

问题描述

我正在尝试解决算法问题，并且要在时间限制内解决该问题，我需要实现一个累积频率表，该频率表的创建需要线性时间或优于线性时间？我的输入仅是整数；因此，我的频率表关键字仅是整数。下面是我想到的一个简单实现（假定cumulative_freq_table是以下代码中的哈希表。）：

I am trying to solve an algorithmic problem, and to solve it within the time constrains I need to implement a cumulative frequency table whose creation takes a linear or better than linear time? My inputs are integers only; hence, my keys of the frequency table are integers only. A simple implementation that I came up with is follows (assume cumulative_freq_table is a hashmap in the following code.):

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）好吗？

I haven't studied any algorithms related course, but I guess its complexity is around O(N^2). Can this be done in time better than O(N^2)?

推荐答案

离线方法

如果您愿意使用两次通行证，则可以这样做：

OFF-LINE APPROACH

If you are happy to use two passes then you can do this:

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 

这将是线性的。

线性方法的问题在于，它要求在访问之前必须先查看所有数据

THe problem with the linear approach is that it requires all the data to be seen before you can access the cumulative frequency table.

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

There are alternative approaches that allow continual access to the cumulative frequency, but have higher complexity.

例如，看看 Fenwick树，了解使用O（log（ N））每个元素的操作。

For example, have a look at Fenwick Trees for an approach that uses O(log(N)) operations for each element.

这篇关于累积频率表具有线性还是优于线性复杂度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！