6

Skiena による本「The Algorithm Design Manual」では、セットのモード(最も頻繁な要素) を計算すると、Ω( n log n ) 下限があると言われています (これは私を困惑させます) だけでなく (正しく推測します)モードを計算するための、より高速な最悪ケースのアルゴリズムは存在しません。下限が Ω( n log n ) であることだけに困惑しています。

Google ブックスで本のページを見る

しかし、確かに、これは場合によっては線形時間 (最良の場合) で計算される可能性があります。たとえば、以下のような Java コード (文字列内で最も頻繁に使用される文字を見つける) によって計算されます。「トリック」は、ハッシュテーブルを使用して出現回数をカウントすることです。これは明らかなようです。

では、問題の理解に欠けているものは何ですか?

編集: (ミステリーが解決されました) StriplingWarrior が指摘するように、比較のみが使用される場合、つまりメモリのインデックス作成がない場合、下限が保持されます。

// 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

それで、私は問題の私の理解に何が欠けていますか？

多くの場合、配列またはハッシュテーブルで十分です。「一般的なケース」では、ハッシュテーブルへのアクセスが常に一定時間であるとは限らないため、そうではありません。

一定時間のアクセスを保証するには、各ビンに入る可能性のあるキーの数が一定の定数によって制限されることを保証できる必要があります。文字の場合、これはかなり簡単ですが、セット要素がたとえばdoubleまたはstringsである場合、そうではありません（たとえば、有限数のdouble値があるという純粋に学術的な意味を除いて）。

于 2010-11-12T20:40:00.303 に答える
2

ハッシュ テーブルのルックアップは一定時間償却されます。つまり、一般に、n 個のランダムなキーをルックアップする全体のコストは O(n) です。最悪の場合、それらは線形になる可能性があります。したがって、一般的にはモード計算の次数を O(n) に減らすことができますが、最悪の場合、モード計算の次数を O(n^2) に増やすことになります。

于 2010-11-12T21:04:10.217 に答える