以線性時間計算一個集合的模式（最頻繁的元素）？

在這本書中「的算法設計手冊」，由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

以線性時間計算一個集合的模式（最頻繁的元素）？

回答

相關問題