在线性时间内计算集合的模式（最频繁的元素）？

Question

在 Skiena 的《算法设计手册》一书中，计算集合的众数（最频繁的元素），据说有一个 Ω(n log n）下界（这让我困惑），而且（我猜是正确的）不存在更快的最坏情况算法来计算模式。我只是对下限 Ω(n log n) 感到困惑。

请参阅该书的页面 Google 图书

但在某些情况下这肯定可以在线性时间内计算（最好的情况），例如通过像下面这样的 Java 代码（查找字符串中最常见的字符），“技巧”是使用哈希表来计算出现次数。这似乎是显而易见的。

那么，我对这个问题的理解缺少什么？

编辑：（谜团已解）正如StriplingWarrior指出的那样，如果仅使用比较，即没有内存索引，则下限成立，另请参阅：http://en.wikipedia.org/wiki/Element_distinctness_problem

// Linear time
char computeMode(String input) {
  // initialize currentMode to first char
  char[] chars = input.toCharArray();
  char currentMode = chars[0];
  int currentModeCount = 0;
  HashMap<Character, Integer> counts = new HashMap<Character, Integer>();
  for(char character : chars) {
    int count = putget(counts, character); // occurences so far
    // test whether character should be the new currentMode
    if(count > currentModeCount) {
      currentMode = character;
      currentModeCount = count; // also save the count
    }
  }
  return currentMode;
}

// Constant time
int putget(HashMap<Character, Integer> map, char character) {
  if(!map.containsKey(character)) {
    // if character not seen before, initialize to zero
    map.put(character, 0);
  }
 // increment
  int newValue = map.get(character) + 1;
  map.put(character, newValue);
  return newValue;
}

Answer 1

作者的逻辑似乎基于以下假设：比较是您唯一可用的操作。使用基于哈希的数据结构可以通过降低在大多数情况下需要进行比较的可能性来解决这个问题，从而基本上可以在恒定时间内完成此操作。

然而，如果这些数字是经过精心挑选的，总是会产生哈希冲突，那么您最终会有效地将哈希集转换为列表，这将使您的算法变为 O(n²)。正如作者指出的，首先简单地将值排序到列表中可以提供最佳的保证算法，尽管在大多数情况下哈希集会更好。

Answer 2

那么，我对这个问题的理解中缺少什么？

在许多特定情况下，数组或哈希表就足够了。在“一般情况”下则不然，因为哈希表访问并不总是恒定时间。

为了保证恒定的时间访问，您必须能够保证每个 bin 中可能最终出现的键的数量受到某个常数的限制。对于字符来说，这相当容易，但是如果集合元素是双精度数或字符串，则情况就不是这样了（除了纯粹的学术意义上，例如存在有限数量的双精度值）。

Answer 3

哈希表查找是摊销常数时间的，即一般来说，查找n个随机键的总成本是O(n)。在最坏的情况下，它们可以是线性的。因此，虽然通常它们可以将模式计算的阶数减少到 O(n)，但在最坏的情况下，它会将模式计算的阶数增加到 O(n^2)。