6

在 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;
}
4

3 回答 3

10

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

但是，如果精心挑选的数字总是会产生哈希冲突，那么您最终会有效地将哈希集变成一个列表，这会使您的算法变成 O(n²)。正如作者所指出的那样，首先将值简单地排序到一个列表中提供了最好的保证算法，即使在大多数情况下哈希集更可取。

于 2010-11-12T20:26:52.720 回答
2

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

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

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

于 2010-11-12T20:40:00.303 回答
2

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

于 2010-11-12T21:04:10.217 回答