8歳児向けのBig-O?[重複]

Question

この質問にはすでに答えがあります:

• 「Big O」表記を英語でわかりやすく説明すると何ですか？ 39 件の回答

これが私のコードにとって何を意味するかについてさらに質問しています。概念は数学的には理解していますが、概念的に何を意味するのかを理解するのに苦労しています。たとえば、データ構造に対して O(1) 操作を実行する場合、アイテムの数が増えるため、実行する必要がある操作の数は増加しないことがわかります。O(n) 操作は、各要素に対して一連の操作を実行することを意味します。誰かここの空白を埋めてくれませんか？

• O(n^2) 演算は正確には何を行うのでしょうか?
• そして、操作が O(n log(n)) である場合、それは一体何を意味するのでしょうか?
• そして、O(x!) を書くために誰かがクラックを吸わなければならないのでしょうか?

Answer 1

それについての 1 つの考え方は次のとおりです。

O(N^2) は、すべての要素について、他のすべての要素に対して比較などの処理を行っていることを意味します。バブルソートはその一例です。

O(N log N) は、すべての要素について、要素の log N だけを調べる必要があることを実行していることを意味します。これは通常、効率的な選択を可能にする要素について何かを知っているためです。最も効率的なソートは、マージ ソートなどの例です。

O(N!) は、N 要素の考えられるすべての順列に対して何らかの処理を行うことを意味します。巡回セールスマンはその一例で、N! が存在します。ノードを訪問する方法があり、強引な解決策は、考えられるすべての置換の総コストを調べて最適な置換を見つけることです。

Answer 2

Big-O 記法がコードにとって意味する大きなことは、コードが処理する「もの」の量が 2 倍になったときにコードがどのようにスケールされるかということです。具体的な例を次に示します。

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(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 倍速くなります。その場合、明らかに最速のアルゴリズムを選択することが重要です。数百万行のデータベースにアクセスすると、クエリを 0.2 秒で実行する場合と、数時間かかる場合の違いが生じます。

もう 1 つ考慮すべき点は、不適切なアルゴリズムはムーアの法則では解決できないことの 1 つであるということです。たとえば、O(n^3) の科学計算があり、1 日に 100 件の処理ができる場合、プロセッサの速度を 2 倍にしても、1 日に得られる処理量は 125 件にすぎません。ただし、その計算を O(n^2) にすると、1 日に 1,000 件のことを行うことになります。

説明:実際、Big-O は、同じ特定のサイズ ポイントでの異なるアルゴリズムのパフォーマンスの比較については何も述べておらず、むしろ、異なるサイズ ポイントでの同じアルゴリズムのパフォーマンスの比較について述べています。

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

Answer 3

それを視覚化すると役立つかもしれません。

また、 LogY/LogX 機能をスケールする n^1/2, 、n、n² 全部似てる 直線, 、オンの間 LogY/X 規模 2ⁿ, 、eⁿ, 10ⁿ 直線であり、 ん！ 線形です（次のようになります） nログn).

Answer 4

これは数学的すぎるかもしれませんが、これが私の試みです。（私 午前 数学者です。）

何かがO(f(n))、それでは実行時間です n 要素は次と等しくなります あ f(n) + B (たとえば、クロック サイクルまたは CPU 動作で測定されます)。これらの定数もあることを理解することが重要です あ そして B, 、特定の実装から生じます。 B は基本的に操作の「一定のオーバーヘッド」を表します。たとえば、コレクションのサイズに依存しない前処理などです。 あ 実際のアイテム処理アルゴリズムの速度を表します。

ただし、重要なのは、ビッグ O 記法を使用して理解することです。 何かがどの程度うまくスケールするか. 。したがって、これらの定数は実際には重要ではありません。アイテム数を 10 個から 10,000 個にスケールする方法を見つけようとしている場合、一定のオーバーヘッドを誰が気にするでしょうか。 B?同様に、他の懸念事項 (以下を参照) は、乗算定数の重みを確実に上回ります。 あ.

それで、本当の取引は f(n）。もし f 全く成長しない n, 、例えば f(n) = 1 の場合、驚異的に拡張できます -- 実行時間は常にわずかになります。 あ + B. 。もし f と直線的に成長します n, 、つまり f(n) = n, を実行すると、実行時間は予想される限り最高になります。ユーザーが 10 個の要素で 10 ns 待機している場合、10,000 個の要素で 10,000 ns 待機することになります (加法定数は無視します)。でも、もしそれがより速く成長するなら、 n², 、それでは困ってしまいます。コレクションが大きくなると、処理が非常に遅くなり始めます。 f(n) = n ログ（n) は適切な妥協案であり、通常は次のようになります。あなたの操作は線形スケーリングを行うほど単純ではありませんが、以前よりもはるかにうまくスケーリングできるように物事を削減することに成功しました。 f(n) = n².

実際に、ここにいくつかの良い例を示します。

• O(1):配列から要素を取得します。メモリ内のどこにあるかは正確にわかっているので、それを取りに行くだけです。コレクションにアイテムが 10 個あるか 10000 個あるかは関係ありません。まだインデックス (たとえば) 3 にあるので、メモリ内の位置 3 にジャンプするだけです。
• お(n):リンクされたリストから要素を取得します。ここ、 あ = 0.5。平均すると、探している要素を見つけるまでにリンク リストの 1/2 を参照する必要があるためです。
• お(n²):さまざまな「愚かな」並べ替えアルゴリズム。一般に、彼らの戦略には各要素 (n）、他のすべての要素を確認します（つまり、別の要素も確認します） n, 、与える n²)、適切な場所に位置を決めます。
• お(n ログ（n)):さまざまな「スマート」ソートアルゴリズム。たとえば、10 個の要素のうち 10 個の要素だけを見ればよいことがわかりました。¹⁰- 相対的に自分自身をインテリジェントに分類するための要素コレクション みんな 他はコレクションにあります。他のみんなもそうだから また 10 個の要素を調べると、ソートされたリストを作成するのに十分なように、出現した動作が適切に調整されます。
• お(n!):(に比例する) ものがあるため、「すべてを試す」アルゴリズム n！可能な組み合わせ n 特定の問題を解決できる可能性のある要素。したがって、そのようなすべての組み合わせをループして試し、成功するたびに停止します。

Answer 5

don.neufeld の答えは非常に優れていますが、おそらく 2 つの部分に分けて説明します。まず、ほとんどのアルゴリズムが該当する O() の大まかな階層があります。次に、それらのそれぞれを見て、どのようなスケッチを思いつくことができます。 典型的な 当時のアルゴリズムは複雑です。

実用的な目的で、重要と思われる唯一の O() は次のとおりです。

• O(1) 「一定時間」 - 必要な時間は入力のサイズに依存しません。大まかなカテゴリとして、ハッシュ ルックアップや Union-Find などのアルゴリズムをここに含めます (実際にはどちらも O(1) ではありません)。
• O(log(n)) 「対数」 - 入力が大きくなると速度は遅くなりますが、入力がかなり大きくなると、心配するほど変化しなくなります。ランタイムが適度なサイズのデータ​​で問題がない場合は、必要なだけ追加データをランタイムに詰め込んでも問題はありません。
• O(n) 「線形」 - 入力が多いほど、均等なトレードオフで時間がかかります。入力サイズが 3 倍になると、時間もおよそ 3 倍かかります。
• O(n log(n)) 「二次方程式よりも優れている」 - 入力サイズの増加は苦痛ですが、それでも管理可能です。アルゴリズムはおそらくまともですが、根本的な問題が線形時間で解決できる問題よりも難しい (入力データに関して決定が局所的ではない) というだけです。入力サイズがそこまで増加している場合は、アーキテクチャを変更せずに (たとえば、夜間のバッチ計算に移行したり、フレームごとに処理を行わなかったりすることで) 必ずしも 2 倍のサイズを処理できるとは考えないでください。ただし、入力サイズが少し増加しても問題ありません。ただ複数に注意してください。
• O(n^2) "二次" - 実際には入力の特定のサイズまでしか機能しないため、どのくらい大きくなる可能性があるかに注意してください。また、あなたのアルゴリズムは最悪かもしれません。必要なものを提供する O(n log(n)) アルゴリズムがあるかどうか、よく考えてください。ここに着いたら、私たちに与えられた素晴らしいハードウェアにとても感謝してください。少し前までは、あなたがやろうとしていることは、実際的な目的では不可能だったでしょう。
• O(n^3) 「立方体」 - 定性的には O(n^2) とそれほど変わりません。同じコメントが当てはまりますが、さらに当てはまります。より賢いアルゴリズムにより、この時間をより小さな値、たとえば O(n^2 log(n)) や O(n^2.8...) まで短縮できる可能性は十分にありますが、それでも、苦労する価値はないだろう。(実際の入力サイズにはすでに制限があるため、より賢いアルゴリズムに必要な定数係数によって、実際のケースではその利点が無効になる可能性があります。また、思考も遅いです。コンピュータにそれを実行させると、全体的な時間を節約できる可能性があります。)
• O(2^n) 「指数関数的」 - 問題は根本的に計算が難しいか、あなたが馬鹿であるかのどちらかです。これらの問題には、独特の特徴があります。入力サイズは、かなり具体的なハードリミットで制限されています。自分がその制限に当てはまるかどうかはすぐにわかります。

以上です。これらの間に適合する (または O(2^n) より大きい) 可能性は他にもたくさんありますが、実際にはそれらは頻繁に発生するものではなく、これらのいずれかと定性的に大きな違いはありません。三次アルゴリズムはすでに少々無理があります。私がそれらを含めたのは、言及する価値があるほど頻繁に遭遇したからです (行列の乗算など)。

これらのクラスのアルゴリズムでは実際に何が起こっているのでしょうか?そうですね、良いスタートを切れたと思いますが、これらの特徴に当てはまらない例はたくさんあります。しかし、上記の場合、通常は次のようになると思います。

• O(1) - 入力データの固定サイズのチャンクだけをほとんど見ていて、まったく見ていない可能性があります。例：ソートされたリストの最大値。
  • または、入力サイズが制限されています。例：2 つの数字の加算。(N 個の数の加算は線形時間であることに注意してください。)
• O(log n) - 入力の各要素は、入力の残りの大部分を無視するのに十分な情報を示します。例：二分探索で配列要素を調べると、その値は、配列の「半分」を何も調べずに無視できることを示します。または同様に、注目する要素によって、残りの入力の一部の概要が十分に得られるため、それを参照する必要はありません。
  • ただし、半分について特別なことは何もありません。各ステップで入力の 10% しか無視できないとしても、それは対数的です。
• O(n) - 入力要素ごとに一定量の作業を実行します。(ただし、以下を参照してください。)
• O(n log(n)) - いくつかのバリエーションがあります。
  • 入力を 2 つの山に分割し (直線時間以内に)、各山で問題を個別に解決し、2 つの山を組み合わせて最終的な解決策を形成できます。2 つの杭の独立性が重要です。例：古典的な再帰的マージソート。
  • データを線形時間で通過するたびに、解の半分まで到達します。例：各分割ステップでの最終的なソート位置までの各要素の最大距離という観点から考えると、クイックソートになります (もちろん、ピボットの選択が縮退しているため、実際には O(n^2) であることはわかっています。しかし、実際的に言えば、これは私の考えでは O(n log(n)) のカテゴリに分類されます。)
• O(n^2) - 入力要素のすべてのペアを確認する必要があります。
  • あるいは、実際にはそうではありませんが、そう思っていて、間違ったアルゴリズムを使用していることもあります。
• O(n^3) - うーん...私はこれらを明確に特徴づけることができません。おそらく次のいずれかです。
  • 行列を乗算している
  • すべての入力のペアを確認していますが、実行する操作ではすべての入力を再度確認する必要があります
  • 入力のグラフ構造全体が関連している
• O(2^n) - 入力の可能なすべてのサブセットを考慮する必要があります。

これらはどれも厳密なものではありません。特に線形時間アルゴリズム (O(n)) ではありません。すべての入力を確認し、次にその半分を確認し、次にその半分を確認するなど、いくつかの例が思いつきます。またはその逆 -- 入力のペアをまとめてから、出力を再帰します。各入力を一度ずつ確認するわけではないため、これらは上記の説明には当てはまりませんが、それでも線形時間で出力されます。それでも、99.2% の確率で、線形時間は各入力を 1 回調べることを意味します。

Answer 6

これらの多くは、カードをシャッフルするなど、プログラミング以外のものを使って簡単に実証できます。

デッキ全体を調べてスペードのエースを見つけ、次にデッキ全体を調べてスペードの 2 を見つける、というようにカードのデッキを並べ替える場合、デッキがすでに逆方向に並べ替えられている場合、最悪の場合は n^2 になります。52 枚のカードすべてを 52 回見たことになります。

一般に、本当に悪いアルゴリズムは必ずしも意図的であるわけではなく、同じセットに対して線形的に繰り返す別のメソッド内で線形なメソッドを呼び出すなど、他のものの誤用であることが一般的です。

Answer 7

OK、ここには非常に良い答えがいくつかありますが、ほとんどすべてが同じ間違いを犯しているようで、それは一般的な使用法に浸透しています。

非公式には、スケーリング係数まで、n0 より大きいすべての n について g(n) が次の場合、 f(n) = O( g(n) ) と書きます。 より大きな f(n)よりも。つまり、f(n) 早く成長しない よりも、または 上から境界がある による、g(n)。これは、f(n) が g(n) よりも悪くならないことが保証されているという事実を除いて、f(n) がどれだけ速く増加するかについては何も示しません。

具体的な例:n = O( 2^n )。n の増加速度は 2^n よりもはるかに遅いことは誰もが知っているため、n は指数関数によって制限されていると言えます。n と 2^n の間にはかなりのスペースがあるため、それほど大きな値ではありません。 きつい バインドされていますが、それでも正当なバインドです。

なぜ私たち (コンピューター科学者) は正確ではなく境界を使用するのでしょうか?なぜなら、a) 限界は多くの場合証明が容易であり、b) アルゴリズムの特性を表現するための省略表現が得られるからです。私の新しいアルゴリズムが O(n.log n) であると言う場合、それは最悪の場合、その実行時間が n 個の入力に対する n.log n によって上から制限されることを意味します (ただし、n が十分に大きい場合は、以下の私のコメントを参照してください)最悪の場合を意味するわけではないかもしれません）。

代わりに、関数が他の関数とまったく同じ速度で成長すると言いたい場合は、次のようにします。 シータ その点を強調するために (マークダウンでは f(n) の heta を意味するために 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 を使用するアルゴリズムよりも悪くはなりません。しかし、時には、実行時間について話したいことがあります。 平均 そしてさらに 最高 ケース。

いつものように Vanilla クイックソートが良い例です。最悪の場合は 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) であるため、要素のペアごとに 1 回、個々の要素ごとに 100 回アクセスする必要がある可能性があります。O( ) 表記の背後にある考え方は、n^2 が 100n よりはるかに大きくなり、実行時間に対する 100n の影響さえ気付かないため、n が十分に大きい場合、これはまったく問題にならないということです。ただし、定数係数などが実際に大きな違いを生むような「十分に小さい」 n を扱うことがよくあります。

たとえば、クイックソート (平均コスト T(n.log n)) とヒープソート (平均コスト T(n.log n)) はどちらも同じ平均コストの並べ替えアルゴリズムですが、通常、クイックソートはヒープソートよりもはるかに高速です。これは、ヒープソートがクイックソートよりも要素ごとに多くの比較を行うためです。

これは、O( ) 表記が役に立たないということではなく、単に不正確であるだけです。これは、小さな n に対して使用するには非常に鈍いツールです。

(この論文の最後の注意点として、O( ) 表記は関数の成長を表すだけであることを覚えておいてください。それは必ずしも時間である必要はなく、メモリ、分散システムで交換されるメッセージ、または必要な CPU の数である可能性があります。並列アルゴリズム。)

Answer 8

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!) は、うーん、簡単なことを思いつくのに疲れているようです。
しかし、一般的なポイントは理解できたと思いますか?

Answer 9

技術者ではない友人に私がそれを説明する方法は次のとおりです。

複数桁の加算を考えてみましょう。古き良き、紙と鉛筆を使った追加です。7、8歳のときに習ったやつ。2 つの 3 桁または 4 桁の数字が与えられると、それらの合計をかなり簡単に見つけることができます。

100 桁の数字を 2 つ与えて、それらの合計が何になるかを尋ねたら、たとえ紙と鉛筆を使わなければならなかったとしても、それを計算するのは非常に簡単です。頭の良い子供なら、ほんの数分でこのような足し算を行うことができます。これに必要な操作は約 100 回だけです。

次に、複数桁の乗算を考えてみましょう。あなたはおそらく8歳か9歳頃にそれを学びました。あなたは（できれば）その背後にある仕組みを学ぶために、繰り返しの訓練をたくさん行いました。

さて、私が同じ 2 つの 100 桁の数字を渡して、それらを掛け合わせるように指示したと想像してください。これはかなりの量になりますが、 多くの より困難な作業、実行するには何時間もかかるもの、そして間違いなく実行する可能性は低いものです。その理由は、(このバージョンの) 乗算が O(n^2) であるためです。下の数値の各桁を上の数値の各桁で乗算する必要があり、合計で約 n^2 の演算が必要になります。100桁の数字の場合、10,000回の掛け算になります。

Answer 10

いいえ、O(n) アルゴリズムは、各要素に対して操作を実行することを意味するものではありません。Big-O 表記法を使用すると、実際のマシンとは独立してアルゴリズムの「速度」について話すことができます。

O(n) は、入力が増加するにつれてアルゴリズムにかかる時間が直線的に増加することを意味します。O(n^2) は、アルゴリズムにかかる時間が入力の 2 乗に応じて増加することを意味します。などなど。

Answer 11

私が考えるに、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 倍になったとしても、暗号化を解読するのに 100 年かかることを保証するには、あと何ビット使用する必要がありますか? 1年だけじゃないの？）

関係者に影響を与える場合、一部の境界には奇妙な表現が含まれる可能性があります。Knuth の Art of Computer Programming のどこかで、いくつかのアルゴリズムについて O(N log(N) log(log(N))) のような記述を見たことがあります。（頭の中でどれが思い浮かんだのか思い出せません）

Answer 12

何らかの理由でまだ触れられていないことが 1 つあります。

O(2^n) や O(n^3) などの厄介な値を含むアルゴリズムを目にした場合、それは多くの場合、許容可能なパフォーマンスを得るために、問題に対する不完全な答えを受け入れる必要があることを意味します。

最適化問題を扱う場合、このように爆発する正解はよくあります。妥当な期間内にほぼ正解に近い答えが得られることは、機械が朽ち果ててからずっと経ってから得られる正解よりも優れています。

チェスを考えてみましょう。正しい解決策が何であると考えられるのか正確にはわかりませんが、おそらく O(n^50) かそれ以上の値になるでしょう。理論的には、どんなコンピューターでも実際に正しい答えを計算することは不可能です。宇宙のすべての粒子を計算要素として使用し、宇宙の存続期間中可能な最小限の時間で演算を実行したとしても、依然として多くのゼロが残っています。 。（量子コンピュータで解決できるかどうかは別問題です。）

Answer 13

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) に対して一種の「速度制限」を課します。最終的にはそれを通過し、永久に取り残されるからです。

これは正確には次の定義ではありません ビッグオー表記, また、これは、f(x) が定数 C について C*g(x) より大きくなければならないだけであるとも述べています (これは、g(x) に次の値を掛けても、競争に勝つのに貢献できないことを言い換えているだけです)定数係数 - f(x) は最終的に常に勝ちます)。正式な定義では絶対値も使用されます。しかし、なんとか直感的に理解できたと思います。

Answer 14

• そして、O(x!) を書くために誰かがクラックを吸わなければならないのでしょうか?

いいえ、Prolog を使用してください。Prolog でソート アルゴリズムを記述し、各要素が前の要素より大きくなければならないとだけ記述し、バックトラッキングにソートを任せると、O(x!) になります。「順列ソート」とも呼ばれます。

Answer 15

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 個のパーティションに到達するまで (これは縮退です)。n を半分に分割して 1 にする回数は約 log n で、各ステップは O(n) であるため、再帰的分割統治は O(n log n) です。マージソートは逆の方法で構築され、1 つの項目の n 回の再結合で始まり、n 個の項目の 1 回の再結合で終了します。ここで、2 つのソートされたリストの再結合は O(n) です。

O(n!) アルゴリズムを作成するには、他に選択肢がない限り、そうする必要があります。上記の巡回セールスマン問題もそのような問題の 1 つであると考えられています。

Answer 16

ほとんどのジョン・ベントリーの本 (例: プログラミングパール）そのようなことを非常に実用的な方法でカバーしています。 この話 彼が提供したクイックソートの分析の 1 つが含まれています。

この質問と完全に関係があるわけではありませんが、Knuth 氏は次のことを考え出しました。 興味深いアイデア:高校の微積分の授業で Big-O 記法を教えていますが、この考えはかなり奇抜だと思います。

Answer 17

レゴ ブロック (n) を垂直に積み上げ、その上をジャンプすることを考えてください。

O(1) は、各ステップで何もしないことを意味します。高さはそのままです。

O(n) は、各ステップで c 個のブロックをスタックすることを意味します (c1 は定数)。

O(n^2) は、各ステップで c2 x n ブロックをスタックすることを意味します。c2 は定数、n はスタックされたブロックの数です。

O(nlogn) は、各ステップで c3 x n x log n ブロックをスタックすることを意味します。ここで、c3 は定数、n はスタックされたブロックの数です。

Answer 18

O(n log n) を理解するには、log n が n の対数底 2 を意味することを思い出してください。次に、各部分を見てみましょう。

O(n) は、多かれ少なかれ、セット内の各項目を操作するときの値です。

O(log n) は、項目数を取得するために 2 を累乗した指数と演算数が同じ場合です。たとえば、二分探索では、セットを半分の対数 n 回に分割する必要があります。

O(n log n) は組み合わせです。セット内の各項目に対して二分探索に沿った処理を行っています。効率的な並べ替えは、多くの場合、アイテムごとに 1 つのループを実行し、各ループで適切な検索を実行して、問題のアイテムまたはグループを配置する適切な場所を見つけることによって機能します。したがって、n * log n となります。

Answer 19

私の上記の投稿に対するいくつかのコメントに返信します。

ドメニク - 私はこのサイトにいます、そして私は気にしています。それは衒学的ではなく、私たちプログラマは通常、精度を気にするからです。ここで一部の人が行っているスタイルで O( ) 表記を誤って使用すると、意味がなくなってしまいます。ここで使用されている規則では、何かには O( n^2 ) として n^2 単位の時間がかかると言ったほうがよいでしょう。O( ) を使用しても何も追加されません。私が話しているのは、一般的な使用法と数学的精度との間の単なる小さな差異ではなく、それが意味のあるものであるかどうかの違いです。

私はこれらの用語を正確に使用する、非常に多くの優秀なプログラマーを知っています。「ああ、私たちはプログラマーだから気にしない」と言うと、企業全体のコストが下がります。

一つずつ - そうですね、あなたの意見はわかりますが、そうではありません。これは、O( ) の定義のような、任意に大きい n に対する O(1) ではありません。これは、O( ) が有界 n に対して適用できる範囲が限られていることを示しています。実際には、その数の限界ではなく、実行されるステップ数について話したいと思います。

Answer 20

8 年前の log(n) は、長さ n の丸太をサイズ n=1 に下げるために 2 つに切る必要がある回数を意味すると教えてください。:p

o（n log n）は通常、o（n^2）の並べ替えです。通常、要素のすべてのペアを比較しています

Answer 21

一定規模の問題を解決できるコンピューターがあるとします。ここで、パフォーマンスを数倍にできると想像してください。2倍になるごとに、どれくらい大きな問題を解決できるでしょうか?

2 倍のサイズの問題を解決できれば、O(n) になります。

1 ではない乗数がある場合、それはある種の多項式の複雑さです。たとえば、2 倍になるたびに問題のサイズを約 40% 増やすことができる場合、それは O(n^2) となり、約 30% は O(n^3) になります。

問題の規模がさらに大きくなると、それは指数関数的かさらに悪化します。たとえば、各 2 倍が 1 つ大きな問題を解決できることを意味する場合、それは O(2^n) です。(これが、適切なサイズの鍵を使用すると、暗号鍵の総当たり攻撃が事実上不可能になる理由です。128 ビット鍵は 64 ビット鍵の約 16 京倍の処理を必要とします。)

Answer 22

ウサギとカメの寓話（カメとウサギ）を覚えていますか？

長期的には亀が勝ちますが、短期的にはウサギが勝ちます。

それは O(logN) (亀) とO(N)（ハレ）。

2 つのメソッドの big-O が異なる場合、どちらかが勝つ N のレベルが存在しますが、big-O はその N がどれほど大きいかについては何も言いません。

Answer 23

質問に対して誠実であり続けるために、私は 8 歳の子供に答えるような態度で質問に答えます

アイスクリームの売り手が、さまざまな形のアイスクリーム ( N 個とする) を整然と並べて準備するとします。真ん中にあるアイスクリームが食べたいです

ケース 1 :- アイスクリームを食べることができます。アイスクリームをすべて食べた場合にのみ、準備したアイスクリームの半分を食べなければなりません（入力）。 （n）

ケース 2 :- 真ん中のアイスクリームを直接食べることができます

解はO(1)になります

ケース 3 :アイスクリームを食べるよりも小さなアイスクリームを食べた場合にのみ、アイスクリームを食べることができ、アイスクリームを食べるたびに、他の子供（新しい子供）がすべてのアイスクリームを食べることができます。 n .......（n/2）回数はo（n2）になります

Answer 24

log(n) は対数増加を意味します。例としては、分割統治アルゴリズムが挙げられます。配列内にソートされた数値が 1000 個ある場合 (例:3、10、34、244、1203 ...) リスト内の数値を検索する (その位置を見つける) 場合は、インデックス 500 の数値の値を確認することから始めることができます。求める値よりも低い場合は、750 にジャンプします。それが求める値より高い場合は、250 にジャンプします。次に、値 (およびキー) が見つかるまでこのプロセスを繰り返します。検索スペースの半分をジャンプするたびに、数値 3004 が数値 5000 を超えることができないことがわかっているため、他の多くの値のテストを省略できます (これはソートされたリストであることを思い出してください)。

n log(n) は n * log(n) を意味します。

Answer 25

専門用語や数学的概念はさておき、実際に8歳の男の子の説明を書いてみます。

正確にはどうなるかというと、 O(n^2) 操作は行いますか？

あなたがパーティーに参加していて、 n あなたを含むパーティーの人々。人々はおそらくある時点で誰と握手したか忘れてしまうだろうとして、全員が他の全員と握手するにはどれだけの握手が必要か。

注記：これはシンプレックスに近似し、 n(n-1) に十分近い n^2.

そして、操作が次のような場合、それは一体何を意味するのでしょうか？ O(n log(n))?

あなたのお気に入りのチームが勝利し、列に並んでいます。 n チームの選手たち。各プレイヤーと複数回ハンドシェイクする場合、各プレイヤーとハンドシェイクするのに必要なハンシェイクの回数、回数、プレイヤーの数は何桁になるか 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