8

重複の可能性:
Big O の平易な英語の説明

私は、自分が書いたアルゴリズムの Big-O 時間と空間の複雑さを計算するのに常に苦労してきました。

アルゴリズムのスペースの複雑さについてもっと勉強するための良いリソースを教えてください。

編集:ここに投稿する前に、チュートリアルを検索しました。残念ながら、すべてのチュートリアルは実行時の複雑さに焦点を当てており、スペースの複雑さについては数行しか書いていません。

4

1 に答える 1

10

飛び込みたい場所にもよりますが、これは良いつま先になるかもしれません。wikiページも高品質で、もう少し詳しく説明されています 。これは高レベルの学部生または大学院生向けの優れたテキストであり、アルゴリズムの実行時間について議論する際にコンピュータ科学者が big-O 表記法をまったく使用しない大きな理由である線形スピードアップ定理に入ります。一言で言えば、ハードウェアに指数関数的な金額を投入することで、速度の向上に常に線形係数を得ることができると言われています。

Big-O 表記の利点は、コスト式の端から「緩い変更」を破棄できることです。これは、入力のサイズが無限大になり、コストの最大項が他の項を支配するという限定的なケースのみを気にするという暗黙の仮定によって正当化されます。

複雑さの分析を実行するには、最初に入力の測定値を選択し、次にどのリソースの消費を測定するかを決定し、特定のサイズの入力で実行したときにアルゴリズムによって消費される量をカウントする必要があります。慣例により、入力サイズの名前はNです。典型的なリソースは、実行された「ステップ」の数またはすべてのコンテナーに格納されたアイテムですが、これらは (一般的な) 例にすぎません。対照的に、比較ベースの並べ替えアルゴリズムは、行われたスワップの数だけに焦点を当てることがよくあります。

通常、入力のサイズは、アルゴリズムの実行にかかる時間や必要なスペースの量を決定する唯一の事実ではありません。たとえば、挿入ソートの実行時間は、すでにソートされた順序と逆ソートされた順序で提示された同じ長さの入力の間で劇的に異なります。これが、最悪のケースと平均的なケースの複雑さ (または最良のケースなど)について話す理由です。たとえば、「起こりうる最悪の事態は何ですか?」と尋ねることで、ソースをステップスルーしてカウントする方法を決定できます。利用方法。

可能な入力の分布に関する知識が必要なため、平均的なケースの複雑さは注意が必要です。最悪の場合の複雑さは、入力分布とは無関係であり、実際には多くの場合、必要なすべてである厳密な上限を提供します。

たとえば、バブル ソートなどのアルゴリズムが項目の配列を入力として受け取る場合、典型的な尺度は配列の長さです。最悪の場合のスワップの回数を数えたいとします。ウィキペディアから取得した疑似コードを次に示します。

procedure bubbleSort( A : list of sortable items )
  repeat
    swapped = false
    for i = 1 to length(A) - 1 inclusive do:
      if A[i-1] > A[i] then
        swap( A[i-1], A[i] )
        swapped = true
      end if
    end for
  until not swapped
end procedure

forこれは基本的に 2 つのループであり、内側のループがもう一方の内側にネストされていることに注意してください。内側のループは から までカウントし1、配列の最大要素が先頭にあるときにlength(A) - 1最大N - 1のスワップを行います。外側のループは、最後のパスでスワッピングが発生している限り、このプロセスを繰り返します。最悪のケースの前のパスを想定すると、以前に最大の未ソート要素がリストの最後に配置され、次に最大の未ソート要素を移動できる距離が 1 つずつ効果的に縮小されます。したがって、連続するパスごとにスワップが 1 つ少なくなり、最終的には

N + (N-1) + (N-2) + ... + 2 + 1 = N * (N + 1) / 2 = 1/2 * N^2 + N/2

Big-O 表記では、これは次のようになります。

O(1/2 * N^2 + N/2) = O(1/2 * N^2) = O(N^2)

ここでは、線形 ( N/2) の項を削除しN -> infます。次に、1/2基本的にハードウェアの詳細であるため、主要な定数係数を削除します。これは人間の動機であることに注意してください。big-O' の賢さは、その定義が、私たちの動機を収容するための厳密なフレームワークを提供することです。そのフレームワークは、主要な定数因子を削除すると言っていることがわかりました。

複雑さの厳密な証明を作成すること自体がスキルであり、定義を知っているだけではあまり役に立ちません。 帰納法による証明は、通常、ループの各パスの前後に事前条件と事後条件を確立する場合に適用できます。私の非公式な議論では、現在の反復について推論するときに、以前の反復を考慮に入れていることに注意してください。これは帰納的思考です。「離散数学」、「帰納法による証明」、「組み合わせ論」、「数え上げ」はすべて、探すのに適したキーワードです。(はい、「数える」こと自体が数学の一分野であり、難しいです。)

式を証明した後、big-O でそれを "還元" するのは別のスキルであり、基本的には微積分 (極限) を少し知っている必要があります。導入は、他の既知のものによって支配されます。

于 2011-09-05T09:56:41.220 に答える