在线性时间内计算集合的模式(最常见元素)？

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²).正如作者所指出的,简单地将值排序到列表中首先提供了最佳保证算法,即使在大多数情况下哈希集也是优选的.