以线性时间计算一个集合的模式（最频繁的元素）？

在这本书中“的算法设计手册”，由Skiena，计算一组的模式（最常见的元素），据说有一个Ω（ñ日志ñ）下限（这让我为难），但也（正确地我猜）没有更快的最坏情况算法存在计算模式。我只是通过下界是Ω（ñ日志ñ）不解。以线性时间计算一个集合的模式（最频繁的元素）？

查看Google Books

的书页但可以肯定，这可能在某些情况下以线性时间（最好的情况下），例如计算通过下面的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; 
}

来源

2010-11-12 Pimin Konstantin Kefaloukos

似乎没有在勘误列表中提到： http://www.cs.sunysb.edu/~skiena/algorist/book/errata – 2010-11-12 20:08:58

无法读取页面。一些古怪的信息，显然是丹麦人。 – 2010-11-12 20:17:04

将google.dk更改为google.com，即可使用。 – StriplingWarrior 2010-11-12 20:20:49

笔者似乎托起逻辑假设比较是唯一可用的操作。使用基于哈希的数据结构排序通过减少需要在大多数情况下进行比较的可能性到基本可以在恒定时间内完成此操作的程度。

但是，如果数字是钦点总是产生散列冲突，你最终会有效地将您的哈希集合到一个列表，这将使你的算法为O（N²）。正如作者所指出的那样，只是排序值到列表第一提供了最好的保证算法，尽管在大多数情况下，哈希集合将是可取的。

来源

2010-11-12 20:26:52 StriplingWarrior

@Skipperkongen：作者实际上在讨论寻找模式时使用了Big-O符号。他说“计算模式的最坏情况算法没有比O（n log n）算法更快的速度，我们知道这一点，因为测试集合*中唯一性的问题可以表示为Ω（n log n）下限。 – StriplingWarrior 2010-11-12 21:42:24

我接受最好的保证算法是O（n log n）。但是你是否同意元素唯一性具有欧米茄（n log n）下限是不正确的？ – 2010-11-12 21:45:09

元素清晰度的维基页面实际上提到了“代数计算树模型”的限制，它禁止使用元素来索引内存... http://en.wikipedia.org/wiki/Element_distinctness_problem – 2010-11-12 21:51:29

所以，我是什么，我对问题的理解缺失？

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

为了保证恒定的时间访问，您必须能够保证可能在每个bin中结束的键的数量受到某个常量的限制。对于字符来说，这很容易，但是如果集合元素是双倍或字符串，那么它不会是（除了在纯粹的学术意义上，例如存在有限数量的双值）。

来源

2010-11-12 20:40:00 mokus

哈希表查找是分摊不变的时间，即一般来说，查找n个随机密钥的总成本是O（n）。在最坏的情况下，它们可以是线性的。因此，尽管一般情况下它们可以将模式计算的顺序降低到O（n），但在最坏的情况下，它会将模式计算的顺序增加到O（n^2）增加。

来源

2010-11-12 21:04:10 MSN

以线性时间计算一个集合的模式（最频繁的元素）？

回答

相关问题