線形時間でセットのモード（最も頻繁な要素）を計算しますか？

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

  •  09-10-2019
  •  | 
  •  

質問

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

本のページを参照してください Google Books

しかし、確かにこれは、場合によっては線形時間（ベストケース）で計算される可能性があります。これは明らかなようです。

それで、私は問題を理解していることで何が欠けていますか？

編集：（ミステリーが解決されます）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²）になります。著者が指摘しているように、最初に値をリストに分類するだけで最高のものが提供されます 保証されています ほとんどの場合、ハッシュセットが望ましい場合でも、アルゴリズム。

他のヒント

それで、私は問題を理解していることで何が欠けていますか？

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

一定の時間アクセスを保証するには、各ビンで終わる可能性のあるキーの数がある程度の定数によって境界を搭載していることを保証できる必要があります。キャラクターの場合、これはかなり簡単ですが、セット要素がダブルまたは文字列などであれば、それはそうではありません（例えば、有限数の二重値があるという純粋に学術的な意味を除く）。

ハッシュテーブルの検索は、一定の時間を償却します。つまり、一般に、ランダムキーを調べるための全体的なコストはO（n）です。最悪の場合、それらは線形になる可能性があります。したがって、一般的にはモード計算の順序をO（n）に減らすことができますが、最悪の場合は 増加 O（n^2）へのモード計算の順序。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top