CS の学位を取得したほとんどの人は、 Big O の略語を知っているはずです。アルゴリズムがどれだけうまくスケールするかを測定するのに役立ちます。
しかし、興味深いのは、アルゴリズムの複雑さをどのように計算または概算するのですか?
質問する
479364 次
24 に答える
1526
ここでは簡単な言葉で説明するように最善を尽くしますが、このトピックを生徒が最終的に理解するには数か月かかることに注意してください。詳細については、Javaブックのデータ構造とアルゴリズムの第2章を参照してください。
BigOhを取得するために使用できる機械的な手順はありません。
「クックブック」として、コードの一部から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)（ほぼ）一定を意味します。CN
for文番号1の記述は注意が必要です。インデックスはで終了し2 * Nますが、増分は2で行われます。つまり、最初のfor実行はNステップのみであり、カウントを2で割る必要があります。
f(N) = Summation(i from 1 to 2 * N / 2)( ... ) =
= Summation(i from 1 to N)( ... )
文番号2は、の値に依存するため、さらに注意が必要ですi。見てみましょう：インデックスiは値を取ります：0、2、4、6、8、...、2 * N、そして2番目forが実行されます：最初のもののN倍、N-2秒、N-4 3番目...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実行の複雑さを想定しています。
これで、いくつかのIDルールを使用して合計を簡略化できます。
- Summation（w from 1 to N）（C）= N * C
- Summation（w from 1 to N）（A（+/-）B）= Summation（w from 1 to N）（A）（+/-）Summation（w from 1 to N）（B）
- Summation（w from 1 to N）（w * C）= C * Summation（w from 1 to N）（w）（Cは定数であり、
w）に依存しません - Summation（w from 1 to N）（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²)
于 2011-01-31T15:33:54.120 に答える
209
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 回実行して数値を見つけたとしても、Big-O は依然として O(n) です (オメガは下限を表し、シータはタイト バウンドを表します)。 .
ネストされたループに到達すると、次のようになります。
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 乗が残るからです。
これはほんの表面をなぞっただけですが、より複雑なアルゴリズムを分析する場合、証明を含む複雑な数学が必要になります。ただし、これで少なくとも基本に慣れることを願っています。
于 2008-08-06T13:34:13.753 に答える
108
特定の問題の Big O 時間を計算する方法を知ることは役に立ちますが、いくつかの一般的なケースを知ることは、アルゴリズムで決定を下すのに大いに役立ちます。
http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functionsから取り上げた、最も一般的なケースのいくつかを次に示します。
O(1) - 数値が偶数か奇数かを判断します。一定サイズのルックアップ テーブルまたはハッシュ テーブルを使用する
O(logn) - 二分探索によるソート済み配列内の項目の検索
O(n) - ソートされていないリスト内の項目を検索します。2 つの n 桁の数字の足し算
O(n 2 ) - 簡単なアルゴリズムによる 2 つの n 桁の数字の乗算。2 つの n×n 行列を追加します。バブルソートまたは挿入ソート
O(n 3 ) - 単純なアルゴリズムによる 2 つの n×n 行列の乗算
O(c n ) - 動的計画法を使用して巡回セールスマン問題の (正確な) 解を見つける; ブルートフォースを使用して2つの論理ステートメントが等しいかどうかを判断する
O(n!) - 総当たり検索による巡回セールスマン問題の解決
O(n n ) - O(n!) の代わりによく使用され、漸近的な複雑さのより単純な式を導き出します。
于 2008-09-05T19:09:48.837 に答える
43
ちょっとした注意: このbig O表記法は、漸近的な複雑さ (つまり、問題のサイズが無限大になるとき)を表すために使用され、定数を隠します。
これは、O(n) のアルゴリズムと O(n 2 ) のアルゴリズムの間で、最初のアルゴリズムが常に最速であるとは限らないことを意味します (ただし、サイズ >n の問題の場合、最初のアルゴリズムは最速）。
隠し定数は実装に大きく依存することに注意してください!
また、場合によっては、ランタイムは入力のサイズn の決定論的関数ではありません。たとえば、クイック ソートを使用したソートを考えてみましょう。n 要素の配列をソートするのに必要な時間は定数ではなく、配列の開始構成によって異なります。
さまざまな時間の複雑さがあります。
- 最悪の場合 (通常は最も簡単に判断できますが、必ずしも意味があるとは限りません)
平均的なケース (通常、把握するのははるかに困難です...)
...
よい入門書は、R. Sedgewick と P. Flajolet によるAn Introduction to the Analysis of Algorithmsです。
あなたが言うようにpremature optimisation is the root of all evil、そして（可能であれば）プロファイリングは、コードを最適化するときに常に使用する必要があります。アルゴリズムの複雑さを判断するのにも役立ちます。
于 2008-08-23T20:43:50.357 に答える
30
ここでの答えを見ると、私たちのほとんどは実際にアルゴリズムの順序を概算して、たとえば大学で考えられていたマスターメソッドで計算するのではなく、常識を使用していると結論付けることができると思います. そうは言っても、教授でさえ私たちに（後で）計算するだけでなく、実際にそれについて考えるように勧めたことを付け加えなければなりません.
また、再帰関数に対してそれがどのように行われるかを追加したいと思います:
( scheme code )のような関数があるとします:
(define (fac n)
(if (= n 0)
1
(* n (fac (- n 1)))))
指定された数値の階乗を再帰的に計算します。
最初のステップは、この場合にのみ関数本体のパフォーマンス特性を試して決定することです。本体では何も特別なことは行われず、乗算 (または値 1 の戻り値) のみが実行されます。
したがって、本体のパフォーマンスは O(1) (定数) です。
次に、再帰呼び出しの数についてこれを決定してみてください。この場合、n-1 回の再帰呼び出しがあります。
したがって、再帰呼び出しのパフォーマンスは次のようになります: O(n-1) (重要でない部分を破棄するため、次数は n です)。
次に、これら 2 つを組み合わせると、再帰関数全体のパフォーマンスが得られます。
1 * (n-1) = O(n)
ピーター、あなたが提起した問題に答えるために。ここで説明する方法は、実際にこれをうまく処理します。ただし、これはまだ概算であり、数学的に完全に正しい答えではないことに注意してください。ここで説明する方法は、大学で教えられた方法の 1 つでもあり、私の記憶が正しければ、この例で使用した階乗よりもはるかに高度なアルゴリズムに使用されていました。
もちろん、それは関数本体の実行時間と再帰呼び出しの回数をどれだけ正確に見積もれるかにかかっていますが、それは他の方法にも当てはまります。
于 2008-08-07T08:10:04.780 に答える
27
コストが多項式の場合は、乗数なしで最上位の項を保持します。例えば：
O（（n / 2 + 1）*（n / 2））= O（n 2/4 + n / 2）= O（n 2/4 ） = O（n 2）
これは無限級数では機能しません。一般的なケースの単一のレシピはありませんが、いくつかの一般的なケースでは、次の不等式が適用されます。
O（log N）<O（N）<O（N log N）<O（N 2）<O（N k）<O（e n）<O（n！）
于 2011-01-31T13:30:15.113 に答える
23
情報として考えてみます。どの問題も、特定の数のビットを学習することで構成されます。
基本的なツールは、決定点とそのエントロピーの概念です。ディシジョン ポイントのエントロピーは、それが提供する平均的な情報です。たとえば、プログラムに 2 つの分岐がある決定点が含まれている場合、そのエントロピーは、各分岐の確率の合計にその分岐の逆確率のlog 2を掛けたものになります。それは、その決定を実行することによって、どれだけ多くを学ぶかです。
たとえば、if2 つの分岐があり、どちらも確率が同じであるステートメントのエントロピーは、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 = 約 .01 ビットです。あなたはほとんど学んでいません！2 番目の決定はあまり良くありません。それが、線形探索が非常に遅い理由です。実際、学習する必要があるビット数は指数関数的です。
索引付けを行っているとします。テーブルが多数のビンに事前にソートされており、キー内のすべてのビットの一部を使用して、テーブル エントリに直接インデックスを付けているとします。1024 個のビンがある場合、エントロピーは 1/1024 * log(1024) + 1/1024 * log(1024) + ... であり、1024 個の可能な結果すべてについてです。これは、1/1024 * 1024 の結果の 10 倍、またはその 1 つのインデックス操作の 10 ビットのエントロピーです。そのため、インデックス検索は高速です。
次に、並べ替えについて考えます。N 個のアイテムがあり、リストがあります。項目ごとに、項目がリスト内のどこにあるかを検索してから、リストに追加する必要があります。したがって、ソートには、基礎となる検索のステップ数のおよそ N 倍の時間がかかります。
そのため、ほぼ同じ結果になる可能性があるバイナリ決定に基づくソートは、すべて O(N log N) ステップかかります。インデックス検索に基づいている場合、O(N) ソート アルゴリズムが可能です。
ほぼすべてのアルゴリズムのパフォーマンスの問題は、この方法で調べることができることがわかりました。
于 2009-03-10T13:24:13.873 に答える
16
コードを分析するのではなく、経験的にコードの順序を推定したい場合は、一連の増加する n の値に固執し、コードの時間を計ることができます。対数スケールでタイミングをプロットします。コードが O(x^n) の場合、値は傾き n の直線上にあるはずです。
これには、コードを勉強するだけに比べていくつかの利点があります。1 つには、実行時間が漸近順序に近づく範囲にいるかどうかを確認できます。また、たとえばライブラリ呼び出しに費やされた時間が原因で、順序 O(x) だと思っていた一部のコードが実際には順序 O(x^2) であることに気付く場合もあります。
于 2008-12-11T20:49:05.190 に答える
12
基本的に、90% の確率で発生するのは、ループの分析だけです。シングル、ダブル、トリプルのネストされたループはありますか? O(n)、O(n^2)、O(n^3) の実行時間があります。
ごくまれに (.NET BCL や C++ の STL などの広範な基本ライブラリを使用してプラットフォームを作成している場合を除きます)、ループ (ステートメント、while、goto、等...）
于 2008-08-14T15:35:50.200 に答える
9
一般的にはあまり役に立たないと思いますが、完全を期すために、アルゴリズムの複雑さの下限を定義するBig Omega Ωと、上限と下限の両方を定義するBig Theta Θもあります。
于 2008-09-23T07:26:08.710 に答える
8
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 次時間で実行されます。
于 2008-08-08T13:53:20.930 に答える
7
使用しているアルゴリズムやデータ構造に精通していること、および/または繰り返しの入れ子構造を一目で分析できること。問題は、ライブラリ関数を複数回呼び出す場合です。関数を不必要に呼び出しているかどうか、またはそれらが使用している実装が不明な場合がよくあります。おそらく、ライブラリ関数には、ドキュメントやIntelliSenseで利用できる Big O であろうと他のメトリックであろうと、複雑さ/効率の尺度が必要です。
于 2008-08-06T10:59:40.603 に答える
7
ビッグ O 表記法を知っている断片にアルゴリズムを分解し、ビッグ O 演算子を使用して結合します。それが私が知っている唯一の方法です。
詳細については、件名のウィキペディアのページを確認してください。
于 2008-08-06T11:34:26.803 に答える
6
最初のケースでは、内側のループがn-i回実行されるため、実行の合計数は、 のiから0までn-1(より小さいため、以下ではないため)の合計になりn-iます。あなたは最終的に得るn*(n + 1) / 2ので、O(n²/2) = O(n²).
2 番目のループでは、外側のループのi間に0あり、含まれています。が厳密に より大きいn場合に内側のループが実行されますが、これは不可能です。jn
于 2011-01-31T14:36:02.787 に答える
5
マスターメソッド（またはその特殊化の1つ）を使用することに加えて、私はアルゴリズムを実験的にテストします。これは、特定の複雑さのクラスが達成されたことを証明することはできませんが、数学的分析が適切であるという安心感を与えることができます。この安心感を助けるために、私は実験と組み合わせてコードカバレッジツールを使用して、すべてのケースを実行していることを確認します。
非常に簡単な例として、.NETFrameworkのリストソートの速度について健全性チェックを実行したいとします。次のように記述してから、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);
于 2008-09-05T18:33:32.480 に答える
5
メモリ リソースが限られている場合は、スペースの複雑さも考慮に入れることを忘れないでください。したがって、たとえば、基本的には、アルゴリズムによって使用されるスペースの量がコード内の要因に依存しないことを示す方法である、一定のスペースアルゴリズムが必要な人がいると聞くかもしれません。
複雑さは、何かが呼び出される回数、ループが実行される頻度、メモリが割り当てられる頻度などから生じる場合があります。これは、この質問に答える別の部分です。
最後に、大きな O は、最悪の場合、最良の場合、および償却の場合に使用できます。一般に、アルゴリズムがどれほど悪いかを説明するために使用されるのは最悪の場合です。
于 2008-10-14T20:16:38.760 に答える
4
素晴らしい質問です！
免責事項：この回答には虚偽の記述が含まれています。以下のコメントを参照してください。
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 があることを意味します。関数 f の c と k の値は固定である必要があり、n に依存してはなりません。
では、「最良のケース」と「最悪のケース」の複雑さとは何を意味するのでしょうか?
これは、おそらく例によって最も明確に説明されています。たとえば、並べ替えられた配列内の数値を見つけるために線形検索を使用している場合、最悪のケースは、配列内の項目と同じ数のステップが必要になるため、配列の最後の要素を検索することにした場合です。最良のケースは、最初のチェックの後に完了するため、最初の要素を検索するときです。
これらすべての形容詞の大文字と小文字の複雑さの要点は、特定の変数のサイズに関して、仮想プログラムが完了するまで実行される時間をグラフ化する方法を探しているということです。ただし、多くのアルゴリズムでは、特定のサイズの入力に対して単一の時間はないと主張できます。これは関数の基本的な要件と矛盾することに注意してください。どの入力も複数の出力を持つべきではありません。そのため、アルゴリズムの複雑さを表す複数の関数を考え出しました。サイズ n の配列の検索には、配列で探しているものと n に比例して依存するものに応じてさまざまな時間がかかる場合がありますが、最良の場合、平均の場合を使用してアルゴリズムの有益な説明を作成できます。 、最悪のクラス。
申し訳ありませんが、これは非常に下手に書かれており、多くの技術情報が不足しています。しかし、うまくいけば、時間の複雑さのクラスを考えやすくなるでしょう。これらに慣れると、プログラムを解析して、配列のサイズに依存する for ループなどを探し、データ構造に基づいて推論することで、どのような入力が些細なケースになるか、どのような入力が生じるかを簡単に調べることができます。最悪の場合。
于 2016-08-20T04:57:30.437 に答える
4
見落とされがちなのは、アルゴリズムの予想される動作です。アルゴリズムの Big-O を変更するわけではありませんが、「時期尚早の最適化...」というステートメントに関連しています。
アルゴリズムの予想される動作は、非常に馬鹿げたものですが、表示される可能性が最も高いデータに対してアルゴリズムがどれだけ速く動作すると期待できるかです。
たとえば、リスト内の値を検索している場合、それは O(n) ですが、表示されるほとんどのリストが前もって値を持っていることがわかっている場合、アルゴリズムの典型的な動作はより高速です。
本当にそれを突き止めるには、「入力スペース」の確率分布を記述できる必要があります (リストをソートする必要がある場合、そのリストが既にソートされる頻度はどれくらいですか? 完全に逆になる頻度はどれくらいですか? どのように多くの場合、ほとんどがソートされていますか?) それを知っていることは常に実現可能ではありませんが、知っている場合もあります。
于 2009-03-10T14:30:13.263 に答える
2
コード A の場合、外側のループがn+1時間実行されます。「1」時間は、i がまだ要件を満たしているかどうかをチェックするプロセスを意味します。そして、内側のループはn何回も実行されn-2ます....したがって、0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).
コード B の場合、内側のループは介入して foo() を実行しませんが、内側のループは、外側のループの実行時間 (O(n)) に応じて n 回実行されます。
于 2011-01-31T20:07:35.107 に答える