これが私のコードにとって何を意味するかについてもっと尋ねています。私は概念を数学的に理解していますが、それらが概念的に何を意味するのかを理解するのに苦労しています. たとえば、データ構造に対して O(1) 操作を実行する場合、項目が増えるため、実行する操作の数が増えないことは理解しています。また、O(n) 操作は、各要素に対して一連の操作を実行することを意味します。誰かここの空欄を埋めてくれませんか?
それについての1つの考え方は次のとおりです。
O(N^2) は、すべての要素について、比較など、他のすべての要素に対して何かを行っていることを意味します。バブルソートはその一例です。
O(N log N) は、すべての要素について、log N の要素を確認するだけでよいことを行っていることを意味します。これは通常、効率的な選択を可能にする要素についてある程度知っているためです。マージソートなど、最も効率的なソートはこの例です。
O(N!) は、N 要素のすべての可能な順列に対して何かを行うことを意味します。巡回セールスマンはこの例で、N! ノードを訪問する方法、およびブルートフォースソリューションは、可能なすべての順列の総コストを調べて、最適なものを見つけることです.
コードにとって Big-O 表記が意味する重要な点は、操作対象の「もの」の量を 2 倍にした場合に、どのようにスケールするかということです。具体的な例を次に示します。
ビッグオー | ビッグオー | 10 個の計算 | 100 個の計算 -------------------------------------------------- -------------------- O(1) | 1 | 1 O(ログ(n)) | 3 | 7 O(n) | 10 | 100 O(n log(n)) | 30 | 700 O(n^2) | 100 | 10000
したがって、O(n log(n)) であるクイックソートと O(n^2) であるバブル ソートを使用します。10 個のソートを行う場合、クイックソートはバブルソートよりも 3 倍高速です。しかし、100 個を並べ替えると、14 倍速くなります。その場合、明らかに最速のアルゴリズムを選択することが重要です。100 万行のデータベースに到達すると、0.2 秒で実行されるクエリと数時間かかるクエリの違いを意味する可能性があります。
考慮すべきもう 1 つのことは、悪いアルゴリズムは、ムーアの法則が役に立たないことの 1 つです。たとえば、O(n^3) の科学計算があり、1 日に 100 回計算できる場合、プロセッサ速度を 2 倍にしても、1 日で 125 回しか計算できません。ただし、その計算を O(n^2) にすると、1 日に 1000 のことを行うことになります。
明確化: 実際、Big-O は、同じ特定のサイズ ポイントでの異なるアルゴリズムの比較パフォーマンスについては何も述べていませんが、異なるサイズ ポイントでの同じアルゴリズムの比較パフォーマンスについては述べていません。
計算 計算 計算 ビッグオー | ビッグオー | 10のこと | 100のこと | 1000もの -------------------------------------------------- -------------------- O(1) | 1 | 1 | 1 O(ログ(n)) | 1 | 3 | 7 O(n) | 1 | 10 | 100 O(n log(n)) | 1 | 33 | 664 O(n^2) | 1 | 100 | 10000
視覚化すると便利な場合があります。
また、 LogY/LogXスケールでは関数n 1/2、n、n 2 はすべて直線のように見えますが、LogY/Xスケールでは2 n、e n、10 n は直線であり、n! 線形です（ n log nのように見えます）。
これは数学的すぎるかもしれませんが、これが私の試みです。(私は数学者です。)
何かが O( f ( n )) である場合、 n要素での実行時間はA f ( n ) + B (たとえば、クロックサイクルまたは CPU 操作で測定) に等しくなります。特定の実装に起因するこれらの定数AおよびBもあるということを理解することが重要です。Bは基本的に操作の「一定のオーバーヘッド」を表します。たとえば、コレクションのサイズに依存しない前処理などです。Aは、実際のアイテム処理アルゴリズムの速度を表します。
ただし、重要なのは、大きな O 表記を使用して、何かがどれだけうまくスケーリングされるかを把握することです。したがって、これらの定数は実際には重要ではありません。10 から 10000 アイテムにスケーリングする方法を理解しようとしている場合、一定のオーバーヘッドBを誰が気にしますか? 同様に、他の懸念事項 (以下を参照) は、確実に乗法定数Aの重みを上回ります。
したがって、本当の取引はf ( n ) です。fがnでまったく増加しない場合、たとえばf ( n ) = 1 の場合、驚異的にスケーリングします---実行時間は常にA + Bになります。fがnに比例して増加する場合、つまりf ( n ) = nの場合、実行時間は期待できる限り最高にスケーリングされます。ユーザーが 10 要素に対して 10 ns 待機している場合、ユーザーは 10000 に対して 10000 ns 待機します。要素 (加法定数を無視)。しかし、 n 2のように、より速く成長する場合、その後、あなたは困っています。より大きなコレクションを取得すると、速度が大幅に低下し始めます。f ( n ) = n log( n ) は、通常は適切な妥協点です。線形スケーリングを行うほど単純な操作はできませんが、fよりもはるかに優れたスケーリングになるように物事を削減することができました( n ) = n 2 .
実際には、いくつかの良い例を次に示します。
これらの多くは、カードをシャッフルするなど、プログラミング以外の方法で簡単に実証できます。
デッキ全体を調べてスペードのエースを見つけ、次にデッキ全体を調べてスペードの 2 を見つけるというようにカードのデッキを並べ替えると、デッキが既に後方に並べ替えられている場合、最悪の場合 n^2 になります。52 枚のカードすべてを 52 回見ました。
一般に、本当に悪いアルゴリズムは必ずしも意図的なものではありません。通常、同じセットを線形に繰り返す他のメソッド内で線形のメソッドを呼び出すなど、他の何かの誤用です。
私はC＃で簡単なコード例を挙げて説明しようとしています。
にとってList<int> numbers = new List<int> {1,2,3,4,5,6,7,12,543,7};
O（1）は次のようになります
return numbers.First();
O（n）は次のようになります
int result = 0;
foreach (int num in numbers)
{
result += num;
}
return result;
O（n log（n））は次のようになります
int result = 0;
foreach (int num in numbers)
{
int index = numbers.length - 1;
while (index > 1)
{
// yeah, stupid, but couldn't come up with something more useful :-(
result += numbers[index];
index /= 2;
}
}
return result;
O（n 2）は次のようになります
int result = 0;
foreach (int outerNum in numbers)
{
foreach (int innerNum in numbers)
{
result += outerNum * innerNum;
}
}
return result;
O（n！）は、簡単なことを思いつくのに疲れているように見えます。
しかし、私はあなたが一般的なポイントを得ることを望みますか？
わかりました-ここにはいくつかの非常に良い答えがありますが、それらのほとんどすべてが同じ間違いを犯しているようで、一般的な使用法に浸透しています.
非公式に、f(n) = O( g(n) ) と書きます。スケーリング係数まで、n0 より大きいすべての n に対して、g(n) がf(n)より大きい場合です。つまり、f(n)は g(n)より速く成長しないか、g(n) によって上から制限されます。これは、f(n) が g(n) よりも悪くならないことが保証されているという事実を除けば、f(n) の成長速度については何も教えてくれません。
具体例: n = O( 2^n )。n の成長は 2^n よりもはるかに遅いことは誰もが知っているので、指数関数によって上で制限されていると言えます。n と 2^n の間には多くの余地があるため、厳密な境界ではありませんが、それでも正当な境界です。
なぜ私たち (コンピューター科学者) は正確ではなく境界を使用するのでしょうか? なぜなら、a) 境界はしばしば証明しやすく、b) アルゴリズムのプロパティを表現する簡単な方法を提供してくれるからです。私の新しいアルゴリズムが O(n.log n) であると言った場合、最悪の場合、実行時間は n 個の入力で n.log n によって上から制限されることを意味します (ただし、以下の私のコメントを参照してください)最悪の場合を意味しない場合があります）。
代わりに、関数が他の関数とまったく同じ速さで成長すると言いたい場合は、その点を示すためにthetaを使用します (マークダウンで f(n) の \Theta を意味するように T( f(n) ) と書きます) . T( g(n) ) は、g(n) によって上と下から制限されていることの省略形であり、ここでもスケーリング係数まで漸近的です。
つまり、f(n) = T( g(n) ) <=> f(n) = O(g(n)) および g(n) = O(f(n)) です。この例では、2^n != O(n) であるため、n != T( 2^n ) であることがわかります。
なぜこれについて心配するのですか？あなたの質問では、「誰かが O(x!) を書くためにクラックを吸わなければならないでしょうか?」と書いているからです。答えはノーです - 基本的にあなたが書くものはすべて階乗関数によって上から制限されるからです。クイックソートの実行時間は O(n!) です。厳密な制限ではありません。
ここにも別次元の繊細さがあります。通常、O( g(n) ) 表記を使用する場合、最悪の場合の入力について話しているため、複合ステートメントを作成しています。最悪の場合の実行時間では、g(n) を取るアルゴリズムよりも悪くはありません。 ) ステップ、再びモジュロ スケーリングと十分な大きさの n の場合。しかし、平均的な場合や最良の場合の実行時間について話したい場合もあります。
バニラのクイックソートは、いつものように、良い例です。最悪の場合は T( n^2 ) (実際には少なくとも n^2 ステップかかりますが、それ以上のステップは必要ありません) ですが、平均的なケースでは T(n.log n) です。ステップは n.log n に比例します。最良の場合は T(n.log n) でもありますが、たとえば、配列が既にソートされているかどうかを確認することで改善できます。この場合、最良の場合の実行時間は T( n ) になります。
これは、これらの境界の実際の実現に関するあなたの質問とどのように関連していますか? 残念ながら、O( ) 表記法は、実際の実装で処理しなければならない定数を隠してしまいます。したがって、たとえば T(n^2) 操作の場合、考えられるすべての要素のペアを訪問する必要があると言えますが、それらを何回訪問する必要があるかはわかりません (ただし、それは次の関数ではありません)。 n)。したがって、すべてのペアを 10 回または 10^10 回訪問する必要があり、T(n^2) ステートメントは区別しません。低次関数も隠されています.n^2 + 100n = T(n^2). O( ) 表記の背後にある考え方は、n が十分に大きい場合、n^2 が 100n よりもはるかに大きくなるため、これはまったく問題にならないということです。実行時間に対する 100n の影響に気付くことさえありません。しかし、私たちはしばしば「十分に小さい」 n を扱い、一定の要因などが実際の大きな違いを生むようにします。
たとえば、クイックソート (平均コスト T(n.log n)) とヒープソート (平均コスト T(n.log n)) はどちらも同じ平均コストのソート アルゴリズムですが、一般的にクイックソートはヒープソートよりもはるかに高速です。これは、ヒープソートがクイックソートよりも要素ごとにいくつかの比較を行うためです。
これは、O( ) 表記が役に立たないと言っているのではなく、単に不正確です。小さな n を扱うのは非常に鈍いツールです。
(この論文の最後の注意として、O( ) 表記は関数の成長を表すだけであることを思い出してください。時間である必要はありません。メモリ、分散システムで交換されるメッセージ、または関数に必要な CPU の数である可能性があります。並列アルゴリズム)
技術に詳しくない友人に私が説明する方法は次のとおりです。
複数桁の加算を検討してください。古き良き、鉛筆と紙の追加。7〜8歳のときに学んだ種類。2 つの 3 桁または 4 桁の数字が与えられた場合、これらの数字の合計はかなり簡単にわかります。
100 桁の数字を 2 つあげて、足し合わせるとどうなるかを尋ねた場合、たとえ紙と鉛筆を使わなければならないとしても、それを理解するのは非常に簡単です。頭の良い子供は、ほんの数分でそのような追加を行うことができます. これには、約 100 回の操作しか必要ありません。
ここで、複数桁の掛け算を考えてみましょう。あなたはおそらく8歳か9歳くらいでそれを学びました。あなたは (できれば) その背後にあるメカニズムを学ぶために、多くの反復的なドリルを行いました。
さて、同じ 100 桁の数を 2 つ与えて、それらを乗算するように指示したとします。これは、はるかに困難な作業であり、何時間もかかる作業であり、間違いなく行うことはまずありません。この理由は、(このバージョンの) 乗算が O(n^2) であるためです。下の数値の各桁に上の数値の各桁を掛ける必要があり、合計で約 n^2 の演算が残ります。100 桁の数字の場合、それは 10,000 の掛け算です。
いいえ、O(n) アルゴリズムは、各要素に対して操作を実行するという意味ではありません。Big-O 記法は、実際のマシンとは関係なく、アルゴリズムの「速度」について話す方法を提供します。
O(n) は、入力が増加するにつれて、アルゴリズムにかかる時間が直線的に増加することを意味します。O(n^2) は、アルゴリズムにかかる時間が入力の 2 乗に比例して大きくなることを意味します。などなど。
私の考えでは、N を選んだ邪悪な悪役 V によって引き起こされた問題を解決するタスクがあり、彼が N を増やしたときに問題を解決するのにどれくらいの時間がかかるかを見積もる必要があります。
O(1) -> N を増やしても、実際にはまったく違いはありません
O(log(N)) -> V が N を 2 倍にするたびに、タスクを完了するために余分な時間 T を費やさなければなりません。V は再び N を 2 倍にし、同じ金額を使います。
O(N) -> V が N を 2 倍にするたびに、2 倍の時間を費やします。
O(N^2) -> V が N を 2 倍にするたびに、4 倍の時間を費やします。（それは公平ではありません!!!）
O(N log(N)) -> V が N を 2 倍にするたびに、2 倍の時間と少し多くの時間を費やします。
これらはアルゴリズムの境界です。コンピューター科学者は、N の値が大きい場合にどれくらいの時間がかかるかを説明したいと考えています (これは、暗号で使用される数値を素因数分解するときに重要になります。コンピューターの速度が 10 倍になった場合、あと何ビットで処理できるかを説明します)。 1年だけでなく、暗号化を破るのに100年かかることを確認するために使用する必要がありますか?)
関係する人々に違いをもたらす場合、境界のいくつかは奇妙な表現を持つことができます. O(N log(N) log(log(N))) のようなものを、いくつかのアルゴリズムについて、Knuth の Art of Computer Programming のどこかで見たことがあります。(頭のてっぺんからどれが思い出せません)
何らかの理由でまだ触れられていないことが1つあります。
O（2 ^ n）やO（n ^ 3）などの厄介な値を持つアルゴリズムを見る場合、許容できるパフォーマンスを得るには、問題に対する不完全な答えを受け入れる必要があることを意味します。
このように爆発する正しい解決策は、最適化問題を扱うときに一般的です。妥当な時間枠で提供されるほぼ正解は、マシンが粉塵に崩壊したずっと後に提供される正解よりも優れています。
チェスについて考えてみましょう。正しい解決策が何であるかは正確にはわかりませんが、おそらくO（n ^ 50）またはさらに悪いものです。理論的には、どのコンピューターでも実際に正解を計算することは不可能です。たとえ、宇宙のすべての粒子を計算要素として使用して、宇宙の存続期間中、可能な限り最短の時間で操作を実行したとしても、まだ多くのゼロが残っています。 。（量子コンピューターがそれを解決できるかどうかは別の問題です。）
いいえ、Prolog を使用してください。各要素が前のものよりも大きくなければならないことを記述するだけで Prolog で並べ替えアルゴリズムを記述し、バックトラックに並べ替えを任せると、それは O(x!) になります。「順列ソート」とも呼ばれます。
Big-Oの背後にある「直感」
x が無限大に近づくにつれて、x をめぐる 2 つの関数 f(x) と g(x) の間の「競合」を想像してください。
ここで、ある時点 (ある x) から、一方の関数が常に他方よりも高い値を持っている場合、この関数を他方よりも「高速」と呼びましょう。
したがって、たとえば、x > 100 ごとに f(x) > g(x) である場合、f(x) は g(x) よりも「高速」です。
この場合、g(x) = O(f(x)) となります。f(x) は g(x) の一種の「速度制限」をもたらします。
これはbig-O 記法の正確な定義ではなく、f(x) は定数 C に対して C*g(x) よりも大きくなければならないことも示しています (これは、 g(x) に一定の係数を掛けることで競争に勝つことができます - f(x) は常に最後に勝ちます)。正式な定義でも絶対値が使用されます。しかし、私はそれを直感的にすることができたと思っています。
レゴ ブロック (n) を縦に積み上げて飛び越えるようなものだと考えてください。
O(1) は、各ステップで何もしないことを意味します。高さはそのままです。
O(n) は、各ステップで c 個のブロックをスタックすることを意味します。ここで、c1 は定数です。
O(n^2) は、各ステップで c2 xn ブロックをスタックすることを意味します。ここで、c2 は定数で、n はスタックされたブロックの数です。
O(nlogn) は、各ステップで、c3 xnx log n ブロックをスタックすることを意味します。ここで、c3 は定数で、n はスタックされたブロックの数です。
Don Neufeldの答えが好きですが、O（n log n）について何か追加できると思います。
単純な分割統治戦略を使用するアルゴリズムは、おそらく O(log n) になります。これの最も簡単な例は、ソートされたリストで何かを見つけることです。最初から始めてスキャンするわけではありません。真ん中に移動し、前後に移動するかどうかを決定し、最後に見た場所の途中までジャンプして、探しているアイテムが見つかるまでこれを繰り返します。
クイックソートまたはマージソートのアルゴリズムを見ると、どちらもソートするリストを半分に分割し、それぞれの半分を (同じアルゴリズムを使用して再帰的に) ソートし、2 つの半分を再結合するというアプローチを取っていることがわかります。この種の再帰的な分割統治戦略は O(n log n) になります。
よく考えてみると、クイックソートは n 個のアイテム全体で O(n) 分割アルゴリズムを実行し、次に n/2 個のアイテムで O(n) 分割アルゴリズムを 2 回実行し、次に n/4 個のアイテムで 4 回実行することがわかります。など... 1つのアイテムでn個のパーティションに到達するまで(これは縮退です)。1 になるまでに n を半分に分割する回数は約 log n で、各ステップは O(n) なので、再帰的な分割統治は O(n log n) です。Mergesort は逆に、1 項目の n 回の再結合から始まり、n 個の項目の 1 回の再結合で終了します。ここで、2 つのソートされたリストの再結合は O(n) です。
O(n!) アルゴリズムを書くためのクラックの喫煙に関しては、選択の余地がない限り、そうです。上記の巡回セールスマン問題は、そのような問題の 1 つと考えられています。
ほとんどの Jon Bentley の本 (例: Programming Pearls ) は、このようなことを非常に実用的な方法でカバーしています。彼が行ったこの講演には、そのようなクイックソートの分析が含まれています。
この質問に完全に関連するわけではありませんが、Knuth は興味深いアイデアを思いつきました: 高校の微積分のクラスで Big-O 記法を教えることです。
あるサイズの問題を解けるコンピュータがあるとします。ここで、パフォーマンスを数倍にできると想像してください。倍増するたびにどれだけ大きな問題を解決できるでしょうか?
サイズが 2 倍になる問題を解くことができれば、それは O(n) です。
1 でない乗数がある場合、それはある種の多項式の複雑さです。たとえば、2 倍にするたびに問題のサイズを約 40% 増やすことができる場合、それは O(n^2) であり、約 30% は O(n^3) になります。
問題のサイズに追加すると、指数関数的またはさらに悪化します。たとえば、2 倍になるたびに 1 大きい問題を解くことができる場合、それは O(2^n) です。(これが、適度なサイズの鍵では暗号鍵の総当たり攻撃が実質的に不可能になる理由です。128 ビットの鍵は、64 ビットの鍵の約 16 京倍の処理を必要とします。)
上記の投稿に対するいくつかのコメントに返信するだけです。
Domenic - 私はこのサイトにいて、気にかけています。衒学的なためではなく、プログラマーとして通常は精度を気にするためです。ここで何人かが行ったスタイルで O( ) 表記を誤って使用すると、意味がなくなります。ここで使用されている規則の下では、何かが O( n^2 ) のように n^2 単位の時間がかかると言った方がよいでしょう。O( ) を使用しても何も追加されません。私が話しているのは、一般的な使用法と数学的精度の間の小さな不一致ではなく、意味があるかどうかの違いです。
私は、これらの用語を正確に使用している非常に多くの優れたプログラマーを知っています。「ああ、私たちはプログラマーなので気にしない」と言うと、企業全体が安くなります。
onebyone - まあ、そうではありませんが、私はあなたの主張を理解しています. O( ) の定義のような、任意に大きな n の場合は O(1) ではありません。これは、O( ) が有界 n に対して適用可能性が限られていることを示しています。ここでは、その数の境界ではなく、実行されたステップ数について実際に話したいと思います。
O(n log n) を理解するには、log n が n の対数底 2 を意味することを思い出してください。次に、各部分を見てください。
O(n) は、多かれ少なかれ、セット内の各アイテムを操作する場合です。
O(log n) は、アイテムの数を取得するために、操作の数が 2 を累乗した指数と同じである場合です。たとえば、バイナリ検索では、セットを log n 回半分に分割する必要があります。
O(n log n) は組み合わせです。セット内の各アイテムに対してバイナリ検索の行に沿って何かを行っています。多くの場合、アイテムごとに 1 つのループを実行し、各ループで適切な検索を行って、問題のアイテムまたはグループを配置する適切な場所を見つけることによって、効率的な並べ替えが行われます。したがって、n * log n です。
8 年前の log(n) は、長さ n のログを 2 つに切り刻んで、サイズ n=1 になるまでの回数を意味することを教えてください:p
O(n log n) は通常、並べ替えです O(n^2) は通常、すべての要素のペアを比較します
log(n) は対数成長を意味します。例としては、分割統治アルゴリズムがあります。配列に 1000 個の並べ替えられた数値 (例: 3、10、34、244、1203 ...) があり、リスト内の数値を検索する (その位置を見つける) 場合は、インデックス 500 の番号。求めているものよりも小さい場合は、750 にジャンプします。求めるものよりも大きい場合は、250 にジャンプします。次に、値 (およびキー) が見つかるまでプロセスを繰り返します。検索スペースの半分をジャンプするたびに、3004 という数値が 5000 を超えてはならないことがわかっているため、他の多くの値をテストして除外することができます (これはソートされたリストであることを思い出してください)。
n log(n) は n * log(n) を意味します。
専門用語と数学的概念は別として、実際の 8 歳の男の子の説明を実際に書いてみます。
操作は正確に何を
O(n^2)しますか？
あなたがパーティーに参加していてn、そのパーティーにあなたを含む人がいる場合。ある時点で誰と握手をしたか忘れてしまう可能性があることを考えると、全員が他の全員と握手するのに必要な握手回数。
注: これn(n-1)は に十分近いシンプレックス降伏に近似しn^2ます。
そして、操作が である場合、それは一体どういう意味
O(n log(n))ですか?
お気に入りのチームが勝利し、列に並んでいてn、チームに選手がいます。1 人 1 人を複数回握手をすることを考えると、すべてのプレイヤーと握手をするのに何回の握手が必要か、何回、プレイヤーの数が何桁であるかn。
注: これにより が得られn * log n to the base 10ます。
そして、誰かがクラックを吸ってから書く必要があり
O(x!)ますか？
あなたは金持ちの子供で、ワードローブにはたくさんの布があります。x衣類の種類ごとに引き出しがあり、引き出しは隣同士にあり、最初の引き出しには 1 つのアイテムがあり、各引き出しには引き出しと同じ数の布があります。その左ともう 1 つ、つまり、1帽子、2かつら、..(x-1)ズボン、そしてxシャツのようなものがあります。各引き出しから 1 つのアイテムを使用して、いくつの方法でドレスアップできるでしょうか。
注: この例は、決定ツリー内のリーフの数を表してnumber of children = depthいます。1 * 2 * 3 * .. * x