Big O、どのように計算/近似しますか?

https://stackoverflow.com/questions/3255

08-06-2019
|

質問

CS の学位を持っているほとんどの人は、確かに何を知っているかでしょう。ビッグオーの略です。これは、アルゴリズムが実際にどの程度 (非) 効率的であるかを測定するのに役立ちます。あなたが解決しようとしている問題はどのカテゴリに分類されますかその少しの余分なパフォーマンスを絞り出すことがまだ可能かどうかを判断できます。¹

でも気になる、どうやって あなた アルゴリズムの複雑さを計算または概算しますか?

¹ _{でも、よく言われるように、やりすぎないように、時期尚早の最適化が諸悪の根源, 正当な理由のない最適化もその名前に値するはずです。}

解決

ここでは簡単な言葉で説明するよう最善を尽くしますが、生徒がこのトピックを最終的に理解するまでに 2 ～ 3 か月かかることに注意してください。詳細については、第 2 章を参照してください。 Java のデータ構造とアルゴリズム本。

ありません機械的手順 BigOh を入手するために使用できます。

「料理本」として、ビッグオーコードの一部から、あるサイズの入力が与えられたときに実行される計算ステップの数をカウントする数式を作成していることをまず認識する必要があります。

目的は単純です。コードを実行することなく、理論的な観点からアルゴリズムを比較できます。ステップ数が少ないほど、アルゴリズムは高速になります。

たとえば、次のコードがあるとします。

int sum(int* data, int N) {
    int result = 0;               // 1

    for (int i = 0; i < N; i++) { // 2
        result += data[i];        // 3
    }

    return result;                // 4
}

この関数は配列のすべての要素の合計を返します。その要素を数える式を作成したいと考えています。計算の複雑さその関数の:

Number_Of_Steps = f(N)

それで、私たちは持っています f(N), 、計算ステップ数をカウントする関数。関数の入力は、処理する構造体のサイズです。これは、この関数が次のように呼び出されることを意味します。

Number_Of_Steps = f(data.length)

パラメータ N かかります data.length 価値。ここで、関数の実際の定義が必要になります。 f(). 。これはソースコードから行われ、対象となる各行には 1 から 4 の番号が付けられます。

BigOh を計算するには多くの方法があります。この時点から、入力データのサイズに依存しないすべての文は定数を取ると仮定します。 C 計算ステップの数。

関数の個々のステップ数を追加します。ローカル変数宣言も return ステートメントも、関数のサイズには依存しません。 data 配列。

つまり、行 1 と行 4 はそれぞれ C 量のステップを実行し、関数は次のようになります。

f(N) = C + ??? + C

次の部分は、の値を定義することです。 for 声明。計算ステップの数を数えていることに注意してください。つまり、 for ステートメントが実行される N 回。それは追加するのと同じです C, N 回:

f(N) = C + (C + C + ... + C) + C = C + N * C + C

身体の回数を数える機械的なルールはありません。 for 実行されると、コードが何を行うかを調べてカウントする必要があります。計算を簡略化するために、変数の初期化、条件、および増分の部分を無視しています。 for 声明。

実際の BigOh を取得するには、漸近分析機能の。これは大まかに次のように行われます。

すべての定数を取り除きます C.
から f() を入手する多項式その中で standard form.
多項式の項を分割し、成長率で並べ替えます。
大きくなったものは取っておく N アプローチ infinity.

私たちの f() 次の 2 つの用語があります。

f(N) = 2 * C * N ^ 0 + 1 * C * N ^ 1

全てを奪い取る C 定数と冗長部分:

f(N) = 1 + N ^ 1

後期は大きくなる時期なので f() 無限に近づく（考えてみる）限界) これは BigOh の引数であり、 sum() 関数の BigOh は次のとおりです。

O(N)

いくつかの難しい問題を解決するには、いくつかのトリックがあります。使用合計あなたができる時はいつでも。

たとえば、このコードは合計を使用して簡単に解決できます。

for (i = 0; i < 2*n; i += 2) {  // 1
    for (j=n; j > i; j--) {     // 2
        foo();                  // 3
    }
}

最初に尋ねる必要があるのは、実行順序です。 foo(). 。いつものことである一方で、 O(1), 、それについては教授に尋ねる必要があります。 O(1) (ほぼ、ほとんど) 一定を意味します C, 、サイズに関係なく N.

の for 文 1 のステートメントは注意が必要です。インデックスは次で終わりますが、 2 * N, 、増分は 2 ずつ行われます。つまり、最初の for 実行されるだけ N ステップなので、カウントを 2 で割る必要があります。

f(N) = Summation(i from 1 to 2 * N / 2)( ... ) = 
     = Summation(i from 1 to N)( ... )

文番号二の値に依存するため、さらに複雑になります。 i. 。ご覧ください:インデックス i は次の値を取ります。0、2、4、6、8、...、2 * N、および 2 番目 for 実行される:最初は N 倍、2 回目は N - 2、3 回目は N - 4...N / 2 ステージまで、2 番目のステージ for 決して処刑されることはありません。

式では、それは次のことを意味します。

f(N) = Summation(i from 1 to N)( Summation(j = ???)(  ) )

繰り返しますが、私たちは数えています歩数. 。そして定義上、すべての合計は常に 1 で始まり、1 以上の数値で終わる必要があります。

f(N) = Summation(i from 1 to N)( Summation(j = 1 to (N - (i - 1) * 2)( C ) )

(次のように仮定しています) foo() は O(1) そしてかかります C ステップ。）

ここで問題が発生します。いつ i 値を受け取ります N / 2 + 1 上向きにすると、内部の合計は負の数で終わります。それは不可能だし間違っている。合計を 2 つに分割する必要があります。ここが重要なポイントになります。 i かかります N / 2 + 1.

f(N) = Summation(i from 1 to N / 2)( Summation(j = 1 to (N - (i - 1) * 2)) * ( C ) ) + Summation(i from 1 to N / 2) * ( C )

極めて重要な瞬間以来 i > N / 2, 、内部 for は実行されず、本体の C 実行の複雑さは一定であると想定しています。

ここで、いくつかの恒等規則を使用して合計を簡略化できます。

合計(1からNまでのw)( C ) = N * C
総和(1 から N までの w)( A (+/-) B ) = 総和(1 から N までの w)( A ) (+/-) 総和(1 から N までの w)( B )
Summation(w from 1 to N)( w * C ) = C * Summation(w from 1 to N)( w ) (C は定数であり、 w)
合計(1からNまでのw)( w ) = (N * (N + 1)) / 2

いくつかの代数を適用すると、次のようになります。

f(N) = Summation(i from 1 to N / 2)( (N - (i - 1) * 2) * ( C ) ) + (N / 2)( C )

f(N) = C * Summation(i from 1 to N / 2)( (N - (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (Summation(i from 1 to N / 2)( N ) - Summation(i from 1 to N / 2)( (i - 1) * 2)) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2)( i - 1 )) + (N / 2)( C )

=> Summation(i from 1 to N / 2)( i - 1 ) = Summation(i from 1 to N / 2 - 1)( i )

f(N) = C * (( N ^ 2 / 2 ) - 2 * Summation(i from 1 to N / 2 - 1)( i )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N / 2 - 1) * (N / 2 - 1 + 1) / 2) ) + (N / 2)( C )

=> (N / 2 - 1) * (N / 2 - 1 + 1) / 2 = 

   (N / 2 - 1) * (N / 2) / 2 = 

   ((N ^ 2 / 4) - (N / 2)) / 2 = 

   (N ^ 2 / 8) - (N / 4)

f(N) = C * (( N ^ 2 / 2 ) - 2 * ( (N ^ 2 / 8) - (N / 4) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - ( (N ^ 2 / 4) - (N / 2) )) + (N / 2)( C )

f(N) = C * (( N ^ 2 / 2 ) - (N ^ 2 / 4) + (N / 2)) + (N / 2)( C )

f(N) = C * ( N ^ 2 / 4 ) + C * (N / 2) + C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + 2 * C * (N / 2)

f(N) = C * ( N ^ 2 / 4 ) + C * N

f(N) = C * 1/4 * N ^ 2 + C * N

BigOh は次のとおりです。

O(N²)

他のヒント

Big O は、アルゴリズムの時間計算量の上限を与えます。通常、データセット (リスト) の処理と組み合わせて使用されますが、他の場所でも使用できます。

C コードでの使用例をいくつか示します。

n 個の要素の配列があるとします。

int array[n];

配列の最初の要素にアクセスしたい場合、配列の大きさに関係なく、最初の項目を取得するのに常に同じ一定の時間がかかるため、これは O(1) になります。

x = array[0];

リスト内の番号を見つけたい場合は、次のようにします。

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

番号を見つけるにはせいぜいリスト全体を調べる必要があるため、これは O(n) になります。Big-O は、最初の試行で数値を見つけてループを 1 回実行したとしても、依然として O(n) です。これは、Big-O がアルゴリズムの上限を記述するためです (オメガは下限を表し、シータはタイトバウンドを表します)。。

ネストされたループに到達すると、次のようになります。

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

これは O(n^2) です。外側のループ ( O(n) ) の各パスでリスト全体を再度調べる必要があるため、n を乗算すると n の 2 乗が残ります。

これはほんの表面をなぞっただけですが、より複雑なアルゴリズムを分析するようになると、証明を含む複雑な数学が必要になります。ただし、少なくとも基本については理解していただければ幸いです。

特定の問題の Big O 時間を計算する方法を知っていることは役に立ちますが、いくつかの一般的なケースを知っておくことは、アルゴリズムでの意思決定に大いに役立ちます。

以下に、最も一般的なケースをいくつか挙げます。 http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions:

O(1) - 数値が偶数か奇数かを判断します。一定サイズのルックアップテーブルまたはハッシュテーブルを使用する

O(logn) - 二分探索によるソートされた配列内の項目の検索

O(n) - ソートされていないリスト内の項目を検索します。2 つの n 桁の数字を加算する

の上²) - 単純なアルゴリズムによる 2 つの n 桁の数値の乗算。2 つの n×n 行列を追加します。バブルソートまたは挿入ソート

の上³) - 単純なアルゴリズムによる 2 つの n×n 行列の乗算

O(cⁿ) - 動的プログラミングを使用して巡回セールスマン問題の (正確な) 解決策を見つける。ブルートフォースを使用して 2 つの論理ステートメントが同等かどうかを判断する

O(n!) - 総当たり検索による巡回セールスマン問題の解決

の上ⁿ) - 漸近複雑さのより単純な式を導出するために、O(n!) の代わりによく使用されます。

ちょっとした注意事項:の big O 表記法は次のことを示すために使用されます 漸近的 複雑さ (つまり、問題のサイズが無限大に増大する場合)、 そして 定数を隠します。

これは、O(n) のアルゴリズムと O(n) のアルゴリズムの間で²)、最速が常に最初のアルゴリズムであるとは限りません (ただし、サイズ > n の問題の場合、最初のアルゴリズムが最速になるように n の値が常に存在します)。

隠し定数は実装に大きく依存することに注意してください。

また、場合によっては、ランタイムが決定的な関数ではないこともあります。 サイズ 入力の n。クイックソートを使用した並べ替えを例に挙げます。n 要素の配列をソートするのに必要な時間は一定ではなく、配列の開始時の構成によって異なります。

さまざまな時間計算量があります。

最悪のケース (通常は最も簡単に判断できますが、常に意味があるとは限りません)
平均的なケース (通常、理解するのは非常に困難です...)
...

良い紹介は、 アルゴリズム分析の概要 R 著セジウィックと P.フラジョレット。

あなたが言うように、 premature optimisation is the root of all evil, 、そして（可能であれば） プロファイリング 実際には、コードを最適化するときに常に使用する必要があります。アルゴリズムの複雑さを判断するのにも役立ちます。

ここでの答えを見ると、私たちのほとんどはアルゴリズムの次数を実際に次のように近似していると結論付けることができると思います。 探している たとえば、マスターメソッド私たちが大学で考えていたように。そうは言っても、教授さえも私たちに（後で）実際にそうするよう勧めてくれたことを付け加えなければなりません。 考える ただ計算するのではなく、それについて考えてみてください。

また、それがどのように行われるかを追加したいと思います 再帰関数:

(のような関数があるとします)スキームコード):

(define (fac n)
    (if (= n 0)
        1
            (* n (fac (- n 1)))))

指定された数値の階乗を再帰的に計算します。

最初のステップは、パフォーマンス特性を試して判断することです。 関数本体のみ この場合、本体では特別なことは何も行われず、単に乗算 (または値 1 を返す) が行われるだけです。

それで、 本体のパフォーマンスは次のとおりです。○(1) （絶え間ない）。

次にこれを試して決定してください 再帰呼び出しの数. 。この場合、n-1 個の再帰呼び出しがあります。

それで、 再帰呼び出しのパフォーマンスは次のとおりです。O(n-1) (重要でない部分は破棄するため、順序は n です)。

次に、これら 2 つを組み合わせると、再帰関数全体のパフォーマンスが得られます。

1 * (n-1) = O(n)

ピーター, 、答えるあなたが提起した問題。ここで説明する方法は実際にこれを非常にうまく処理します。ただし、これはまだ問題であることに注意してください。近似数学的に完全に正しい答えではありません。ここで説明する方法も大学で教えられた方法の 1 つで、私の記憶が正しければ、この例で使用した階乗よりもはるかに高度なアルゴリズムに使用されていました。
もちろん、すべては関数本体の実行時間と再帰呼び出しの数をどれだけ正確に見積もることができるかによって決まりますが、それは他のメソッドにも同様に当てはまります。

コストが多項式の場合は、乗数を付けずに最高次項だけを保持します。例えば。：

O((n/2 + 1)*(n/2)) = O(n²/4 + n/2) = O(n²/4) = O(n²)

これは無限シリーズでは機能しません、念のため。一般的なケースに単一のレシピはありませんが、いくつかの一般的なケースでは、次の不等式が適用されます。

O(ログ N) < O(N) < O(N ログ N) < O(N²) < O(N^k) < O(eⁿ) < O(n!)

情報という観点から考えてみます。どのような問題も、特定のビット数を学習することで構成されます。

基本的なツールは、意思決定ポイントとそのエントロピーの概念です。決定点のエントロピーは、決定点から得られる平均的な情報です。たとえば、プログラムに 2 つの分岐を持つ決定点が含まれている場合、そのエントロピーは、各分岐の確率とログの合計の合計になります。₂ その分岐の逆確率。その決定を実行することでどれだけ多くのことを学ぶことができます。

たとえば、 if 2 つの分岐を持つステートメントのエントロピーは、両方とも同じ確率で、1/2 * log(2/1) + 1/2 * log(2/1) = 1/2 * 1 + 1/2 * 1 = 1 となります。したがって、そのエントロピーは 1 ビットです。

N=1024 のように、N 個の項目からなるテーブルを検索しているとします。log(1024) = 10 ビットなので、これは 10 ビットの問題です。したがって、同じ可能性の結果が得られる IF ステートメントを使用して検索できる場合、10 回の決定が必要になるはずです。

それは二分探索で得られるものです。

線形探索を行っているとします。最初の要素を見て、それが必要なものかどうかを尋ねます。そうなる確率は 1/1024、そうでない確率は 1023/1024 です。その決定のエントロピーは、1/1024*log(1024/1) + 1023/1024 * log(1024/1023) = 1/1024 * 10 + 1023/1024 * 約 0 = 約 0.01 ビットです。あなたはほとんど学んでいません！2 番目の決定はそれほど良いものではありません。これが、線形検索が非常に遅い理由です。実際、学習する必要があるビット数は指数関数的に増加します。

インデックス作成を行っているとします。テーブルが多数のビンに事前に並べ替えられており、キー内のすべてのビットの一部を使用してテーブルエントリに直接インデックスを付けるとします。1024 個のビンがある場合、エントロピーは 1/1024 * log(1024) + 1/1024 * log(1024) + ... になります。1024 のすべての可能な結果について。これは、1/1024 * 10 倍 1024 の結果、つまり 1 回のインデックス付け操作の 10 ビットのエントロピーです。これが、インデックス検索が高速である理由です。

次に、並べ替えについて考えてみましょう。N 個の項目があり、リストがあります。項目ごとに、その項目がリスト内のどこにあるかを検索し、リストに追加する必要があります。したがって、並べ替えには、基になる検索のステップ数のおよそ N 倍かかります。

したがって、ほぼ同じ確率の結果をもたらす二項決定に基づく並べ替えには、すべて約 O(N log N) ステップがかかります。インデックス検索に基づく場合、O(N) ソートアルゴリズムが可能です。

ほぼすべてのアルゴリズムのパフォーマンスの問題は、この方法で検討できることがわかりました。

最初から始めましょう。

まず第一に、データに対する特定の単純な操作はで実行できるという原則を受け入れます。 O(1) 時間、つまり入力のサイズに依存しない時間です。C のこれらの原始的な操作は次のもので構成されます。

算術演算 (例:+ または %)。
論理演算 (例: &&)。
比較演算 (<= など)。
構造体へのアクセス操作 (例:i]のような配列インデックス、または - >演算子とのポインターに従う）。
値を変数にコピーするなどの単純な代入。
ライブラリ関数 (scanf、printf など) の呼び出し。

この原理を正当化するには、典型的なコンピュータの機械命令 (原始ステップ) を詳細に研究する必要があります。説明した各操作は、少数のマシン命令で実行できます。多くの場合、必要な命令は 1 つまたは 2 つだけです。その結果、C のいくつかの種類のステートメントを C で実行できます。 O(1) 時間、つまり入力に関係なく一定の時間内です。これらの単純な内容には、

式に関数呼び出しを含まない代入ステートメント。
ステートメントを読みます。
引数を評価するために関数呼び出しを必要としないステートメントを作成します。
ジャンプステートメントは、式に機能呼び出しが含まれていない場合、式を破壊し、続行し、gotoし、式を返すことができます。

Cでは、インデックス変数を何らかの値に初期化し、ループの周りにその変数を1倍に増分することにより、多くのloopsが形成されます。インデックスが何らかの制限に達すると、for-loopは終了します。たとえば、for ループ

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

インデックス変数 i を使用します。ループの周りに毎回Iを増加させ、n - 1に到達すると反復が止まります。

ただし、現時点では、for ループの単純な形式に注目してください。 最終値と初期値の差をインデックス変数の増加量で割ると、ループを何回繰り返すかがわかります。. 。Jump ステートメントを介してループを終了する方法がない限り、このカウントは正確です。いずれの場合も、それは反復回数の上限です。

たとえば、for ループは反復します。 ((n − 1) − 0)/1 = n − 1 times、0はiの初期値であるため、n - 1はiによって到達される最高値です（すなわち、iがn -1に達すると、ループ停止が停止し、i = n -1で反復が発生しません）、1が追加され、1が追加されます。ループの各反復で。

最も簡単な場合、ループ本体で費やされる時間が反復ごとに同じである場合、 ボディのBig-OH上限にループの周りの回数を掛けることができます. 。厳密に言えば、次のようにしなければなりません。 ループインデックスを初期化するためにO（1）時間を追加し、ループインデックスを制限と最初に比較するためにO（1）時間, 、ループを一周するよりも 1 回多くテストするためです。ただし、ループゼロ回を実行することができない限り、ループを初期化して制限をテストする時間は、合計ルールで削除できる低次項です。

次に、次の例を考えてみましょう。

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

私達はことを知っています ライン1） かかります O(1) 時間。明らかに、ライン（1）にある上限から下限を差し引き、1を追加することで決定できるため、ループを回転させます。本体、線（2）にはO（1）に時間がかかるため、Jを増分する時間とJとnを比較する時間を無視することができます。どちらもO（1）です。したがって、行 (1) と (2) の実行時間は次のようになります。 n と O の積(1), 、つまり O(n).

同様に、線（2）から（4）で構成される外側ループの実行時間をバウンドできます。

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

行 (3) と行 (4) のループには O(n) 時間がかかることはすでに確認されています。したがって、O（1）時間を無視し、Iを増分し、各反復でI <nがO（n）時間にかかると結論付けます。

外部ループの初期化I = 0と（n + 1）条件I <nのSTテストは、同様にO（1）時間を取り、無視することができます。最後に、私たちは外側のループを回避し、各反復にO（n）時間をかけ、合計を与えることを観察しますO(n^2) 実行時間。

より実践的な例。

enter image description here

コードを分析するのではなく、経験的にコードの順序を推定したい場合は、n の値を連続的に増加させてコードの時間を計測することができます。タイミングを対数スケールでプロットします。コードが O(x^n) の場合、値は傾き n の線上に収まる必要があります。

これには、単にコードを勉強するよりもいくつかの利点があります。まず、実行時間が漸近順序に近づく範囲内にいるかどうかを確認できます。また、ライブラリ呼び出しに費やした時間などにより、O(x) 次だと思っていたコードが実際には O(x^2) 次であることがわかる場合もあります。

基本的に、90% の確率で発生するのはループの分析だけです。単一、二重、三重のネストされたループはありますか?実行時間は O(n)、O(n^2)、O(n^3) です。

非常にまれに、(たとえば、.NET BCL や C++ の STL などの) 広範な基本ライブラリを備えたプラットフォームを作成している場合を除き、ループ (for ステートメント、while、goto、等...）

アルゴリズムをビッグ O 表記法がわかっている部分に分割し、ビッグ O 演算子を介して結合します。それが私が知っている唯一の方法です。

詳細については、ウィキペディアのページ件名に。

Big O 記法は、扱いやすく、不必要な複雑さや詳細を (不必要の定義によっては) 隠すことができるため便利です。分割統治アルゴリズムの複雑さを解決する優れた方法の 1 つは、ツリー法です。中央値プロシージャを備えたバージョンのクイックソートがあるとします。そのため、毎回配列を完全にバランスの取れたサブ配列に分割します。

ここで、操作するすべての配列に対応するツリーを構築します。ルートには元の配列があり、ルートにはサブ配列である 2 つの子があります。単一要素の配列が一番下になるまでこれを繰り返します。

O(n) 時間で中央値を見つけ、O(n) 時間で配列を 2 つの部分に分割できるため、各ノードで行われる作業は O(k) になります (k は配列のサイズです)。ツリーの各レベルには (多くても) 配列全体が含まれるため、レベルごとの作業は O(n) になります (部分配列のサイズを合計すると n になります。レベルごとに O(k) があるため、これを合計できます)。。入力を半分にするたびに、ツリーには log(n) レベルのみが存在します。

したがって、作業量の上限を O(n*log(n)) にすることができます。

ただし、Big O には、無視できないいくつかの詳細が隠されています。次のフィボナッチ数列を計算することを検討してください。

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

そして、a と b が Java の BigInteger か、任意の大きな数値を処理できる何かであると仮定します。ほとんどの人は、これは O(n) アルゴリズムだとひるむことなく言うでしょう。その理由は、for ループ内に n 回の反復があり、ループ内で O(1) が動作するためです。

しかし、フィボナッチ数は大きく、n 番目のフィボナッチ数は n の指数関数であるため、それを保存するだけでも n バイトのオーダーがかかります。大きな整数で加算を実行すると、O(n) 個の作業量がかかります。したがって、この手順で行われる作業の合計量は次のようになります。

1 + 2 + 3 + ...+ n = n(n-1)/2 = O(n^2)

つまり、このアルゴリズムは 2 次時間で実行されます。

使用するアルゴリズムやデータ構造、および/または反復ネストの簡単な分析に精通していること。問題は、ライブラリ関数をおそらく複数回呼び出すときです。関数を不必要に呼び出しているのかどうか、または関数がどのような実装を使用しているのかがよくわからないことがよくあります。おそらくライブラリ関数には、Big O であろうと他の指標であろうと、ドキュメントやさらには入手可能な複雑さ/効率性の尺度が必要です。インテリセンス.

一般的にはあまり有用ではないと思いますが、完全を期すために、ビッグオメガΩ, 、アルゴリズムの複雑さの下限を定義します。ビッグシータΘ, 、上限と下限の両方を定義します。

Big O を「どのように計算するか」については、これは計算量理論. 。いくつかの (多くの) 特殊なケースでは、いくつかの単純なヒューリスティック (入れ子になったループのループ数を乗算するなど) を使用できる場合があります。必要なのは上限推定値だけで、それが悲観的すぎても気にしない場合 - おそらくそれがあなたの質問の内容だと思います。

アルゴリズムに関する質問に本当に答えたい場合、できる最善のことは理論を適用することです。私が見つけた単純な「最悪の場合」の分析に加えて償却分析実際に非常に役立ちます。

1 番目のケースでは、内側のループが実行されます。 n-i 回なので、実行の合計数は次の合計になります。 i から行く 0 に n-1 (以下ではなく、以下であるため) n-i. 。ついに得られる n*(n + 1) / 2, 、それで O(n²/2) = O(n²).

2 番目のループでは、 i は間に 0 そして n 外側のループに含まれます。内側のループは次のときに実行されます。 j 厳密には次より大きいです n, 、それなら不可能です。

マスターメソッド (またはその特殊化の 1 つ) の使用に加えて、アルゴリズムを実験的にテストします。これはできません 証明する 特定の複雑度クラスが達成されていることはわかりますが、数学的分析が適切であるという安心感を与えることができます。この安心感を高めるために、私は実験と組み合わせてコードカバレッジツールを使用し、すべてのケースを確実に実行できるようにしています。

非常に単純な例として、.NET Framework のリストソートの速度について健全性チェックを行いたいとします。次のような内容を記述し、結果を Excel で分析して、n*log(n) 曲線を超えていないことを確認できます。

この例では比較の数を測定しますが、各サンプルサイズに必要な実際の時間を調べることも賢明です。ただし、アルゴリズムを測定しているだけであり、テストインフラストラクチャからのアーティファクトは含まれていないことにさらに注意する必要があります。

int nCmp = 0;
System.Random rnd = new System.Random();

// measure the time required to sort a list of n integers
void DoTest(int n)
{
   List<int> lst = new List<int>(n);
   for( int i=0; i<n; i++ )
      lst[i] = rnd.Next(0,1000);

   // as we sort, keep track of the number of comparisons performed!
   nCmp = 0;
   lst.Sort( delegate( int a, int b ) { nCmp++; return (a<b)?-1:((a>b)?1:0)); }

   System.Console.Writeline( "{0},{1}", n, nCmp );
}


// Perform measurement for a variety of sample sizes.
// It would be prudent to check multiple random samples of each size, but this is OK for a quick sanity check
for( int n = 0; n<1000; n++ )
   DoTest(n);

メモリリソースが限られている場合には、スペースの複雑さも考慮することを忘れないでください。これも懸念の原因となります。したがって、たとえば、一定スペースアルゴリズムを求める人がいるかもしれません。これは基本的に、アルゴリズムが使用するスペースの量はコード内のいかなる要素にも依存しない、ということを意味します。

場合によっては、何かが呼び出される回数、ループが実行される頻度、メモリが割り当てられる頻度などによって複雑さが発生することがあります。これは、この質問に答えるもう 1 つの部分です。

最後に、大きな O は、最悪のケース、最良のケース、および償却ケースに使用できます。一般に、アルゴリズムがどの程度悪いかを説明するために使用されるのは最悪のケースです。

見落とされがちなのが、 期待される アルゴリズムの動作。 アルゴリズムの Big-O は変わりません, しかし、これは「時期尚早な最適化」という記述に関連しています。。..」

アルゴリズムの期待される動作は、非常に単純化して、表示される可能性が最も高いデータに対してアルゴリズムがどの程度の速度で動作すると期待できるかです。

たとえば、リスト内の値を検索する場合、それは O(n) ですが、表示されるほとんどのリストに値が事前に含まれていることを知っていれば、アルゴリズムの通常の動作は高速になります。

それを本当に正確に特定するには、「入力空間」の確率分布を記述できる必要があります (リストをソートする必要がある場合、そのリストはどのくらいの頻度ですでにソートされているでしょうか?完全に逆転する頻度はどれくらいですか？どれくらいの頻度でほとんどソートされていますか?) それを常に知っているわけではありませんが、知っている場合もあります。

素晴らしい質問です！

免責事項:この回答には虚偽の記述が含まれています。以下のコメントを参照してください。

Big O を使用している場合は、より悪いケースについて話していることになります (これが何を意味するかについては後で詳しく説明します)。さらに、平均的なケースには大文字のシータがあり、最良のケースには大きなオメガがあります。

Big O の正式な定義については、このサイトをご覧ください。 https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) は、すべての n ≥ k に対して 0 ≤ f(n) ≤ cg(n) となる、正の定数 c と k が存在することを意味します。c と k の値は関数 f に対して固定されている必要があり、n に依存してはなりません。

さて、「最良の場合」と「最悪の場合」の複雑さは何を意味するのでしょうか?

これはおそらく、例を通して最も明確に説明されます。たとえば、線形検索を使用してソートされた配列内の数値を検索する場合、 最悪の場合 それは私たちが決断するときです 最後の要素を検索する これには、配列内の項目と同じ数のステップが必要となるためです。の 最良の場合 を検索するとそうなります 最初の要素 最初のチェックが終わったら完了するからです。

これらすべてのポイントは 形容詞-case の複雑さは、特定の変数のサイズに関して、仮説上のプログラムが完了するまでの実行時間をグラフ化する方法を探していることです。ただし、多くのアルゴリズムでは、特定のサイズの入力に対して 1 回の時間は存在しないと主張できます。これは関数の基本的な要件と矛盾することに注意してください。入力は 1 つ以上の出力を持つべきではありません。そこで私たちはこう思いつきます複数アルゴリズムの複雑さを記述する関数。サイズ n の配列の検索にかかる時間は、配列内で何を探しているか、n に比例するかによって異なりますが、最良の場合と平均的な場合を使用してアルゴリズムの有益な説明を作成できます。、および最悪の場合のクラス。

申し訳ありませんが、これは非常に稚拙に書かれており、技術的な情報があまりありません。しかし、うまくいけば、時間計算量のクラスを考えるのが容易になります。これらに慣れると、プログラムを解析して、配列サイズに依存する for ループなどを探したり、データ構造に基づいて推論したりして、どのような種類の入力が些細なケースをもたらすか、またどのような入力が結果として生じるかを調べるのが簡単になります。最悪の場合。

これをプログラム的に解決する方法はわかりませんが、人々が最初に行うことは、実行された操作の数における特定のパターンのアルゴリズムをサンプリングすることです。たとえば、4n^2 + 2n + 1 には 2 つのルールがあります。

項の合計がある場合、最大の成長率を示す項が保持され、他の項は省略されます。
複数の因子の積がある場合、定数因子は省略されます。

f(x) を単純化すると、f(x) は実行された演算数の公式 (上で説明した 4n^2 + 2n + 1) となり、big-O 値 [O(n^2) が得られます。場合]。ただし、これにはプログラム内のラグランジュ補間を考慮する必要があり、実装が難しい場合があります。そして、実際の big-O 値が O(2^n) で、O(x^n) のような値になる場合はどうなるでしょうか。そのため、このアルゴリズムはおそらくプログラム可能ではありません。しかし、誰かが私が間違っていると証明したら、コードを教えてください。。。。

コード A の場合、外側のループは次のように実行されます。 n+1 「1」回は、要件をまだ満たしているかどうかをチェックするプロセスを意味します。そして内側のループが実行されます n 回、 n-2 回....したがって、0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

コード B の場合、内側のループは介入して foo() を実行しませんが、内側のループは外側のループの実行時間 (O(n)) に応じて n 回実行されます。

ビッグオーについて、少し違った側面から解説していきたいと思います。

Big-O は、プログラムの複雑さを比較するだけであり、入力が増加したときにプログラムがどれだけ速く成長するかを意味し、アクションの実行に費やされる正確な時間を比較するものではありません。

私の意見では、big-O の式では、より複雑な式は使用しないほうがよいでしょう (次のグラフのものに固執するだけでもよいでしょう)。ただし、他のより正確な式 (3^n、n^3 など) を使用することもできます。 .) しかし、それ以上は誤解を招く可能性があります。したがって、できるだけシンプルにしておく方が良いでしょう。

ここでアルゴリズムの正確な式を取得したいわけではないことをもう一度強調したいと思います。入力が増加するときにどのように増加するかを示し、その意味で他のアルゴリズムと比較することのみを目的としています。それ以外の場合は、ベンチマークなどの別の方法を使用することをお勧めします。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow