在线性时间计算集合的模式（最常见的元素）？

StackOverflow https://stackoverflow.com/questions/4168622

  •  09-10-2019
  •  | 
  •  

题

在Skiena的《算法设计手册》一书中，计算 模式 （最常见的元素）一组，据说具有ω（n 日志 n）下界（这使我感到困惑），但（我想正确地）也没有为计算模式而存在更快的最坏情况算法。我只是因下限为ω而感到困惑（n 日志 n).

查看书的页面 Google书籍

但是，可以肯定的是，在某些情况下，这可以在线性时间（最佳情况下）进行计算，例如，Java代码如下（找到字符串中最频繁的字符），“技巧”是使用hashtable计数出现。这似乎很明显。

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

编辑：（神秘解决）如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;
}
有帮助吗？

解决方案

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

但是，如果数字被手工挑选以始终产生哈希碰撞，则最终将有效地将哈希设置变成列表，这将使您的算法变成O（n²）。正如作者指出的那样，首先将值分类到列表中 保证 算法，即使在大多数情况下，哈希集将是可取的。

其他提示

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

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

为了确保持续的时间访问，您必须能够确保可能最终在每个垃圾箱中最终的密钥数受到一定的常数界限。对于角色来说，这很容易，但是如果设定元素是双打或字符串，则不会（在纯粹的学术意义上，例如，有限的双重值数量）。

哈希表格查找是摊销的恒定时间，即通常，查找n随机键的总成本为o（n）。在最坏的情况下，它们可以是线性的。因此，尽管通常它们可以将模式计算顺序减少到O（n），但在最坏的情况下，它将 增加 模式计算的顺序为O（n^2）。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top