48

ハッシュと検索のタイプ​​を含むアルゴリズムの議論で、O（1）の非常に奇妙な使用法に気づきました。多くの場合、言語システムによって提供される辞書タイプを使用するか、配列を使用して使用される辞書またはハッシュ配列タイプを使用します。 -インデックス表記。

基本的に、O（1）は、一定の時間と（通常は）固定された空間によって制限されることを意味します。いくつかのかなり基本的な操作はO（1）ですが、中間言語と特別なVMを使用すると、ここで考えるものが歪む傾向があります（たとえば、ガベージコレクターやその他の動的プロセスをO（1）アクティビティよりもどのように償却するか）。

しかし、レイテンシーの償却やガベージコレクションなどを無視すると、非常に特殊な条件下を除いて、ある種の検索を含む特定の手法がO（1）になる可能性があるという仮定への飛躍がどのように行われるのかまだわかりません。

これは以前にも気づきましたが、Pandincusの質問に、「C＃.NETでO（1）時間にアイテムを取得するために使用する「適切な」コレクション？」という例が表示されました。。

そこで述べたように、保証された境界としてO（1）アクセスを提供するコレクションは、整数のインデックス値を持つ固定境界配列だけです。配列は、O（1）操作を使用してそのインデックスを持つセルを見つけるランダムアクセスメモリへのマッピングによって実装されていると想定されます。

別の種類のインデックス（または整数インデックスを持つスパース配列）の一致するセルの場所を特定するための何らかの検索を伴うコレクションの場合、人生はそれほど簡単ではありません。特に、衝突があり、混雑が発生する可能性がある場合、アクセスは正確にはO（1）ではありません。また、コレクションに柔軟性がある場合は、輻輳が緩和される（たとえば、衝突の発生率が高い、ツリーの不均衡など）基礎となる構造（ツリーやハッシュテーブルなど）を拡張するコストを認識して償却する必要があります。

私はこれらの柔軟で動的な構造をO（1）として話すことを考えたことはありませんでした。それでも、実際にO（1）アクセスを保証するために維持する必要のある条件を特定せずに、O（1）ソリューションとして提供されていると思います（また、その定数は無視できるほど小さいです）。

質問：この準備はすべて、本当に質問のためのものです。O（1）の周りのカジュアルさは何ですか、そしてなぜそれはそれほど盲目的に受け入れられるのですか？O（1）でさえ、ほぼ一定であっても、望ましくないほど大きくなる可能性があることは認識されていますか？それとも、O（1）は、計算の複雑さの概念を非公式な使用に単純に流用しているのでしょうか。困惑しています。

更新：回答とコメントは、私がO（1）を自分で定義することに何気がなかった場所を指摘しており、それを修復しました。私はまだ良い答えを探しています、そしていくつかのケースでは、コメントスレッドのいくつかは彼らの答えよりもかなり面白いです。

4

13 に答える 13

61

問題は、人々が用語に本当にずさんなことです。ここには3つの重要ですが異なるクラスがあります。

O（1）最悪の場合

これは単純です。最悪の場合、すべての操作にかかる時間は一定であり、したがってすべての場合にかかります。配列の要素へのアクセスはO(1)最悪の場合です。

O（1）償却済みワーストケース

償却とは、すべての操作がO(1)最悪の場合ではないことを意味しますが、N個の操作のシーケンスの場合、シーケンスの総コストはO(N)最悪の場合ではありません。つまり、単一の操作のコストを定数で制限することはできませんが、一連の操作の実行時間が線形になるように、「遅い」操作を補うのに十分な「速い」操作が常に存在します。操作の数で。

たとえば、いっぱいになると容量が2倍になる標準の動的配列O(1)は、一部の挿入に時間がかかる場合でも、最後に要素を挿入するために償却時間を必要とします。O(N)常に十分なO(1)挿入があるため、N個のアイテムの挿入には常にO(N)合計時間がかかります。

O（1）平均ケース

これは最もトリッキーです。平均ケースには2つの可能な定義があります。1つは入力が固定されたランダム化アルゴリズム用で、もう1つは入力がランダム化された決定論的アルゴリズム用です。

入力が固定されたランダム化されたアルゴリズムの場合、アルゴリズムを分析し、すべての可能な実行時間の確率分布を決定し、その分布の平均を取ることによって、任意の入力の平均ケース実行時間を計算できます（アルゴリズムに応じて、これはまたは停止問題のために不可能な場合があります）。

他のケースでは、入力全体に確率分布が必要です。たとえば、並べ替えアルゴリズムを測定する場合、そのような確率分布の1つは、すべてN！入力の可能な順列も同様に可能性があります。次に、平均ケース実行時間は、各入力の確率で重み付けされた、すべての可能な入力の平均実行時間です。

この質問の主題は決定論的なハッシュテーブルであるため、平均ケースの2番目の定義に焦点を当てます。さて、入力の確率分布を常に決定できるとは限りません。なぜなら、ほぼすべてをハッシュすることができ、それらのアイテムは、ユーザーが入力したもの、またはファイルシステムからのものである可能性があるためです。したがって、ハッシュテーブルについて話すとき、ほとんどの人は、入力が適切に動作し、ハッシュ関数が適切に動作して、入力のハッシュ値が可能なハッシュ値の範囲全体に本質的にランダムに均一に分散されると想定します。

少し時間を取って、最後のポイントを沈めてみましょうO(1)。ハッシュテーブルの平均的なパフォーマンスは、すべてのハッシュ値が均一に分散されていると仮定した場合に得られます。この仮定に違反した場合（通常はそうではありませんが、実際に発生する可能性があり、実際に発生します）、実行時間はO(1)平均ではなくなります。

アルゴリズムの複雑さによるサービス拒否も参照してください。この論文では、著者は、2つのバージョンのPerlで使用されるデフォルトのハッシュ関数のいくつかの弱点を利用して、ハッシュ衝突を伴う多数の文字列を生成する方法について説明します。この文字列のリストを利用して、一部のWebサーバーにこれらの文字列をフィードすることにより、サービス拒否攻撃を生成し、O(N)Webサーバーが使用するハッシュテーブルで最悪の場合の動作を引き起こしました。

于 2008-12-02T05:09:53.750 に答える
40

私の理解では、O（1）は必ずしも一定ではありません。むしろ、検討中の変数に依存していません。したがって、ハッシュルックアップは、ハッシュ内の要素の数に関してはO（1）と言えますが、ハッシュされるデータの長さやハッシュ内のバケットに対する要素の比率に関してはそうではありません。

混乱のもう1つの要素は、大きなO表記が制限動作を表すことです。したがって、Nの値が小さい場合の関数f（N）は確かに大きな変動を示す可能性がありますが、Nが無限大に近づくときの限界がNに対して一定である場合、それはO（1）であると言うのは正しいでしょう。

于 2008-12-02T03:38:51.017 に答える
19

O(1) は、一定の時間と (通常は) 固定スペースを意味します

明確にするために、これらは 2 つの別個のステートメントです。時間的には O(1) ですが、空間には O(n) などがあります。

O(1) でさえ、ほぼ一定であるにもかかわらず、望ましくないほど大きくなる可能性があることを認識していますか?

O(1) は非現実的なほど巨大になる可能性があり、それでも O(1) です。非常に小さなデータ セットを使用することがわかっている場合、複雑さよりも定数の方が重要であり、適度に小さなデータ セットの場合は 2 つのバランスが重要であることは、しばしば無視されます。O(n!) アルゴリズムは、データセットの定数とサイズが適切なスケールである場合、O(1) よりも優れたパフォーマンスを発揮します。

O() 表記は複雑さの尺度です。アルゴリズムにかかる時間や、特定のアルゴリズムが特定の目的に対してどれだけ「優れている」かを示す純粋な尺度ではありません。

于 2008-12-02T04:03:51.183 に答える
11

あなたが言っていることはわかりますが、ハッシュテーブルでのルックアップはO（1）の複雑さを持っているという主張の根底にあるいくつかの基本的な仮定があると思います。

  • ハッシュ関数は、多数の衝突を回避するように合理的に設計されています。
  • キーのセットは、ほぼランダムに分散されているか、少なくともハッシュ関数のパフォーマンスを低下させるように意図的に設計されていません。

ハッシュテーブルルックアップの最悪の場合の複雑さはO（n）ですが、上記の2つの仮定を考えると、それは非常にありそうにありません。

于 2008-12-02T03:39:56.537 に答える
8

Hashtablesは、O(1) の検索と挿入をサポートするデータ構造です。

ハッシュテーブルには通常、キーと値のペアがあり、キーは関数 (ハッシュ関数)のパラメーターとして使用され、内部データ構造(通常は配列)内の値の場所を決定します。

挿入と検索はハッシュ関数の結果のみに依存し、ハッシュテーブルのサイズや格納された要素の数には依存しないため、ハッシュテーブルには O(1) の挿入と検索があります。

ただし、注意点が 1 つあります。つまり、ハッシュテーブルがますますいっぱいになると、ハッシュ関数がすでに占有されている配列の要素を返すハッシュ衝突が発生します。これにより、別の空の要素を見つけるために衝突の解決が必要になります。

ハッシュ衝突が発生すると、検索または挿入を O(1) 時間で実行できなくなります。ただし、適切な衝突解決アルゴリズムを使用すると、別の適切な空のスポットを見つけようとする回数を減らすことができます。また、ハッシュテーブルのサイズを大きくすると、そもそも衝突の回数を減らすことができます。

したがって、理論的には、要素数が無限の配列と完全なハッシュ関数を備えたハッシュテーブルのみが O(1) パフォーマンスを達成できます。必要な操作。したがって、任意の有限サイズの配列は、ハッシュの衝突により、O(1) 未満になることがあります。

例を見てみましょう。(key, value)ハッシュテーブルを使用して、次のペアを格納しましょう。

  • (Name, Bob)
  • (Occupation, Student)
  • (Location, Earth)

100 要素の配列を使用してハッシュテーブル バックエンドを実装します。

は、( , ) ペアkeyを格納する配列の要素を決定するために使用されます。要素を決定するために、が使用されます。keyvaluehash_function

  • hash_function("Name")18を返します
  • hash_function("Occupation")32を返します
  • hash_function("Location")74を返します。

(key, value)上記の結果から、ペアを配列の要素に割り当てます。

array[18] = ("Name", "Bob")
array[32] = ("Occupation", "Student")
array[74] = ("Location", "Earth")

挿入にはハッシュ関数の使用のみが必要であり、ハッシュテーブルのサイズやその要素に依存しないため、O(1) 時間で実行できます。

同様に、要素の検索にはハッシュ関数が使用されます。

key を調べたい場合は"Name"、 a を実行しhash_function("Name")て、目的の値が存在する配列内の要素を見つけます。

また、検索はハッシュテーブルのサイズや格納されている要素の数に依存しないため、O(1) 操作になります。

すべては順調です。のエントリを追加してみましょう("Pet", "Dog")。ただし、キーの同じハッシュである18hash_function("Pet")が返されるため、問題があります。"Name"

したがって、このハッシュ衝突を解決する必要があります。使用したハッシュ衝突解決関数によって、新しい空の要素が29であることが判明したとします。

array[29] = ("Pet", "Dog")

この挿入でハッシュ衝突があったため、パフォーマンスは完全には O(1) ではありませんでした。

を実行してキー"Pet"を含む要素を見つけようとすると、最初は常に 18 が返されるため、この問題はキーを検索しようとしたときにも発生します。"Pet"hash_function("Pet")

要素 18 を調べると、"Name"ではなくキーが見つかります"Pet"。"Pet"この不一致が見つかったら、実際のキーを含む正しい要素を取得するために衝突を解決する必要があります。ハッシュ衝突の解決は、ハッシュテーブルが O(1) 時間で実行されないようにする追加の操作です。

于 2008-12-02T04:01:10.580 に答える
4

あなたが見た他の議論について話すことはできませんが、O（1）であることが保証されているハッシュアルゴリズムが少なくとも1つあります。

カッコウハッシュは不変条件を維持するため、ハッシュテーブルに連鎖はありません。挿入はO（1）で償却され、取得は常にO（1）です。私はそれの実装を見たことがありません、それは私が大学にいたときに新しく発見されたものです。比較的静的なデータセットの場合、2つのハッシュ関数を計算し、2つのルックアップを実行し、すぐに答えがわかるため、非常に優れたO（1）である必要があります。

念のために言っておきますが、これはハッシュ計算もO（1）であると想定しています。長さKの文字列の場合、ハッシュは最小限O（K）であると主張できます。実際には、Kを非常に簡単にバインドできます。たとえば、K <1000です。K<1000の場合、O（K）〜= O（1）です。

于 2008-12-02T04:49:03.293 に答える
4

Big-Oh表記をどのように理解しているかに関して概念上の誤りがあるかもしれません。つまり、アルゴリズムと入力データセットが与えられた場合、データセットのサイズが無限大になる傾向がある場合、アルゴリズムの実行時間の上限はO関数の値に依存します。

アルゴリズムにO（n）時間がかかると言う場合、アルゴリズムの最悪の場合の実行時間は、入力セットのサイズに直線的に依存することを意味します。

アルゴリズムにO（1）時間がかかる場合、それが意味するのは、関数f（n）の実行時間を計算する関数T（f）が与えられると、T（f）のような自然な正の数kが存在するということだけです。任意の入力nに対して<k。基本的に、アルゴリズムの実行時間の上限はそのサイズに依存せず、固定された有限の制限があることを意味します。

さて、これは制限が小さいことを意味するのではなく、入力セットのサイズに依存しないことを意味します。したがって、データセットのサイズの境界kを人為的に定義すると、その複雑さはO（k）== O（1）になります。

たとえば、リンクリストで値のインスタンスを検索するのはO（n）操作です。しかし、リストに最大8つの要素があると言えば、O（n）はO（8）になり、O（1）になります。

この場合、トライデータ構造を辞書として使用しました（文字のツリー。リーフノードにはキーとして使用される文字列の値が含まれます）。キーが制限されている場合、そのルックアップ時間はO（ 1）（文字フィールドの長さが最大でk文字であると定義した場合、これは多くの場合に合理的な仮定になります）。

ハッシュテーブルの場合、ハッシュ関数が良好（ランダムに分散）であり、衝突を最小限に抑えるために十分にスパースであり、データ構造が十分に密であるときに再ハッシュが実行されると仮定する限り、実際にO（1 ）アクセス時間構造。

結論として、O（1）時間は、多くの点で過大評価される可能性があります。大規模なデータ構造の場合、適切なハッシュ関数の複雑さは些細なことではなく、衝突の量によってO（n）データ構造のように動作する十分なコーナーケースが存在し、再ハッシュは非常にコストがかかる可能性があります。その場合、AVLやBツリーのようなO（log（n））構造が優れた代替手段になる可能性があります。

于 2008-12-02T05:00:08.090 に答える
2

HashTableのルックアップは、テーブル内のアイテムの数に関してO（1）です。これは、リストに追加するアイテムの数に関係なく、単一のアイテムをハッシュするコストはほぼ同じであり、ハッシュを作成するとわかります。あなたはアイテムのアドレスです。

これが関連する理由に答えるために：OPは、O（1）が、多くの状況で明らかに適用できないと考えているのに、なぜそんなにカジュアルに投げられたように見えるのかについて尋ねました。この答えは、O（1）時間が実際にそのような状況で可能であることを説明しています。

于 2008-12-02T03:32:56.770 に答える
2

一般的に、正確さに関係なく、比較的使用されていると思います。たとえば、ハッシュベースのデータ構造は、適切に設計されていて、適切なハッシュがある場合、O（1）（平均）ルックアップです。すべてが単一のバケットにハッシュされる場合、それはO（n）です。一般に、優れたアルゴリズムを使用し、キーが合理的に分散されているため、すべての資格なしでO（1）として説明すると便利です。リストやツリーなどについても同様です。特定の実装を念頭に置いており、一般論を議論するときは、資格なしでそれらについて話す方が簡単です。一方、特定の実装について話し合っている場合は、より正確に説明することをお勧めします。

于 2008-12-02T03:46:11.890 に答える
1

O(1) は、正確には、アルゴリズムの時間計算量が固定値によって制限されていることを意味します。これは、定数であることを意味するのではなく、入力値に関係なく制限されることのみを意味します。厳密に言えば、O(1) 時間アルゴリズムとされている多くのアルゴリズムは、実際には O(1) ではなく、非常にゆっくりと進行するため、すべての実用的な入力値が制限されます。

于 2008-12-02T06:12:55.620 に答える
1

ハッシュテーブルの実装は、実際には「正確に」O(1) を使用しているわけではありません。テストすると、大規模なデータセット全体で特定のキーを見つけるために、平均で約 1.5 回のルックアップが行われることがわかります。

(衝突が発生するという事実のため、衝突すると、別の場所を割り当てる必要があります)

また、実際には、HashMaps は初期サイズの配列によってサポートされます。つまり、平均で 70% の占有率に達すると 2 倍のサイズに「成長」し、比較的適切なアドレス空間が得られます。70% の充満度の後、衝突率はより速くなります。

Big O 理論では、O(1) アルゴリズム、または O(2) アルゴリズムを使用している場合、重要な要素は、入力セットのサイズと、それらの 1 つを挿入/フェッチする手順との関係の程度であると述べています。O(2) は依然として定数時間なので、ほぼ同じことを意味するため、O(1) として概算します。

実際には、O(1) で「完全なハッシュテーブル」を作成する方法は 1 つしかなく、それには次のものが必要です。

  1. グローバルな完全ハッシュ キー ジェネレーター
  2. 無制限のアドレス空間。

(例外ケース: システムで許可されているキーのすべての順列を事前に計算でき、ターゲット バッキング ストア アドレス空間が、許可されているすべてのキーを保持できるサイズに定義されている場合、完全なハッシュを取得できます。 、しかしその「ドメイン限定」の完璧さ）

固定のメモリ割り当てを考えると、データを失うことなく固定量のスペースに無限の量のデータをパックする魔法のような方法があると想定されるため、これを行うことは少なくとももっともらしくありません。これは論理的に不可能です。 .

振り返ってみると、一定時間である O(1.5) を、比較的ナイーブなハッシュ キー ジェネレーターを使用しても限られた量のメモリで取得することは、非常に素晴らしいことだと思います。

補足説明 注意ここでは O(1.5) と O(2) を使用します。これらは実際には big-o には存在しません。これらは、大物を知らない人々がその理論的根拠であると想定しているだけです。

キーを見つけるのに 1.5 ステップ、そのキーを見つけるのに 2 ステップ、またはそのキーを見つけるのに 1 ステップかかる場合でも、ステップ数が 2 を超えることはなく、1 ステップか 2 ステップかは完全にランダムです。 O(1) の Big-O。これは、データセットのサイズにいくつのアイテムを追加しても、<2 ステップを維持するためです。すべてのテーブルで > 500 キーの場合、2 つのステップが必要な場合、これらの 2 つのステップは実際には 2 つの部分を含む 1 つのステップであると想定できます。これはまだ O(1) です。

この仮定を立てることができない場合、Big-O 思考ではありません。なぜなら、すべてを実行するために必要な有限の計算ステップの数を表す数値を使用する必要があり、「1 ステップ」は意味がないからです。Big-O と関連する実行サイクル数の間には直接的な相関関係がないことを頭に入れておいてください。

于 2008-12-02T03:52:11.067 に答える
1

はい、ガベージ コレクションは、ガベージ コレクションの分野で実行されるアルゴリズムの漸近的な複雑さに影響を与えます。コストがないわけではありませんが、相互作用コストは構成的ではないため、経験的方法なしで分析することは非常に困難です。

ガベージ コレクションにかかる時間は、使用されているアルゴリズムによって異なります。通常、最新のガベージ コレクターは、メモリがいっぱいになるとモードを切り替えて、これらのコストを制御します。たとえば、一般的なアプローチは、より多くのスペースを使用する代わりにライブ セットのサイズに比例したコストを支払うため、メモリ プレッシャが低い場合は Cheney スタイルのコピー コレクタを使用し、メモリ プレッシャが発生した場合はマーク アンド スイープ コレクタに切り替えることです。マーキングのライブ セットとスイープのヒープまたはデッド セット全体に比例するコストを支払うにもかかわらず、より大きくなります。カードのマーキングやその他の最適化などを追加する頃には、実用的なガベージ コレクターの最悪の場合のコストは実際にはかなり悪くなる可能性があり、使用パターンによっては余分な対数係数が発生します。

したがって、大きなハッシュ テーブルを割り当てた場合、たとえ O(1) 検索を使用してアクセスしたとしても、ガベージ コレクトされた環境でこれを行うと、ガベージ コレクタが配列全体をトラバースすることがあります。はサイズ O(n) であり、収集中に定期的にそのコストを支払うことになります。

通常、アルゴリズムの複雑さの分析からそれを除外する理由は、ガベージ コレクションが自明ではない方法でアルゴリズムと相互作用するためです。コストがどれほど悪いかは、同じプロセスで他に何をしているかに大きく依存するため、分析は構成的ではありません。

さらに、コピー、コンパクト、マーク アンド スイープの問題以外にも、実装の詳細が結果として生じる複雑さに大きく影響する可能性があります。

  1. ダーティ ビットなどを追跡するインクリメンタル ガベージ コレクタは、これらのより大きな再トラバーサルをほとんどなくすことができます。
  2. これは、GC が実時間に基づいて定期的に機能するか、割り当ての数に比例して実行されるかによって異なります。
  3. マーク アンド スイープ スタイルのアルゴリズムがコンカレントかストップ ザ ワールドか
  4. 新しい割り当てを黒のコンテナーにドロップするまで白のままにする場合、黒としてマークするかどうか。
  5. 言語がポインターの変更を許可するかどうかによって、一部のガベージ コレクターが 1 回のパスで動作する可能性があります。

最後に、アルゴリズムについて議論するとき、私たちはストローマンについて議論しています。漸近線は、環境のすべての変数を完全に組み込むことはありません。データ構造のすべての詳細を設計どおりに実装することはめったにありません。あちらこちらで機能を借りたり、順序付けられていない高速なキー アクセスが必要なためハッシュ テーブルをドロップしたり、パス圧縮を使用したばらばらなセットに対してユニオン検索を使用したり、ランクごとにユニオンを使用してメモリ領域をマージしたりできません。それらをマージするとき、または何を持っているかによって、リージョンのサイズに比例したコストを支払う余裕があります。これらの構造はプリミティブと考えられており、漸近線は「大規模な」構造の全体的なパフォーマンス特性を計画する際に役立ちますが、定数についての知識も重要です。

完全に O(1) の漸近特性を持つハッシュ テーブルを実装できますが、ガベージ コレクションは使用しないでください。ファイルからメモリにマップし、自分で管理します。ただし、関連する定数はおそらく気に入らないでしょう。

于 2008-12-02T14:44:23.763 に答える
0

多くの人が「O（1）」という用語を投げかけるとき、文脈で「小さい」が意味するものは何でも、暗黙のうちに「小さい」定数を念頭に置いていると思います。

このbig-O分析はすべて、コンテキストと常識を持って行う必要があります。使い方によっては、非常に便利なツールになることもあれば、ばかげていることもあります。

于 2008-12-02T03:38:13.373 に答える