「Big O」表記を英語でわかりやすく説明すると何ですか？

StackOverflow https://stackoverflow.com/questions/487258

質問

私はできるだけ正式な定義を少なくし、単純な数学を好みます。

役に立ちましたか？

解決

簡単な注意ですが、これはほぼ確実に混乱を招きます ビッグオー表記 (これは上限です)、シータ表記「Θ」(これは両側限界です)を使用します。私の経験では、これは実際、学術以外の場での議論によく見られる現象です。混乱を招いてしまったことをお詫び申し上げます。

Big O の複雑さは、次のグラフで視覚化できます。

Big O Analysis

Big-O 表記法について私が与えることができる最も簡単な定義は次のとおりです。

Big-O 表記は、アルゴリズムの複雑さを相対的に表現したものです。

この文には、意図的に選ばれた重要な単語がいくつかあります。

  • 相対的： リンゴとリンゴを比較することしかできません。算術乗算を行うアルゴリズムと、整数のリストを並べ替えるアルゴリズムを比較することはできません。しかし、算術演算 (1 つは乗算、1 つは加算) を実行する 2 つのアルゴリズムを比較すると、意味のあることが分かります。
  • 表現： Big-O (最も単純な形式) は、アルゴリズム間の比較を単一の変数に減らします。その変数は観察または仮定に基づいて選択されます。たとえば、並べ替えアルゴリズムは通常、比較操作 (2 つのノードを比較して相対的な順序を決定する) に基づいて比較されます。これは、比較にはコストがかかることを前提としています。しかし、比較は安くても交換が高かったらどうなるでしょうか?それは比較を変えます。そして
  • 複雑： 10,000 個の要素を並べ替えるのに 1 秒かかる場合、100 万個の要素を並べ替えるのにどれくらい時間がかかりますか?この場合の複雑さは、他のものとの相対的な尺度です。

残りを読み終わったら、戻って上記を読み直してください。

私が思いつくビッグオーの最も良い例は、算術を行うことです。2 つの番号 (123456 と 789012) を選択します。私たちが学校で学んだ基本的な算術演算は次のとおりです。

  • 追加;
  • 引き算;
  • 乗算;そして
  • 分割。

これらはそれぞれ操作または問題です。これらを解決する方法を「」といいます。 アルゴリズム.

加算が最も簡単です。数値を (右側に) 並べて列に数字を加算し、その加算結果の最後の数値を結果に書き込みます。その数値の「10」の部分は次の列に引き継がれます。

これらの数値の加算が、このアルゴリズムで最も負荷の高い操作であると仮定しましょう。これら 2 つの数字を加算するには、6 桁を加算する必要があるのは当然です (おそらく 7 桁目も加算されます)。2 つの 100 桁の数字を加算する場合、100 回加算する必要があります。追加すると 二 10,000 桁の数値に対しては、10,000 回の足し算を行う必要があります。

パターンが見えますか?の 複雑 (演算回数) は桁数に正比例します n より大きな数で。これを私たちは呼んでいます の上） または 線形の複雑さ.

減算も同様です (キャリーの代わりに借入が必要な場合がある点を除いて)。

掛け算は違います。数字を並べて、下の数字の最初の桁を取り出し、それを上の数字の各桁と順番に掛け算し、各桁にわたって同様に掛けます。したがって、2 つの 6 桁の数値を乗算するには、36 回の乗算を行う必要があります。最終結果を得るには、10 列または 11 列の追加を行う必要がある場合もあります。

100 桁の数値が 2 つある場合、10,000 回の乗算と 200 回の加算を行う必要があります。2 つの 100 万桁の数値に対して、1 兆 (1012) 乗算と 200 万の加算。

アルゴリズムが n- に応じてスケールするため、二乗, 、 これは の上2) または 二次複雑度. 。ここで、もう 1 つの重要な概念を紹介します。

私たちは複雑さの最も重要な部分のみを考慮します。

賢明な方は、操作の数を次のように表現できることに気づいたかもしれません。n2 +2n。しかし、それぞれ 100 万桁の 2 つの数値を使用した例からわかるように、2 番目の項 (2n) は重要ではなくなります (その段階までの全演算の 0.0002% を占める)。

ここでは最悪のシナリオを想定していることに気づくでしょう。6 桁の数値を乗算するときに、一方が 4 桁で、もう一方が 6 桁の場合、乗算は 24 回しかありません。それでも、その「n」、つまり両方が 6 桁の数字である場合の最悪のシナリオを計算します。したがって、Big-O 表記はアルゴリズムの最悪のシナリオに関するものです。

電話帳

私が思いつく次善の例は電話帳です。通常はホワイト ページなどと呼ばれますが、国によって異なります。しかし、私が話しているのは、姓、次にイニシャルまたは名、おそらく住所、そして電話番号で人々をリストするものについてです。

さて、1,000,000 人の名前が含まれる電話帳から「ジョン スミス」の電話番号を検索するようにコンピューターに指示した場合、どうしますか?S がどこまで始まるか推測できるという事実を無視した場合 (推測できないと仮定しましょう)、あなたならどうしますか?

典型的な実装は、真ん中まで開いて、500,000 を取得することです。番目 「スミス」と比較してください。それがたまたま「スミス、ジョン」だったら、本当に幸運です。「ジョン・スミス」がその名前の前か後にある可能性の方がはるかに高いです。それ以降の場合は、電話帳の後半を半分に分割して繰り返します。以前の場合は、電話帳の前半を半分に分割して繰り返します。等々。

これはと呼ばれます 二分探索 そして、あなたが意識しているかどうかに関係なく、プログラミングで毎日使用されています。

したがって、100 万件の名前が含まれる電話帳から名前を見つけたい場合、これを最大 20 回実行するだけで、実際には任意の名前を見つけることができます。検索アルゴリズムを比較する際、この比較が「n」であると判断します。

  • 3 人の名前の電話帳の場合、(最大でも) 2 回の比較が必要です。
  • 7 の場合、最大でも 3 つ必要です。
  • 15の場合は4かかります。
  • …
  • 1,000,000の場合は20必要です。

それは驚くほど良いことですよね？

Big-O 用語で言えば、これは O(log n) または 対数複雑度. 。ここで、問題の対数は ln (底 e)、log になります。10, 、ログ2 または他の基地。O(2n と同じように O(log n) であることは問題ではありません2) と O(100n2) は依然として両方とも O(n2).

この時点で、Big O を使用してアルゴリズムで 3 つのケースを決定できることを説明する価値があります。

  • 最良の場合： 電話帳検索では、1 回の比較で名前が見つかるのが最良のケースです。これは ○(1) または 一定の複雑さ;
  • 予想されるケース: 上で説明したように、これは O(log n) です。そして
  • 最悪の場合： これも O(log n) です。

通常、私たちは最良のケースを気にしません。私たちは予想される最悪のケースに興味があります。場合によっては、これらのどちらかがより重要になることがあります。

電話帳に戻ります。

電話番号を持っていて名前を調べたい場合はどうすればよいでしょうか?警察は逆引きの電話帳を持っていますが、そのような検索は一般の人々には拒否されています。それともそうですか？技術的には、通常の電話帳の番号を逆引きすることができます。どうやって？

名前から始めて番号を比較します。一致した場合は問題ありませんが、一致しなかった場合は次のステップに進みます。電話帳はこうする必要があるので、 順序なし （とにかく電話番号で）。

電話番号から名前を検索するには (逆引き参照):

  • 最良の場合： O(1);
  • 予想されるケース: O(n) (500,000 の場合);そして
  • 最悪の場合： O(n) (1,000,000 の場合)。

巡回セールスマン

これはコンピュータ サイエンスでは非常に有名な問題であり、言及する価値があります。この問題には N 個の町があります。これらの各町は、一定距離の道路によって 1 つ以上の他の町とつながっています。巡回セールスマンの問題は、すべての町を訪れる最短のツアーを見つけることです。

簡単そうに思えますか？もう一度考えて。

A、B、C の 3 つの町があり、すべてのペアの間に道路がある場合、次のようになります。

  • A→B→C
  • A → C → B
  • B → C → A
  • B → A → C
  • C→A→B
  • C→B→A

まあ、実際にはこれよりも少ないのは、これらのいくつかは同等であるためです (たとえば、A → B → C と C → B → A は同じ道路を逆に使用しているため、同等です)。

実際には 3 つの可能性があります。

  • これを 4 つの町に持っていくと、(iirc) 12 の可能性があります。
  • 5だと60になります。
  • 6は360になります。

これは、と呼ばれる数学的演算の関数です。 階乗. 。基本的に：

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
  • 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
  • …
  • 25! = 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000
  • …
  • 50! = 50 × 49 × … × 2 × 1 = 3.04140932 × 1064

つまり、巡回セールスマン問題の Big-O は次のようになります。 の上！） または 階乗または組み合わせの複雑さ.

200 の町に到達するまでに、従来のコンピューターで問題を解決するのに十分な時間は宇宙に残されていません。

考えるべきことがある。

多項式時間

私が簡単に述べておきたかったもう 1 つの点は、アルゴリズムの複雑さは次のとおりです。 の上ある) あると言われています 多項式の複雑さ またはで解決可能です 多項式時間.

O(n)、O(n2）など。はすべて多項式時間です。一部の問題は多項式時間では解決できません。このため、特定のものが世界中で使用されています。 公開鍵暗号化 はその代表的な例です。非常に大きな数の 2 つの素因数を見つけるのは計算上困難です。そうしないと、私たちが使用している公開鍵システムを使用できなくなります。

とにかく、これで Big O (改訂版) についての (できれば平易な英語での) 説明は終わりです。

他のヒント

アルゴリズムがどのように拡張されるかを示します。

の上2):として知られている 二次複雑度

  • 1 アイテム:1秒
  • 10項目:100秒
  • 100アイテム:10000秒

項目数は 10 倍に増加しますが、時間も 10 倍に増加することに注目してください。2. 。基本的に、n=10 なので、O(n2) スケーリング係数 n が得られます。2 それは10です2.

の上）:として知られている 線形複雑さ

  • 1 アイテム:1秒
  • 10項目:10秒
  • 100アイテム:100秒

今回はアイテムの数が 10 倍に増加し、時間も増加します。n=10 なので、O(n) のスケーリング係数は 10 です。

○(1):として知られている 一定の複雑さ

  • 1 アイテム:1秒
  • 10項目:1秒
  • 100アイテム:1秒

項目数は依然として 10 倍に増加していますが、O(1) のスケーリング係数は常に 1 です。

O(log n):として知られている 対数複雑度

  • 1 アイテム:1秒
  • 10項目:2秒
  • 100アイテム:3秒
  • 1000 アイテム:4秒
  • 10000 アイテム:5秒

計算数は入力値の対数だけ増加します。したがって、この場合、各計算に 1 秒かかると仮定すると、入力のログは次のようになります。 n 所要時間ですので、 log n.

それが要点です。計算が削減されるため、正確に n にならない可能性があります2 あるいは彼らが何と言おうと、それがスケーリングにおける支配的な要素となるでしょう。

Big-O 表記法 (「漸近成長」表記法とも呼ばれます) は、 定数要素や原点付近のものを無視した場合、関数はどのように見えるか. 。について話すためにそれを使います 物事の規模.

基本

「十分に」大きな入力の場合...

  • f(x) ∈ O(upperbound) 手段 f 「これより早く成長することはない」 upperbound
  • f(x) ∈ Ɵ(justlikethis) 平均 f 「まったく同じように成長する」 justlikethis
  • f(x) ∈ Ω(lowerbound) 手段 f 「それよりも遅くは成長しない」 lowerbound

big-O 表記法では定数因数は考慮されません。関数 9x² 「まったく同じように成長する」と言われています 10x². 。ビッグオーもそうではない 漸近的 表記注意 非漸近的 もの (「原点に近いもの」または「問題のサイズが小さい場合に何が起こるか」):関数 10x² 「まったく同じように成長する」と言われています 10x² - x + 2.

なぜ方程式の小さな部分を無視したいのでしょうか?なぜなら、スケールがますます大きくなるにつれて、方程式の大きな部分によってそれらが完全に矮小化されてしまうからです。彼らの貢献は矮小化され、無意味なものになってしまいます。(例のセクションを参照してください。)

別の言い方をすれば、それはすべてです。 比率 無限に行くにつれて。 実際にかかった時間を割ると、 O(...), 、大規模な入力の制限に一定の係数が得られます。 直感的にこれは理にかなっています:一方を乗算してもう一方を取得できる場合、関数は互いに「同じようにスケール」されます。つまり、私たちが言うとき...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

...この意味は 「十分に大きい」問題サイズ N の場合 (原点付近のものを無視すると)、何らかの定数が存在します(例:2.5、完全に構成されています）次のようになります。

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)

定数には多くの選択肢があります。多くの場合、「最良の」選択はアルゴリズムの「定数要素」として知られています...しかし、最大でない項を無視するのと同じように、それを無視することがよくあります (定数因子が通常重要ではない理由については、定数因子のセクションを参照してください)。上の式を境界として考えることもできます。最悪のシナリオでも、所要時間はおよそより悪くなることはありません N*log(N), 、係数 2.5 以内 (定数係数はあまり気にしません)".

一般的に、 O(...) 私たちは最悪の場合の動作を気にすることが多いため、これが最も便利です。もし f(x) プロセッサやメモリの使用状況などの「悪い」ものを表す場合、「f(x) ∈ O(upperbound)" 手段 "upperbound これはプロセッサ/メモリ使用量の最悪のシナリオです。」

アプリケーション

純粋に数学的な構造として、big-O 記法は処理時間とメモリについて話すことに限定されません。これを使用して、次のようなスケーリングが意味のあるあらゆるものの漸近について議論できます。

  • 間のハンドシェイクの可能性のある回数 N パーティーにいる人々 (Ɵ(N²), 、 具体的には N(N-1)/2, 、しかし重要なのは、「スケールが似ている」ということです。 N²)
  • 時間の関数として何らかのバイラルマーケティングを見た確率的に予想される人の数
  • Web サイトの遅延が CPU、GPU、またはコンピューター クラスターの処理ユニットの数に応じてどのように増減するか
  • CPU ダイの熱出力がトランジスタ数、電圧などの関数としてどのように変化するか。
  • 入力サイズの関数として、アルゴリズムの実行に必要な時間
  • 入力サイズの関数として、アルゴリズムを実行する必要があるスペースの量

例

上の握手の例では、部屋にいる全員が他の全員と握手します。その例では、 #handshakes ∈ Ɵ(N²). 。なぜ？

少しバックアップしてください:ハンドシェイクの数は正確に n-choose-2 または N*(N-1)/2 (N 人のそれぞれが他の N-1 人と握手をしますが、これでは握手のカウントが 2 倍になるため、2 で割ります):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article. adjacency matrix

ただし、非常に多数の人の場合、線形項は N は矮小化され、実質的に比率に 0 が寄与します (グラフ内:参加者の数が増えるにつれて、ボックス全体に対する対角線上の空のボックスの割合は小さくなります)。したがって、スケーリング動作は次のようになります。 order N², 、またはハンドシェイクの数が「N² のように増加」します。

#handshakes(N)
────────────── ≈ 1/2
     N²

チャートの対角線上にある空のボックス (N*(N-1)/2 チェックマーク) さえ存在しないかのようです (N2 漸近的にチェックマークを付けます)。

(「平易な英語」からの一時的な脱線:) これを自分で証明したい場合は、比率に対して簡単な代数を実行して、比率を複数の項に分割することができます (lim は「の限界で考慮される」という意味です。まだ見ていない場合は無視してください。これは「そして N は本当に非常に大きい」の単なる表記です):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

先生:ハンドシェイクの数は、大きな値では x² のように見えるため、#handshakes/x² の比率を書き留める必要がないという事実があります。 その通り x² ハンドシェイクは、任意の長い期間、小数点でさえ表示されません。

例えばx=100万の場合、#handshakes/x²の比率:0.499999...

直感を構築する

これにより、次のようなステートメントを作成できるようになります...

「inputsize=N が十分に大きい場合、定数係数が何であっても、 ダブル 入力サイズ...

  • ...O(N) (「線形時間」) アルゴリズムにかかる時間を 2 倍にしました。」

    N → (2N) = 2(N)

  • ...O(N²) (「二次時間」) アルゴリズムにかかる時間を 2 乗 (4 倍) にしました。 （例えば。100 倍大きな問題には 100²=10000 倍の時間がかかります...おそらく持続不可能）

    N² → (2N)² = 4(N²)

  • ...O(N³) (「3 次時間」) アルゴリズムにかかる時間を 2 倍 (8 倍) にしました。」 （例えば。100 倍大きな問題には 1003=1000000 倍の時間がかかります...非常に持続不可能です）

    cN3 → c(2N)3 = 8(cN3)

  • ...O(log(N)) (「対数時間」) アルゴリズムにかかる時間に固定量を加算します。 （安い！）

    cログ(N) → c log(2N) = (c log(2))+(cログ(N)) = (固定量)+(cログ(N))

  • ...O(1) (「一定時間」) アルゴリズムにかかる時間は変更しません。」 （最も安い！）

    c*1 → c*1

  • ...O(N log(N)) アルゴリズムにかかる時間が「(基本的に) 2 倍」になります。 （非常に一般的な）

    それは O(N1.000001)、基本的には線形と呼ぶこともできます。

  • ...私はばかげて時間を増やします a O(2N) (「指数関数的時間」) アルゴリズムがかかります。」 (問題を 1 単位増やすだけで、時間は 2 倍 (または 3 倍など) になります)

    2N → 22N = (4N)......別の言い方をすると...... 2N → 2N+1 = 2N21 = 2 2N

[数学に興味のある方は、ネタバレ部分にマウスを置くと細かい補足が表示されます]

(クレジット付き) https://stackoverflow.com/a/487292/711085 )

(技術的には、より難解な例では定数係数が重要になる可能性がありますが、私は上記のことを表現しました (例:log(N)) ではそうならないように)

これらは、プログラマーや応用コンピューター科学者が参照点として使用する成長の基本的な順序です。彼らはこれらを常に見ています。(したがって、技術的には「入力を 2 倍にすると O(√N) アルゴリズムが 1.414 倍遅くなる」と考えることもできますが、「これは対数よりも悪くなりますが、線形よりは優れている」と考えたほうがよいでしょう。)

定数係数

通常、特定の定数因子が何であるかは気にしません。なぜなら、それらは関数の成長方法に影響を与えないからです。たとえば、2 つのアルゴリズムは両方とも次のようになります。 O(N) 完了までに時間がかかりますが、一方が他方よりも 2 倍遅くなる可能性があります。最適化は難しい作業であるため、係数が非常に大きくない限り、通常はあまり気にしません。 最適化が時期尚早なのはどのような場合でしょうか? );また、より優れた big-O を備えたアルゴリズムを選択するだけで、パフォーマンスが桁違いに向上することがよくあります。

いくつかの漸近的に優れたアルゴリズム (例:比較対象外 O(N log(log(N))) sort) は非常に大きな定数係数を持つことができます (例: 100000*N log(log(N)))、または次のような比較的大きなオーバーヘッド O(N log(log(N))) 隠れたもので + 100*N, 、「ビッグデータ」であっても使用する価値はほとんどありません。

なぜ O(N) が最善の場合があるのか​​というと、なぜデータ構造が必要なのか

O(N) すべてのデータを読み取る必要がある場合、アルゴリズムはある意味で「最適な」アルゴリズムです。の まさに読書という行為 大量のデータは O(N) 手術。通常、メモリにロードするのは、 O(N) (ハードウェア サポートがある場合はより高速ですが、すでにデータを読み取っている場合は時間がかかりません)。しかし、あなたが触れたり、 見て すべてのデータ (または他のすべてのデータ) で、アルゴリズムは O(N) これを実行する時間です。実際のアルゴリズムにどれだけ時間がかかるとしても、少なくとも O(N) なぜなら、その時間をすべてのデータの確認に費やしたからです。

同じことが、 まさに書くという行為. 。N 個の内容を出力するすべてのアルゴリズムは、出力が少なくともそれだけ長いため、N 時間かかります (例:N 枚のトランプのセットのすべての順列 (並び替える方法) を出力することは階乗です: O(N!)).

これは、 データ構造:データ構造ではデータの読み取りが 1 回だけ必要になります (通常は O(N) 時間）に加えて、任意の量の前処理（例: O(N) または O(N log(N)) または O(N²)）これを小さく保つよう努めます。その後、データ構造の変更 (挿入/削除など) やデータに対するクエリの作成には、非常に短時間で済みます。 O(1) または O(log(N)). 。次に、大量のクエリを作成します。一般に、事前にやっておく作業が多ければ多いほど、後でやらなければならない作業は少なくなります。

たとえば、何百万もの道路セグメントの緯度と経度の座標があり、すべての道路の交差点を見つけたいとします。

  • 素朴な方法:道路の交差点の座標があり、近くの道路を調べたい場合は、毎回何百万ものセグメントを調べて、それぞれの隣接性を確認する必要があります。
  • これを一度だけ実行する必要がある場合は、次のような単純な方法を実行する必要はありません。 O(N) 作業は 1 回だけですが、何度も実行したい場合 (この場合、 N 回、セグメントごとに 1 回)、次のことを行う必要があります。 O(N²) 仕事、または 1000000²=1000000000000 回の操作。良くありません (最新のコンピューターは 1 秒あたり約 10 億回の演算を実行できます)。
  • ハッシュ テーブル (ハッシュマップまたはディクショナリとも呼ばれるインスタント スピード ルックアップ テーブル) と呼ばれる単純な構造を使用する場合、すべてを前処理することで少額のコストを支払います。 O(N) 時間。その後は、キーによって何かを検索するのに平均して一定の時間しかかかりません (この場合、キーはグリッドに丸められた緯度と経度の座標です。9 個しかない隣接するグリッド空間を検索します (これは定数です)。
  • 私たちの任務は実行不可能なものから始まりました O(N²) 管理可能なものに O(N), 、そして私たちがしなければならなかったのは、ハッシュテーブルを作成するために少額のコストを支払うことだけでした。
  • 類推:この特定のケースのアナロジーは、ジグソーパズルに似ています。データの何らかの特性を利用するデータ構造を作成しました。道路セグメントがパズルのピースのような場合、色とパターンを一致させることでグループ化します。次に、これを利用して、後で余分な作業 (他の単一のパズル ピースごとではなく、同じ色のパズル ピース同士を比較する) を行うことを回避します。

この話の教訓:データ構造により操作を高速化できます。さらに高度なデータ構造を使用すると、信じられないほど賢い方法で操作を結合したり、遅延させたり、無視したりすることができます。問題が異なれば類推も異なりますが、それらはすべて、私たちが関心を持っている構造、または簿記のために人為的に課した構造を利用する方法でデータを整理することに関係します。私たちは事前に作業を行う (基本的には計画と整理) ため、繰り返し行われるタスクがはるかに簡単になりました。

実際の例:コーディング中に成長の順序を視覚化する

漸近記法は本質的に、プログラミングとはまったく別のものです。漸近記法は、物事がどのようにスケールするかを考えるための数学的フレームワークであり、さまざまな分野で使用できます。そうは言っても...これがあなたです 適用する コーディングへの漸近表記。

基礎：サイズ A のコレクション (配列、セット、マップのすべてのキーなど) 内のすべての要素を操作するとき、またはループの A 回の反復を実行するとき、それはサイズ A の乗算係数になります。なぜ「乗算係数」と言うのか? -- ループと関数には (ほぼ定義上) 実行時間が乗算されるためです。反復回数、ループ内 (または関数の場合) で行われた作業の回数。関数を呼び出した回数、関数内で行われた作業の回数)。(これは、ループをスキップしたり、ループを早期に終了したり、引数に基づいて関数内の制御フローを変更したりするなど、特別なことを何も行わない場合に当てはまります。これは非常に一般的です。) ここでは、視覚化手法の例を、疑似コードとともにいくつか示します。

(ここでは、 x定数時間の作業単位、プロセッサ命令、インタープリタのオペコードなどを表します)

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

例 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

例 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

少し複雑なことをしたとしても、何が起こっているかを視覚的に想像できるかもしれません。

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

ここでは、描画できる最小の認識可能な輪郭が重要です。正方形が 2 次元形状 (A^2) であるのと同様に、三角形は 2 次元形状 (0.5 A^2) です。ここでの 2 の定数因子は 2 つの間の漸近比に残りますが、他の因子と同様に無視します...(このテクニックには残念なニュアンスがいくつかありますが、ここでは説明しません。誤解を招く可能性があります。)

もちろん、これはループや関数が悪いという意味ではありません。むしろ、それらは現代のプログラミング言語の構成要素であり、私たちはそれらを愛しています。ただし、ループ、関数、条件文をデータ (制御フローなど) と組み合わせる方法は、プログラムの時間と空間の使用状況を模倣していることがわかります。時間と空間の使用が問題になる場合は、賢明な手段に頼って、考えもしなかった簡単なアルゴリズムやデータ構造を見つけて、何らかの方法で成長の順序を下げようとするときです。それにもかかわらず、これらの視覚化手法は (常に機能するとは限りませんが)、最悪の場合の実行時間を単純に推測することができます。

視覚的に認識できるもう 1 つの点は次のとおりです。

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

これを並べ替えるだけで、O(N) であることがわかります。

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

あるいは、合計 O(N*log(N)) 時間でデータの log(N) パスを実行する場合もあります。

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

関係ありませんが、もう一度言及する価値があります:ハッシュを実行すると (例:辞書/ハッシュテーブル検索)、これは O(1) の係数です。かなり早いですね。

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

再帰関数や分割統治アルゴリズムなど、非常に複雑なことを行う場合、 を使用できます マスター定理 (通常は機能します)、またはばかばかしい場合には、アクラ・バッツィの定理(ほぼ常に機能します) アルゴリズムの実行時間を Wikipedia で調べます。

しかし、プログラマーはこのようには考えません。最終的には、アルゴリズムの直感が第二の性質になるからです。何か非効率的なコードを書き始めると、すぐに「何かやってるのかな？」と思うでしょう。 ひどく非効率的ですか？」。答えが「はい」で、それが実際に重要であると予測できる場合は、一歩下がって、処理を高速化するためのさまざまなトリックを考えることができます (答えは、ほとんどの場合「ハッシュテーブルを使用する」であり、まれに「ツリーを使用する」になります。ごくまれに、もう少し複雑なものもあります)。

償却および平均ケースの複雑さ

「償却」および/または「平均ケース」という概念もあります (これらは異なることに注意してください)。

平均的なケース:これは、関数自体ではなく、関数の期待値に対して big-O 表記法を使用することに他なりません。すべての入力の可能性が等しいと考える通常のケースでは、平均ケースは実行時間の平均にすぎません。たとえば、クイックソートの場合、最悪のケースは次のとおりです。 O(N^2) いくつかの本当に悪い入力の場合、平均的なケースは通常です O(N log(N)) (本当に悪い入力は数が非常に少ないため、平均的な場合は気付かないほどです)。

償却後の最悪ケース:一部のデータ構造では、最悪の場合の複雑さが大きくなる場合がありますが、これらの操作を多数実行すると、平均作業量が最悪の場合よりも改善されることが保証されます。たとえば、通常は定数を取るデータ構造があるとします。 O(1) 時間。ただし、場合によっては「しゃっくり」が発生し、時間がかかることがあります。 O(N) ランダムな操作を 1 回行う時間です。おそらく、何らかの簿記やガベージ コレクションなどを実行する必要があるからです。ただし、たとえ一時停止が発生しても、あと N 回の操作では再度一時停止しないことが保証されています。最悪の場合のコストは依然として O(N) 操作ごと、ただし償却コスト 何度も実行して は O(N)/N = O(1) 操作ごとに。大規模な操作は十分にまれであるため、時折発生する大量の作業は、一定の要素として残りの作業に溶け込んでいると考えることができます。作業は、漸近的に消滅するほど十分な数の呼び出しにわたって「償却」されると言います。

償却分析のアナロジーは次のとおりです。

あなたは車を運転します。場合によっては、ガソリンスタンドに10分間費やしてから、タンクをガスで1分間補充する必要があります。車でどこにでも行くたびにこれを行うと（ガソリンスタンドへの運転10分を費やし、ガロンのほんの一部を埋めるために数秒を費やして）、それは非常に非効率的です。しかし、数日ごとに1回タンクを埋めると、ガソリンスタンドへの運転に費やした11分間は、十分に多数の旅行で「償却」されます。それを無視して、すべての旅行が5％長いふりをすることができます。

平均ケースと償却された最悪ケースの比較:

  • 平均的なケース:私たちは入力に関していくつかの仮定を立てます。つまり入力の確率が異なる場合、出力/ランタイムの確率も異なります (平均をとります)。通常、入力はすべて等しい可能性 (一様確率) であると想定されますが、現実世界の入力が「平均入力」の想定に適合しない場合、平均出力/実行時間の計算は無意味になる可能性があります。ただし、一様にランダムな入力が予想される場合は、これを考慮すると便利です。
  • 償却された最悪の場合:償却された最悪のケースのデータ構造を使用する場合、パフォーマンスは償却された最悪のケースの範囲内であることが保証されます。最終的には (すべてを知っていてあなたを台無しにしようとしている邪悪な悪魔によって入力が選ばれたとしても)。通常、これを使用して、予期せぬ大きな問題が発生してパフォーマンスが非常に「不安定」になる可能性のあるアルゴリズムを分析しますが、時間が経つにつれて、他のアルゴリズムと同様にパフォーマンスが向上します。(ただし、データ構造に、先延ばししても構わない未処理の作業の上限が設定されていない限り、悪意のある攻撃者が、最大量の先延ばし作業を一度に処理することを強制する可能性があります。

でも、もしあなたがそうであれば、 適度に心配 攻撃者に関しては、償却や平均的なケース以外にも、懸念すべきアルゴリズム攻撃ベクトルが多数あります。)

平均ケースと償却はどちらも、スケーリングを念頭に置いて考え、設計するための非常に便利なツールです。

（見る 平均ケースと償却分析の違い このサブトピックに興味があれば。)

多次元ビッグオー

ほとんどの場合、人々は複数の変数が働いていることに気づいていません。たとえば、文字列検索アルゴリズムでは、アルゴリズムに時間がかかる場合があります。 O([length of text] + [length of query]), 、つまりそれは次のような2つの変数で線形です O(N+M). 。他のより素朴なアルゴリズムは次のとおりです。 O([length of text]*[length of query]) または O(N*M). 。複数の変数を無視することは、アルゴリズム分析で最もよく見られる見落としの 1 つであり、アルゴリズムの設計時に障害となる可能性があります。

一部始終

ビッグオーがすべてではないことに留意してください。キャッシュを使用する、キャッシュを意識しないようにする、ディスクの代わりに RAM を使用してボトルネックを回避する、並列化を使用する、または事前に作業を実行することで、一部のアルゴリズムを大幅に高速化できます。これらのテクニックは、多くの場合、 独立した ただし、並列アルゴリズムの big-O 表記ではコアの数がよく見られます。

また、プログラムの隠れた制約により、漸近的な動作はあまり気にしない可能性があることにも留意してください。たとえば、次のように、制限された数の値を操作する場合があります。

  • 5 つの要素のようなものを並べ替える場合は、Speed メソッドを使用したくないでしょう。 O(N log(N)) クイックソート;挿入ソートを使用したいとします。これは、小さな入力でうまく機能します。このような状況は、再帰的並べ替え、高速フーリエ変換、行列の乗算など、問題をより小さなサブ問題に分割する分割統治アルゴリズムでよく発生します。
  • いくつかの値が何らかの隠れた事実により事実上制限されている場合 (例:人間の平均的な名前はおそらく 40 文字で緩やかに制限され、人間の年齢は約 150 文字で緩やかに制限されます)。入力に境界を課して、項を効果的に一定にすることもできます。

実際には、同じまたは類似した漸近的なパフォーマンスを持つアルゴリズム間でも、その相対的なメリットは、実際には次のような他の要因によって左右される可能性があります。その他のパフォーマンス要因 (クイックソートとマージソートは両方とも O(N log(N)), ただし、クイックソートは CPU キャッシュを利用します)。実装の容易さなど、パフォーマンス以外の考慮事項。図書館が利用可能かどうか、そしてその図書館がどの程度評判が良く、維持管理されているか。

また、500MHz のコンピュータでは 2GHz のコンピュータよりもプログラムの実行が遅くなります。私たちはスケーリングをマシン リソース (例:実秒ごとではなく、クロック サイクルごとに)。ただし、エミュレーションで実行しているかどうか、コンパイラがコードを最適化したかどうかなど、パフォーマンスに「密かに」影響を与える可能性のある同様のものが存在します。これらにより、一部の基本的な操作の時間が (相互に相対的にであっても) 長くなったり、一部の操作が漸近的に (相互に相対的にであっても) 高速化または低速化する場合があります。効果は、実装や環境が異なると小さい場合も大きい場合もあります。その少しの余分な作業を補うために、言語やマシンを切り替えますか?それは他の 100 の理由 (必要性、スキル、同僚、プログラマーの生産性、時間の金銭的価値、慣れ、回避策、アセンブリや GPU を使用しない理由など...) によって決まりますが、これらの理由はパフォーマンスよりも重要である可能性があります。

上記の問題は、プログラミング言語と同様、定数要素の一部として考慮されることはほとんどありません (また、そうすべきではありません)。それでも、それらを認識しておく必要があります。 時々 （まれではありますが）物事に影響を与える可能性があります。たとえば、cpython では、ネイティブの優先キューの実装は漸近的に最適ではありません (O(log(N)) それよりも O(1) 挿入または find-min を選択します);別の実装を使用していますか?C 実装のほうがおそらく高速であり、おそらく他の場所にも同様の問題があるため、おそらくそうではありません。トレードオフがあります。それらは重要な場合もあれば、そうでない場合もあります。

(編集:「わかりやすい英語」の説明はここで終わります。）

数学の付録

完全を期すため、big-O 表記の正確な定義は次のとおりです。 f(x) ∈ O(g(x)) これは、「f は const*g によって漸近的に上限が設定される」ことを意味します。x の有限値以下のすべてを無視すると、次のような定数が存在します。 |f(x)| ≤ const * |g(x)|. 。(その他の記号は以下の通りです。と同じように O ≤を意味します。 Ω ≧を意味します。小文字のバリエーションもあります。 o < を意味し、 ω > を意味します。) f(x) ∈ Ɵ(g(x)) 両方を意味します f(x) ∈ O(g(x)) そして f(x) ∈ Ω(g(x)) (上限と下限は g で区切られます):f が常に次の範囲の「帯域」内に位置するような定数がいくつか存在します。 const1*g(x) そして const2*g(x). 。これは、作成できる最も強力な漸近ステートメントであり、次とほぼ同等です。 ==. 。(申し訳ありませんが、明確にするために、絶対値シンボルについての言及を今まで遅らせることにしました。特にコンピューター サイエンスの文脈で負の値が登場するのを見たことがありません。)

人々はよく使います = O(...), これはおそらく、より正確な「comp-sci」表記であり、完全に合法的に使用できます。「f = O(...)」は「f は次数です...」と読みます。/ f は ... によって xxx で区切られています」となり、「f は漸近線が ... である何らかの式である」と考えられます。より厳密なものを使うように教えられました ∈ O(...). ∈ 「の要素である」を意味します（以前と同様に読み取れます）。 O(N²) 実際には 同等クラス, つまり、それは私たちが同じであると考えるもののセットです。この特定のケースでは、 O(N²) { のような要素が含まれています2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} は無限に大きくなりますが、それでも集合です。の = 表記法のほうが一般的である可能性があり、世界的に有名なコンピュータ科学者の論文でも使用されています。さらに、カジュアルな環境では、人々は次のように言うことがよくあります。 O(...) 彼らが意味するとき Ɵ(...);これは技術的には真実です。 Ɵ(exactlyThis) のサブセットです O(noGreaterThanThis)...そして入力しやすくなります。;-)

編集：簡単な注意ですが、これはほぼ確実に混乱を招きます ビッグオー表記 (これは上限です)、Theta 表記法 (これは上限と下限の両方です) を使用します。私の経験では、これは実際、学術以外の場での議論によく見られる現象です。混乱を招いてしまったことをお詫び申し上げます。

一文で言うと：ジョブのサイズが大きくなるにつれて、完了するまでにどのくらい時間がかかりますか?

明らかに、これは入力として「サイズ」を使用し、出力として「所要時間」を使用しているだけです。メモリ使用量などについて話したい場合にも同じ考えが当てはまります。

ここでは、乾燥させたい T シャツが N 枚ある場合の例を示します。良い 仮定する 信じられないほど早く乾燥位置に移動できます（つまり、人間の相互作用は無視できます)。もちろん現実ではそんなことはありませんが…

  • 屋外で物干し竿を使用する場合:無限に広い裏庭があると仮定すると、洗濯物は O(1) 時間で乾きます。どんなにたくさん持っていても、同じように太陽と新鮮な空気が当たるので、サイズは乾燥時間に影響しません。

  • 回転式乾燥機を使用する場合:それぞれの荷物に 10 枚のシャツを入れると、1 時間後には仕上がります。(ここでの実際の数字は無視してください。無関係です。) したがって、50 枚のシャツを乾かすには時間がかかります。 について シャツ10枚を乾燥させるのに5倍の時間がかかります。

  • すべてを食器棚に入れる:すべてを 1 つの大きな山に入れて、一般的な暖かさに任せると、真ん中のシャツが乾くまでに長い時間がかかります。詳細については推測したくありませんが、これは少なくとも O(N^2) ではないかと思います。洗濯負荷が増えると、乾燥時間も早くなります。

「big O」表記の重要な側面の 1 つは、 しません 特定のサイズに対してどのアルゴリズムが高速になるかを示します。ハッシュテーブル (文字列キー、整数値) とペアの配列 (文字列、整数) を比較します。文字列に基づいて、ハッシュテーブル内のキーを見つけるのと配列内の要素を見つけるのはどちらの方が早いでしょうか?(すなわち、配列の場合、「文字列部分が指定されたキーに一致する最初の要素を検索します。」) ハッシュテーブルは通常、償却されます (~= "平均") O(1) — 一度セットアップされると、ほぼ同じ時間がかかります。 1,000,000 エントリ テーブルの場合と同様に、100 エントリ テーブルでエントリを見つけるのに時間がかかります。配列内の要素の検索 (インデックスではなく内容に基づいて) は線形です。O(N) — 平均すると、エントリの半分を見る必要があります。

これにより、ハッシュテーブルの検索が配列より高速になりますか?必ずしも。エントリのコレクションが非常に小さい場合は、配列の方が速い可能性があります。表示しているもののハッシュコードを計算するのにかかる時間内にすべての文字列をチェックできる可能性があります。ただし、データセットが大きくなるにつれて、最終的にはハッシュテーブルが配列を上回ることになります。

Big O は、入力が大きくなったときの関数の成長動作 (プログラムの実行時間など) の上限を記述します。

例:

  • の上）：入力サイズを 2 倍にすると、実行時間も 2 倍になります

  • の上2):入力サイズが 2 倍になると、実行時間は 4 倍になります

  • O(log n):入力サイズが 2 倍になると、実行時間は 1 つ増加します

  • O(2n):入力サイズが 1 増加すると、実行時間は 2 倍になります

入力サイズは通常、入力を表すために必要なビット単位のスペースです。

Big O 表記は、入力セットのサイズの関数として表される、計算 (アルゴリズム) が完了するまでにかかる時間をおおよその尺度としてプログラマによって最も一般的に使用されます。

Big O は、入力数が増加したときに 2 つのアルゴリズムがどの程度スケールアップするかを比較するのに役立ちます。

より正確に ビッグオー表記 関数の漸近的な動作を表現するために使用されます。これは、関数が無限に近づくときにどのように動作するかを意味します。

多くの場合、アルゴリズムの「O」は次のいずれかのケースに当てはまります。

  • ○(1) - 完了までの時間は、入力セットのサイズに関係なく同じです。例としては、インデックスによる配列要素へのアクセスです。
  • O(対数N) - 完了までの時間は、log2(n) にほぼ比例して増加します。たとえば、Log2(1024) = 10 および Log2(32) = 5 であるため、1024 項目の場合は 32 項目の場合の約 2 倍の時間がかかります。例としては、 二分探索木 (BST)。
  • の上） - 入力セットのサイズに比例して増加する完了までの時間。言い換えれば、入力セット内の項目の数を 2 倍にすると、アルゴリズムにかかる時間は約 2 倍になります。例としては、リンクされたリスト内の項目の数を数えることが挙げられます。
  • O(N ログ N) - 完了までの時間は、項目数と Log2(N) の結果の積だけ増加します。この例としては、 ヒープソート そして クイックソート.
  • O(N^2) - 完了までの時間は、アイテム数の 2 乗にほぼ等しくなります。この例としては、 バブルソート.
  • の上！） - 完了までの時間は、入力セットの階乗です。この例としては、 巡回セールスマン問題のブルートフォースソリューション.

Big O は、入力サイズが無限に向かって増加するにつれて、関数の成長曲線に意味のある形で寄与しない要因を無視します。これは、関数に加算または乗算される定数は単純に無視されることを意味します。

Big O は、「コードを実行するのにどのくらいの時間/スペースが必要ですか?」という一般的な方法で自分自身を「表現」する方法にすぎません。

O(n)、O(n) をよく目にするかもしれません。2)、O(nlogn) など、これらはすべて表示方法にすぎません。アルゴリズムはどのように変化するのでしょうか?

o（n）は大きなoがnであることを意味し、今では「n！？」と思うかもしれません。まあ「n」は要素の量です。配列内の項目を検索したいと考えています。あなたは各要素を見なければならないでしょう、そして「あなたは正しい要素/アイテムですか？」最悪の場合、アイテムは最後のインデックスにあります。つまり、リストに項目があるのと同じくらい時間がかかったので、一般的には「ああ、nは公正な値の値です！」と言います。 。

そうすれば、「n」が何であるか理解できるかもしれません2」 という意味ですが、さらに具体的に言うと、単純な、最も単純な並べ替えアルゴリズムを考えて遊んでください。バブルソート。このアルゴリズムでは、項目ごとにリスト全体を調べる必要があります。

私のリスト

  1. 1
  2. 6
  3. 3

ここでの流れは次のようになります。

  • 1 と 6 を比較して、どちらが大きいですか?OK 6 は正しい位置にあり、前進しています!
  • 6 と 3 を比較すると、ああ、3 のほうが少ないですね。それを移動しましょう。OK リストが変更されました。今すぐ最初から始める必要があります。

これはオンです2 なぜなら、「n」個の項目があるリスト内のすべての項目を確認する必要があるからです。各項目について、比較するためにすべての項目をもう一度確認します。これも "n" であるため、すべての項目について "n" 回確認します。つまり、n*n = n になります。2

これがあなたが望むのと同じくらい簡単であることを願っています。

ただし、ビッグ オーは時間と空間の中で自分自身を表現する手段にすぎないことを忘れないでください。

Big O は、アルゴリズムの基本的なスケーリングの性質を説明します。

特定のアルゴリズムについて、Big O が教えていない情報がたくさんあります。これは、アルゴリズムのスケーリングの性質、特に「入力サイズ」に応じてアルゴリズムのリソース使用量 (思考時間またはメモリ) がどのようにスケーリングされるかについての情報のみを骨子的に示しています。

蒸気エンジンとロケットの違いを考えてみましょう。それらは、単に同じものの異なる種類ではありません（たとえば、プリウスのエンジンとエンジンのような）。ランボルギーニ エンジンなど）しかし、それらは本質的には劇的に異なる種類の推進システムです。蒸気エンジンはおもちゃのロケットより速いかもしれませんが、蒸気ピストン エンジンでは軌道打上げロケットの速度を達成することはできません。これは、これらのシステムが、特定の速度 (「入力サイズ」) に達するために必要な燃料 (「リソース使用量」) の関係に関して、異なるスケーリング特性を備えているためです。

なぜこれがそれほど重要なのでしょうか?ソフトウェアは、最大 1 兆倍の大きさが異なる可能性がある問題を扱うからです。少し考えてみましょう。月への移動に必要な速度と人間の歩行速度の比は 10,000:1 未満であり、これはソフトウェアが直面する可能性のある入力サイズの範囲と比較すると、まったく小さいものです。また、ソフトウェアは天文学的な範囲の入力サイズに直面する可能性があるため、アルゴリズムのビッグオーの複雑さ、つまり基本的なスケーリングの性質が実装の詳細よりも優先される可能性があります。

正規のソートの例を考えてみましょう。バブルソートは O(n2) 一方、マージソートは O(n log n) です。バブル ソートを使用するアプリケーション A とマージ ソートを使用するアプリケーション B の 2 つの並べ替えアプリケーションがあるとします。また、入力サイズが約 30 要素の場合、アプリケーション A はアプリケーション B よりも並べ替えが 1,000 倍高速であるとします。30 要素をはるかに超える要素を並べ替える必要がない場合は、これらの入力サイズではアプリケーション A の方がはるかに高速であるため、アプリケーション A を選択する必要があるのは明らかです。ただし、1,000 万個のアイテムを並べ替える必要があることがわかった場合、この場合、アプリケーション B が実際にはアプリケーション A よりも数千倍高速になることが予想されます。これは完全に各アルゴリズムのスケール方法によるものです。

これは、ビッグオーの一般的な種類を説明するときに私がよく使う平易な英語の動物寓話です

どのような場合でも、リストの下位のアルゴリズムよりもリストの上位にあるアルゴリズムを優先します。ただし、より高価な複雑さのクラスに移行するコストは大きく異なります。

O(1):

成長無し。問題がどんなに大きくても、同じ時間で解決できます。これは、放送範囲内にいる人の数に関係なく、一定の距離に放送するには同じ量のエネルギーが必要な放送に似ています。

O(ログ n):

この複雑さは次のようなものと同じです ○(1) ただ少し悪い点を除けば。あらゆる実用的な目的から、これは非常に大きな定数スケーリングと考えることができます。1,000 個の項目を処理する場合と 10 億個の項目を処理する場合の作業量の違いは、わずか 6 分の 1 です。

お(n):

問題を解決するコストは問題の規模に比例します。問題のサイズが 2 倍になれば、解決策にかかるコストも 2 倍になります。ほとんどの問題は、データ入力、ディスク読み取り、ネットワーク トラフィックなどの何らかの方法でコンピュータにスキャンする必要があるため、これは一般に手頃な倍率です。

お(n ログ n):

この複雑さは次のようなものとよく似ています お(n). 。すべての実用的な目的において、この 2 つは同等です。このレベルの複雑さでも、一般的にはスケーラブルであると考えられます。いくつかの仮定を微調整することで、 お(n ログ n) アルゴリズムは次のように変換できます お(n) アルゴリズム。たとえば、キーのサイズを制限すると、ソートが減少します。 お(n ログ n) に お(n).

お(n2):

正方形として成長します。 n 正方形の一辺の長さです。これは、ネットワーク内の全員がネットワーク内の他の全員を知っている可能性がある「ネットワーク効果」と同じ増加率です。成長には費用がかかります。ほとんどのスケーラブルなソリューションでは、かなりの練習をしなければ、このレベルの複雑さのアルゴリズムを使用することはできません。これは一般に、他のすべての多項式の複雑さに当てはまります。 お(nk) - 同じように。

O(2n):

スケーリングされません。自明ではない規模の問題を解決する見込みはありません。何を避けるべきかを知るのに役立ち、専門家がどのようなアルゴリズムに含まれるかを見つけるのに役立ちます。 お(nk).

ビッグOは、アルゴリズムは、その入力の大きさに比べて使用していますどのくらいの時間/空間の尺度です。

このアルゴリズムは、O（n）は、時間/空間は、その入力と同じ速度で増加するであろう。

の場合 アルゴリズムはO（N 2 ）である場合、

その入力の速度で時間/空間の増加は二乗。

のように。

ソフトウェア プログラムの速度を測定することは非常に難しく、実際に測定してみると、答えは非常に複雑で、例外や特殊なケースが多い場合があります。これは大きな問題です。なぜなら、2 つの異なるプログラムを比較してどちらが「速い」かを調べるときに、これらの例外や特殊なケースはすべて気が散って役に立たないからです。

この役に立たない複雑さの結果、人々はソフトウェア プログラムの速度を可能な限り小さく、最も複雑でない (数学的) 式を使用して記述しようとします。これらの式は非常に大まかな近似です。ただし、少し運が良ければ、ソフトウェアが速いか遅いかという「本質」を捉えることができます。

これらは近似値であるため、大幅に単純化しすぎていることを読者に示す慣例として、式の中で文字「O」(Big Oh) を使用します。(そして、誰もその表現が何らかの形で正確であると誤解しないようにするためです)。

「ああ」を「およそ」または「ほぼ」という意味として読んでも、それほど間違っているわけではありません。(ビッグオーの選択はユーモアを試みたものだったのかもしれないと思います)。

これらの「Big-Oh」式が行おうとしている唯一のことは、ソフトウェアが処理しなければならないデータ量が増加するにつれてソフトウェアがどの程度遅くなるかを説明することです。処理する必要のあるデータの量が 2 倍になった場合、ソフトウェアは作業を完了するまでに 2 倍の時間が必要になりますか?10倍の長さですか？実際には、遭遇する可能性があり、考慮する必要があるビッグオー表現の数は非常に限られています。

いいもの：

  • O(1) 絶え間ない:入力がどれほど大きくても、プログラムの実行には同じ時間がかかります。
  • O(log n) 対数:入力サイズが大幅に増加した場合でも、プログラムの実行時間はゆっくりとしか増加しません。

悪い人：

  • O(n) 線形:プログラムの実行時間は、入力のサイズに比例して増加します。
  • O(n^k) 多項式:- 入力のサイズが増加するにつれて、処理時間は多項式関数としてますます速くなります。

...そして醜いもの：

  • O(k^n) 指数関数的 問題のサイズが中程度に増加した場合でも、プログラムの実行時間は非常に急速に増加します。指数アルゴリズムを使用して小さなデータ セットを処理する場合にのみ実用的です。
  • O(n!) 階乗 プログラムの実行時間は、非常に小さくて取るに足らないと思われるデータセット以外を待つ余裕があるよりも長くなります。

ビッグオーを英語でわかりやすく説明すると何ですか？正式な定義をできる限り少なくし、単純な数学を使用します。

わかりやすい英語での説明 必要 Big-O 表記の場合:

プログラミングするとき、私たちは問題を解決しようとします。私たちがコーディングするものはアルゴリズムと呼ばれます。Big O 表記を使用すると、アルゴリズムの最悪の場合のパフォーマンスを標準化された方法で比較できます。ハードウェアの仕様は時間の経過とともに変化するため、ハードウェアの改善によりアルゴリズムの実行にかかる時間を短縮できます。しかし、アルゴリズムは依然として同じであるため、ハードウェアを交換しても、アルゴリズムがより良くなったり、時間の経過とともに改善されることを意味するものではありません。したがって、さまざまなアルゴリズムを比較して、どちらが優れているかどうかを判断できるようにするために、Big O 表記法を使用します。

わかりやすい英語での説明 何 ビッグオーの記法は次のとおりです。

すべてのアルゴリズムが同じ時間で実行されるわけではなく、入力内のアイテムの数に応じて変化する可能性があります。 n. 。これに基づいて、最悪の場合の分析、つまり実行時間の上限を次のように考えます。 n どんどん大きくなっていきます。私たちは次のことを認識しなければなりません n Big O の表記法の多くがそれを参照しているためです。

簡単な直接的な答えができます：

ビッグOは、そのアルゴリズムの最悪のタイミング/スペースを表します。このアルゴリズムは、その限界を超えて、より多くのスペース/時間がかかることはありません。ビッグOは、極端な場合の時間/スペースの複雑さを表します。

[OK]を、私の2centsます。

ビッグ-O、w.r.t.、プログラムが消費するリソースの増加の率のです問題インスタンスサイズ

リソース：全CPU時間のだろう、最大RAM容量である可能性があります。デフォルトでは、CPU時間を指します。

タグ、問題は "総和を探す" と言います 
int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

問題インスタンス= {5,10,15} ==>問題インスタンスサイズ= 3、反復型ループ= 3

問題インスタンス= {5,10,15,20,25} ==>問題インスタンスサイズ= 5回の反復型ループ= 5

のサイズを入力するための「N」プログラムは、アレイ内の「n」は反復の速さで成長しています。したがってビッグOは、O（N）

のようにNを発現しています

タグ、問題は "コンビネーションを探す" と言います 
    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

問題インスタンス= {5,10,15} ==>問題インスタンスサイズ= 3、総反復= 3 * 3 = 9

問題インスタンス= {5,10,15,20,25} ==>問題インスタンスサイズ= 5、総反復= 5 * 5 = 25

のサイズを入力するための「N」プログラムは、アレイ内の「n * n」は反復の速さで成長しています。したがってビッグOは、Nは 2 O（N 2 ）

のように表現されます

ランダウの記号は、スペースや走行時間的にアルゴリズムの上限を記述する方法です。 nは、問題の要素の数（アレイのサイズすなわち、ツリー内のノードの数、等）我々は、nが大きいにつれて走行時間を説明することに興味があるである。

私たちは、いくつかのアルゴリズムはO（F（N））であると言うとき、私たちが実行した時間（またはスペースが必要）と言っているそのアルゴリズムによっては、常にいくつかの定数倍（n）をfより低くなっています。

あなたは常にバイナリサーチの実行中の時間よりも大きくなることにより、ログ（n）を掛けることができ、いくつかの定数cが存在するということであるバイナリ検索はO（LOGN）の走行時間を持っていると言うこと。この場合、あなたは常にログ（n）は比較のいくつかの一定の係数を持つことになります。

G（n）は、あなたのアルゴリズムの実行時間はある言い換えれば、我々はそのG（N）= O（F（n））はG（N）<= C *とのF（N）>言いますK、C、kは、いくつかの定数である。

"ビッグオーを英語でわかりやすく説明すると何ですか？できるだけ正式な定義が少なく、単純な数学。"

このように美しく単純で短い質問には、少なくとも、生徒が個別指導中に受ける場合と同様に、同様に短い回答が与えられるに値すると思われます。

Big O表記は、単にアルゴリズムがどのくらいの時間を実行できるかを単純に示します。 入力データ量のみ**.

( *素晴らしいことに、 ユニットフリー 時間の感覚！）
(**それが重要です。なぜなら、人々はそうするからです。 いつも もっと欲しい, 、彼らが今日生きているか、明日生きているか）

では、Big O 記法がそうするのであれば、何がそんなに素晴らしいのでしょうか?

  • 実際的に言えば、Big O 分析は次のとおりです。 とても便利で重要です なぜなら、Big O はアルゴリズムに真正面から焦点を当てているからです。 自分の 複雑かつ完全に 無視する JavaScript エンジン、CPU の速度、インターネット接続など、単なる比例定数にすぎないものはすべて、モデルと同じくらいすぐに時代遅れになってしまいます。 T. 。Big O は、現在または将来に生きる人々にとって同等に重要な点でのみパフォーマンスに焦点を当てます。

  • Big O 記法は、コンピューター プログラミング/エンジニアリングの最も重要な原則、つまりすべての優れたプログラマーに思考と夢を持ち続けるよう促す事実にも直接スポットライトを当てています。テクノロジーのゆっくりとした前進を超えて結果を達成する唯一の方法は、 より良いアルゴリズムを発明する.

アルゴリズムの例 (Java): 

// given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

アルゴリズムの説明:

  • このアルゴリズムはリストを項目ごとに検索し、キーを探します。

  • リスト内の各項目を反復処理し、それがキーの場合は True を返します。

  • キーが見つからないままループが終了した場合は、False を返します。

Big-O 表記は複雑さ (時間、空間、...) の上限を表します。

The Big-O の時間複雑性を見つけるには:

  • 最悪の場合にかかる時間 (入力サイズに関して) を計算します。

  • 最悪の場合：キーがリストに存在しません。

  • 時間(最悪の場合) = 4n+1

  • 時間：o（4n+1）= o（n）| BIG-Oでは、定数は無視されます

  • O(n) ~ リニア

ベストケースの複雑さを表す Big-Omega もあります。

  • 最良の場合：キーは最初の項目です。

  • 時間(ベストケース) = 4

  • 時間：Ω(4) = O(1) ~ 瞬間\定数

ビッグオー

f(x) = O(g(x)) x が a になるとき (たとえば、a = +∞)、関数があることを意味します k そのような：

  1. f(x) = k（バツ）g（バツ）

  2. k は a の近傍で制限されます (a = +∞ の場合、これは、すべての x > N に対して | となるような数 N と M が存在することを意味します)。k（x）| <m）。

言い換えれば、平易な英語で言うと次のようになります。 f(x) = O(g(x))、x → a は、a の近傍で、 f の積に分解される g そしていくつかの制限された関数。

小○

ちなみに比較のために小さいoの定義を載せておきます。

f(x) = o(g(x)) x が a になるときは、次のような関数 k があることを意味します。

  1. f(x) = k（バツ）g（バツ）

  2. kx が a になると (x) は 0 になります。

例

  • x → 0 の場合、sin x = O(x)。

  • sin x = O(1) x → +∞ の場合、

  • バツ2 + x = O(x) x → 0 の場合、

  • バツ2 + x = O(x2) x → +∞ の場合、

  • x → +∞ の場合、ln(x) = o(x) = O(x)。

注意！ 等号「=」を使用した表記は「偽の等価性」を使用します。o(g(x)) = O(g(x)) であることは真ですが、O(g(x)) = o(g(x)) であることは偽です。同様に、「x → +∞ のとき ln(x) = o(x)」と書いても問題ありませんが、「o(x) = ln(x)」という公式は意味を持ちません。

他の例

  • O(1) = O(n) = O(n2) n → +∞ の場合 (ただし、その逆はなく、等式は「偽」です)、

  • O(n) + O(n2) = O(n2) n → +∞の場合

  • O(O(n2)) = O(n2) n → +∞の場合

  • の上2）の上3) = O(n5) n → +∞の場合

ウィキペディアの記事は次のとおりです。 https://en.wikipedia.org/wiki/Big_O_notation

ランダウの記号は、アルゴリズムは、我々は「n」を呼ぶことにします入力パラメータ、任意の数を与え走らますどのように迅速に記述する方法です。異なるマシンが異なる速度で動作し、単にあなたが4.5 GHzのオクトコアプロセッサを搭載したシステムを実行することができる一方で、私が実行している可能性があるため、アルゴリズムははるかにあなたを教えてくれない5秒かかることを言っているのでそれはコンピュータサイエンスに有用です関係なく、アルゴリズムの時間がかかる可能性が15歳、800 MHzのシステム。だからではなく、アルゴリズムは時間的に実行されますどのくらいの速指定する、我々はそれが入力パラメータ、または「N」の数の点で実行されますどのくらいの速言います。このようにアルゴリズムを記述することにより、我々は考慮にコンピュータ自体の速度を取ることなく、アルゴリズムの速度を比較することができます。

私はかつて<のhref = "http://rob-bell.net/2009/06/a-beginners-guide-toが見つかりました：私はさらに、対象に貢献するが、それでも、私は共有したいと思っています。

わかりません-big-O-表記/」relが= "noreferrer">ビッグO上のいくつかの非常に便利（ただし、非常に基本的な）説明と用例を持っているためにこのブログの記事でます：

の例を経由して、これは私のべっ甲のような頭蓋骨に裸の基礎を得る助けたので、私はそれはあなたが正しい方向に向かって取得するか、かなり降下10分だと思います。

あなたは大きなOを知っているためにそこにあるすべてを知りたいですか？だから私の操作を行います。

ビッグOの話にだから、私はその中の一つだけのビートを持っている単語を使用します。単語ごとに一つの音。小さな言葉が迅速です。あなたはこれらの単語を知っている、と私たちは1つの音で単語を使用しますI.を行います。彼らは小さい。私はあなたが私たちが使用するすべての単語を知っていると確信しています！

さて、あなたと私は、仕事の話をしてみましょう。ほとんどの時間は、私は仕事が好きではありません。あなたは仕事が好きですか？それはあなたが行うケースかもしれないが、私は私はないと確信しています。

私は仕事に行くのが好きではありません。私は仕事で時間を過ごすのが好きではありません。私は私の方法を持っていた場合、私はちょうど遊ぶのが好き、そして楽しいことをするだろう。あなたは私と同じように感じますか？

今の回で、私は仕事に行かなければなりません。それは悲しいが、本当です。私は仕事で午前ときに、私はルールを持っている：私はあまり仕事をしてみてください。私はできる限りなしの仕事に近いよう。それから私は遊ぶ行く！

そこでここではビッグニュースです：ビッグOは仕事をしないように私を助けることができます！私は大きなO.少ない仕事、より多くの遊びを知っていれば、私は、時間の多くを再生することができます！これは大きなOは私が行うことができますものです。

今、私はいくつかの仕事を持っています。 1、2、3、4、5、6：私はこのリストを持っています。私は、このリスト内のすべてのものを追加する必要があります。

うわー、私は仕事が嫌い。しかしまあ、私はこれをしなければなりません。だからここに私は行くます。

ワンプラス2は、3 ...プラス3が6 ...と4がある...私は知りません。私は失われてしまいました。私は私の頭の中でやることはあまりにも難しいです。私はこの種の仕事のためにあまり気を行います。

それでは、仕事をしないようにしましょう。あなたと私はちょうどそれがいかに難しいかを考えてみましょう。どのくらいの仕事私は6つの数字を追加するために、しなければならないのでしょうか？

まあ、見てみましょう。私は6で追加カウント、すべてのすべてで... 1と2を追加し、3にそれを追加し、4にそれを追加する必要があります。私は6を行う必要があり、これを解決するために追加します。

ここでは、この数学がどれだけ難しいたちに伝えるために、大きなOを来ています。

ビッグOは言う：私たちは6の操作を行う必要があり、これを解決するために追加されます。一つは、1から6までの各事のために、追加します。仕事の六小さなビット...仕事の各ビットが1つの追加されます。

さて、私は今、それらを追加する作業を行うことはありません。しかし、私はそれが可能だろうか難しい知っています。それは、6が追加になります。

ああ、今私はより多くの仕事を持っています。ったく。誰が原料のこの種を作る？！

今、彼らは1から10に追加する私に尋ねます！なぜ私はそれをしますか？私は6に1を追加したくありませんでした。 1から10に追加するには...よく...それはもっと難しいだろう！

これはどのようにはるかに難しいだろうか？どのくらいのより多くの仕事は、私がしなければならないでしょうか？私は、多かれ少なかれのステップが必要ですか？

まあ、私は10をしなければならないだろうと思い... 1から10までの各事のための1つを追加します。テンは半年以上です。私は六から一よりも、1から10まで追加することずっと仕事をしなければならないでしょう！

私は今、追加する必要はありません。私はちょうどそれがずっと追加するかもしれませんどのようにハードに考えてほしいです。そして、私はすぐに私ができるように再生するには、願っています。

1から6に追加するには、それはいくつかの作業です。しかし、あなたは1から10に追加し、参照してくださいか、それはより多くの仕事ですか？

ビッグOは、あなたの友人と私のものです。ビッグOは、私たちは私たちがしなければならないどのくらいの仕事に考えることができますので、私たちは計画を立てることができます。そして、私たちは大きなOと友達であるならば、彼はそれほど難しいことではありません仕事を選ぶ私たちを助けることができます！

今、私たちは、新たな作業を行わなければなりません。大野。私はすべて、この作業のことを好きではありません。

新しい仕事がある：1からnまでのすべてのものを追加します。

。

待って！ Nとは何ですか？私はそれを逃しましたか？あなたは何をnとする？

私に教えていない場合はどうすればnに1から追加することができます

さて、私は何であるかnは知りません。私は言われませんでした。あなたはそうでしたの？番号？しかたがない。だから我々は仕事をすることはできません。やれやれます。

しかし、私たちは今、仕事をしないでしょうが、私たちは知っていたn個あれば、それは、だろういかに難しいかを推測することができます。我々は右、n個の物事を追加する必要がありますでしょうか？もちろん！

今ここに大きなOが来て、彼はこの作品がいかに難しいかを教えてくれる。彼はこう述べています。一つ一つは、O（n）は、1からNまですべてのものを追加します。これらすべてのものを追加するには、[私はn回を追加する必要があります知っている。] [1]これは大きなOです！彼は、それが作品のいくつかの種類を行うことですいかに難しいかを物語っています。

私に、私は大きな、遅い、上司の男のような大きなOを考えます。彼は仕事に思うが、彼はそれをしていません。彼はT」、と言うかもしれません帽子の仕事は。速い」あるいは、彼は、言うかもしれない 『！仕事はとても遅いとハードであることを』しかし、彼は仕事をしません。彼はただの仕事を見て、その後、彼はそれがかかる場合がありますどのくらいの時間を教えてくれる。

私がなぜ大きなO.のための多くは気に？私は仕事が好きではありません！誰もが動作するのが好きありません。我々はすべてのビッグOを愛する理由です！彼は、私たちが動作することができますどのくらいの速を教えてくれる。彼は私たちがどのようにハードワークを考えることができます。

ええとああ、より多くの仕事。さて、仕事をしないようにしましょう。しかし、一歩一歩、のは、それを行うための計画を作成してみましょう。

彼らは私たちに10枚のカードのデッキを与えました。彼らはすべてを混在している：7、4、2、6 ...ないストレートですべて。そして今...私たちの仕事は、それらを並べ替えることです。

Ergh。それは多くの作業のように聞こえる！

どのように我々はこのデッキを並べ替えることができますか？私は計画を持っています。

私は最初から最後まで、デッキを通じて、ペアによるペア、カードの各ペアを見ていきます。 1ペアの最初のカードが大きいと、そのペアの次のカードが小さければ、私はそれらを交換します。そうでなければ、私は次のペアに行く、などのように...とすぐに、デッキが行われます。

デッキが完了したら、

、私が尋ねる：私はそのパスでカードを交換しましたか？もしそうなら、私は上から、もう一度それをすべて行う必要があります。

どこかの時点で、いくつかの時点で、そこにはスワップしないであろう、とデッキの私たちの並べ替えが行われます。だから、多くの仕事！

さて、どのくらいの仕事それは、これらのルールでカードを並べ替えるために、だろうか？

私は10枚のカードを持っています。そして、ほとんどの時間 - 、私は運の多くを持っていない場合 - 。私はデッキを通って上に10のカードスワップで、10回までの全体のデッキ経由するたびに行かなければなりません。

ビッグO、私を助けて！

ビッグOはで来て、言う：Nカードのデッキのために、それをソートするこの方法は、（N平方）Oで時間を行われます。

。

なぜ彼は、n乗と言うのでしょうか？

さて、あなたは、n乗さを知っているn回のn。今、私はそれを得る：Nカードは、デッキを通じてn回かもしれないものまで、チェックしました。すなわち、n個のステップを有する2つのループが、それぞれです。なお、n乗される多くの作業が行われます。確かに多くの作業、！

これは大きなOはそれが仕事をOを取る（N乗）であろうと言うとき、彼は、n鼻の上に、追加乗を意味するものではありません。これは、いくつかのケースのために、いくつかの小さなビットより少ないかもしれません。しかし、最悪の場合には、nの近くにデッキをソートする作業の手順を乗されます。

ビッグOは、私たちの友人である。ここで、

今ここにある。

ビッグOはこれを指摘する：nは大きなにつれて、我々はカードを並べ替えるとき、ジョブがはるかに多くのHARD古いだけ-アドオンこれら-事を仕事より取得します。どのように我々はこれを知っていますか？

nは本当の大きななれば

さて、私たちはnに追加またはN乗かもしれないものを気にしません。

大きなnに対して、n個の二乗は、nよりも大きいます。

ビッグOは、物事を追加するよりも、より困難である事をソートするために私たちにそれを伝えます。 Oは、（N乗）の大きなnに対してO（n）を超えています。それは意味：nは物事を追加nは混合するよりも、n個のものの混合デッキは、より多くの時間を取る必要がありますソートする、本当の大きななれば

。

ビッグOは、私たちのために仕事を解決しません。ビッグOは仕事がどのようにハードを教えてくれる。

私は、カードのデッキを持っています。私はそれらを並べ替えました。あなたは助けました。おかげます。

のカードを並べ替えるために、より高速な方法はありますか？ビッグOは、私たちを助けることができますか？

はい、より高速な方法があります！それは学ぶためにいくつかの時間がかかりますが、それは動作します...そして、それは非常に高速に動作します。あなたもそれを試みるが、各ステップで、あなたの時間がかかるし、あなたの場所を失うことはありませんすることができます。

デッキを並べ替えるには、この新しい方法では、我々は、カードのペアに、我々はしばらく前に行った方法をチェックしません。ここでは、このデッキをソートする新しいルールがあります：

ワン：私たちは今の作業デッキの一部に一枚のカードを選択してください。あなたが好きならあなたは私のための1つを選択することができます。 （私たちはこれを行う最初の時間は、「我々は今に取り組むデッキの一部は」当然の全体のデッキ、である。）

2：私はあなたが選んだそのカードのデッキをスプレイ。このスプレーは何ですか。どのように私はスプレイのですか？まあ、私は1つずつ、ダウンスタートカードから行く、と私はスプレイカードよりも高く、カードを探します。

3：私は最後のカードを上から行く、と私はスプレイカードよりも低いカードを探してください。

私はこれらの2枚のカードが見つかったら、

、私はそれらを交換し、交換するより多くのカードを探しに行きます。それは私があなたには、いくつかのより多くを選んだカード上に2つ、およびスプレイに戻ってください、である。

いくつかの点で、（二から三まで）このループが終了します。この検索の両方の半分がスプレイカードで会うときに終了します。その後、私たちは、あなたがステップ1で選択したカードでデッキを広がっています。さて、スタートの近くにすべてのカードは、スプレイカードよりも低いです。そして終了間際のカードは、スプレイカードよりも高いです。クールなトリック！

フォー（これは楽しい部分です）：私はスプレイカードよりも低い1以上、今二つの小さなデッキを持ち、かつ1より高いです。今私は、各小さなデッキで、1に進みます！それは私が最初に小さなデッキに一段階から開始し、その作業が行われたとき、私は次の小甲板上のステップの一つから始める、と言うことです。

私は部品でデッキを分割し、各部分をソートし、より小さく、より小さく、いくつかの時点で私が行うにはより多くの仕事を持っていません。さて、これはすべてのルールで、ゆっくりと思われるかもしれません。しかし、それは全く遅くはありませんが、私を信頼しています。それは、物事をソートする最初の方法よりもはるかに少ない作品です！

このソートは何と呼ばれていますか？これは、クイックソートと呼ばれています！その種は C.と呼ばれる人間によって作られましたA. R.ホーアはと彼はクイックソートそれを呼びました。さて、クイックソートはすべての時間を使用します！

クイックソートは小さなもので大きなデッキを壊します。それはそれは小さなもので大きなタスクを分割し、言うことです。

うーん。私が思うに、そこにルールがあるかもしれません。大きなタスクを小さくするには、それらを破るます。

このソートはかなり速いです。どのように迅速な？ビッグOは教えてくれる：このソートはOを必要とする（nはn個のログ）の平均場合には、行われることに努めています。

それは最初のソートよりも多かれ少なかれ速い

ですか？ビッグO、助けてください！

最初のソートはOであった（N乗）。しかし、クイックソートはO（n個のnを記録）です。あなたは、nログnは右、大きなnについて、平方未満であることを知っていますか？まあ、それは我々がクイックソートが高速であることを知っている方法です！

あなたがデッキを並べ替える必要がある場合、

、最良の方法は何ですか？さて、あなたがやりたいことができますが、私はクイックソートを選択することになります。

なぜ私はクイックソートを選ぶのですか？私はもちろん、仕事に好きではありません！私は仕事をするとすぐに私はそれを成し遂げることができますように行わたい。

どのように私はクイックソートが少ない作業である知っているのですか？私は、Oは（N Nをログ）（N乗）O未満であることを知っています。 Oのようにクイックソートが少ない作業で、もっと小さいです！

今、あなたは私の友人、彼は私たちがより少ない作業を行うことができますビッグO.を知っています。あなたは大きなOを知っているなら、あなたはあまりにも少ない作業を行うことができます！

あなたは私と一緒にすべてのことを学びました！あなたはとてもスマートです！ありがとうございました！

今その作業が行われ、遊ぼ行こう！

<時間>

[1]：すべてを一度に、1からnまでのすべてのものをカンニングして追加する方法があります。彼は8歳の時にガウスという名前のいくつかの子供はこれを見つけました。私は彼がそれをやったにどのようには私に聞かないでください、しかしそのスマートではないと思います。

アルゴリズムについて話していると仮定します あ, 、サイズのデータ​​セットで何かを行う必要があります n.

それから O( <some expression X involving n> ) 簡単な英語で言うと、次のようになります。

Aを実行する際に不運な場合は、x（n）操作が完了する場合があります。

偶然にも、特定の関数があります (次のように考えてください)。 実装 の X(n)）非常に頻繁に発生する傾向があります。これらはよく知られており、簡単に比較できます (例: 1, Log N, N, N^2, N!, 、など）

話をするときにこれらを比較すると、 あ および他のアルゴリズムを使用すると、演算の数に応じてアルゴリズムを簡単にランク付けできます。 5月 (最悪の場合) 完了する必要があります。

一般に、私たちの目標はアルゴリズムを見つけたり構築したりすることです。 あ 機能を持つように X(n) 可能な限り小さい数値を返します。

時間の複雑さを計算するための最も一般的なメトリックを理解するためのより簡単な方法は、大きなO表記です。これにより、すべての定数要素が削除され、N が無限大に近づくにつれて実行時間を N に関連して推定できるようになります。一般的には次のように考えることができます。

statement;

一定です。ステートメントの実行時間は、N に関係なく変化しません。

for ( i = 0; i < N; i++ )
  statement;

直線的です。ループの実行時間は N に正比例します。N が 2 倍になると、実行時間も長くなります。

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

二次関数です。2 つのループの実行時間は N の 2 乗に比例します。N が 2 倍になると、実行時間は N * N だけ増加します。

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

対数です。アルゴリズムの実行時間は、N を 2 で割ることができる回数に比例します。これは、アルゴリズムが反復ごとに作業領域を半分に分割するためです。

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

N * log ( N ) です。実行時間は対数的な N ループ (反復または再帰) で構成されているため、アルゴリズムは線形と対数の組み合わせになります。

一般に、1 次元のすべての項目で何かを行うことは線形であり、2 次元ですべての項目で何かを行うことは 2 次であり、作業領域を半分に分割することは対数です。他にも 3 次、指数、平方根などの Big O 尺度がありますが、それほど一般的ではありません。Big O 表記は O ( ) と記述されます。ここで はメジャーです。クイックソート アルゴリズムは O ( N * log ( N ) ) として記述されます。

注記：これらのどれも、最良、平均、最悪の場合の対策を考慮していません。それぞれに独自の Big O 表記があります。また、これは非常に単純化した説明であることにも注意してください。Big O が最も一般的ですが、私が示したようにより複雑でもあります。他にもビッグオメガ、リトルオー、ビッグシータなどの表記もあります。おそらく、アルゴリズム分析コース以外ではこれらに遭遇することはないだろう。

ハリー・ポッターを注文したとします。コンプリート 8 フィルム コレクション [Blu-ray] を Amazon から購入し、同時に同じフィルム コレクションをオンラインでダウンロードします。どちらの方法が速いかをテストしたいとします。配達にはほぼ 1 日かかりますが、ダウンロードは約 30 分早く完了しました。素晴らしい！だから、タイトなレースだよ。

『ロード・オブ・ザ・リング』、『トワイライト』、『ダークナイト トリロジー』など、複数の Blu-ray 映画を注文した場合はどうなりますか。すべての映画をオンラインで同時にダウンロードしますか?今回も、配送が完了するまでに 1 日かかりますが、オンライン ダウンロードが完了するまでに 3 日かかります。ネットショッピングの場合、商品の購入数（入力）は納期に影響しません。出力は一定です。これを私たちは呼んでいます ○(1).

オンライン ダウンロードの場合、ダウンロード時間はムービー ファイル サイズ (入力) に直接比例します。これを私たちは呼んでいます の上）.

実験から、オンライン ショッピングはオンライン ダウンロードよりも拡張性が高いことがわかりました。ビッグ O 表記法を理解することは、分析に役立つため非常に重要です。 スケーラビリティ そして 効率 アルゴリズムの。

注記： Big O 表記は、 最悪のシナリオ アルゴリズムの。それを仮定しましょう ○(1) そして の上） は、上記の例の最悪のシナリオです。

参照 : http://carlcheo.com/compsci

あなたがあなたの頭の中で無限の、適切な概念を持っている場合は、

は、その後、非常に簡単な説明があります：

  

ランダウの記号は、あなたの無限大問題を解決するためのコストを伝えます。

、さらに

  

定要因は無視できる

あなたは倍の速あなたのアルゴリズムを実行することができ、コンピュータにアップグレードする場合は、

、ランダウの記号はそれを気付くことはありません。一定の係数の改善にも大きなO記法で扱う規模で注目されるには小さすぎます。これは大きなO記法の設計の意図的な一部であることに注意してください。

一定の係数よりも「大きい」何かを検出することができるが、しかし

場合は、サイズが十分にほぼ無限大と考えることが「大」である計算をすることに興味を持って、その後、大きなO記法は約あなたの問題を解決するための費用です。

<時間> 上記は意味がない場合は、

、あなたはあなたの頭の中で無限の互換性のある直感的な概念を持っていない、とあなたはおそらく、上記のすべてを無視してください。私は、彼らがまだ直感的に有用ではない場合、これらのアイデアは厳格にするために、またはそれらを説明するために知っている唯一の方法は、最初にあなたに大きなO記法または類似した何かを教えることです。 （あなたも、将来的に大きなO記法を理解すれば、けれども、それはこれらのアイデアを再検討する価値があるかもしれません）。

「Big O」表記を英語でわかりやすく説明すると何ですか？

非常に簡単なメモ:

「Big O」の O は「Order」（正確には「order of」）を指します。
したがって、文字通り、比較するために何かを注文するために使用されるという考えを理解することができます。

  • 「Big O」は 2 つのことを行います。

    1. タスクを達成するためにコンピュータが適用する方法のステップ数を推定します。
    2. それが良いかどうかを判断するために、他のものと比較するプロセスを促進しますか?
    3. 「ビッグオー」は上記2つを標準化で実現します Notations.

  • 最もよく使われる表記法は 7 つあります

    1. O(1) は、コンピュータがタスクを実行することを意味します。 1 ステップ、素晴らしいです、注文番号No.1
    2. O(logN) は、コンピュータが次のタスクを完了したことを意味します。 logN ステップ、それは良いです、注文番号 2
    3. O(N)、タスクを終了してください N ステップ、それは公平です、注文番号 3
    4. O(NlogN)、タスクを終了します O(NlogN) ステップ、それは良くありません、注文番号 4
    5. O(N^2)、タスクを完了してください N^2 ステップ、悪いです、注文番号 5
    6. O(2^N)、タスクを完了します 2^N ステップ、ひどいです、注文番号 6
    7. O(N!)、タスクを完了してください N! ステップ、ひどいです、注文番号 7

enter image description here

表記を取得したとします O(N^2), 、この方法ではタスクを達成するのに N*N のステップが必要であることが明らかなだけでなく、それが適切ではないこともわかります。 O(NlogN) そのランキングから。

理解を深めるために、行末の順序に注意してください。すべての可能性を考慮すると、7 つ以上の表記があります。

CS では、タスクを達成するための一連の手順をアルゴリズムと呼びます。
用語では、アルゴリズムのパフォーマンスや複雑さを説明するために Big O 表記が使用されます。

さらに、Big O は最悪のケースを確立するか、上限ステップを測定します。
最良の場合については、Big-Ω (Big-Omega) を参照してください。

big-ω（big-omega）表記（記事）|カーンアカデミー

  • まとめ
    「Big O」はアルゴリズムのパフォーマンスを説明し、評価します。

    または正式に対処する場合、「Big O」はアルゴリズムを分類し、比較プロセスを標準化します。

最も簡単な見方（平易な英語で）

入力パラメーターの数がアルゴリズムの実行時間にどのような影響を与えるかを確認しようとしています。アプリケーションの実行時間が入力パラメーターの数に比例する場合、それは n の Big O にあると言われます。

上記の記述は出発点としては適切ですが、完全に真実ではありません。

より正確な説明（数学的）

仮定する

n=入力パラメータの数

T(n)= アルゴリズムの実行時間を n の関数として表す実際の関数

c= 定数

f(n)= アルゴリズムの実行時間を n の関数として表す近似関数

次に、Big O に関する限り、以下の条件が真である限り、近似 f(n) は十分に良好であると考えられます。

lim     T(n) ≤ c×f(n)
n→∞

nは、nがnのtに近づくと、nのc時間以下であるように読み取られます。

ビッグオー記法では、これは次のように書かれます。

T(n)∈O(n)

これは、n の T が n の大きな O にあると読みます。

英語に戻る

上記の数学的定義に基づいて、アルゴリズムが n のビッグ オーであると言う場合、それは n (入力パラメーターの数) の関数であることを意味します。 またはそれより速い. 。アルゴリズムが n の Big O である場合、それは自動的に n 平方の Big O にもなります。

n の Big O は、私のアルゴリズムが少なくともこれと同じ速度で実行されることを意味します。アルゴリズムの Big O 表記を見て、遅いと言うわけにはいきません。速いとしか言​​えません。

チェック これ カリフォルニア大学バークレー校の Big O に関するビデオチュートリアルをご覧ください。それは実際には単純な概念です。シューチャック教授（別名神レベルの先生）の説明を聞いたら、「ああ、それだけだ！」と思うでしょう。

私は特に数学にあまりいない誰かのために大きなO記法については本当に偉大な説明を見つけます。

ます。https：// rob- bell.net/2009/06/a-beginners-guide-to-big-o-notation/する

  

ランダウの記号は、パフォーマンスを記述するためにコンピュータサイエンスで使用されています   またはアルゴリズムの複雑さ。ビッグOは、具体的に説明します   最悪のシナリオ、および実行時間を記述するために使用することができます   必要またはスペースはによって（例えば、メモリまたはディスク上に）使用   アルゴリズムます。

     プログラミングの真珠やその他のコンピュータサイエンスを読んだ

誰も   書籍や数学の基礎を持っていませんが、壁にヒットしているだろう   彼らは一見O（N Nを記録）、または他のはもちろんの章に達したとき   クレイジー構文。うまくいけば、この記事はあなたが得るのに役立ちます   ビッグOと対数の基本を理解する。

     

プログラマとして第一及び第二の数学（または多分第三又は   第四）私はビッグOを理解する最良の方法を徹底的にしました   コード内のいくつかの例を生成します。だから、以下のいくつかの一般的な注文があります   説明と例とともに成長可能な限ります。

     

O（1）

     

O（1）常に同じ時間に実行されるアルゴリズムを説明します   （または空間）に関係なく、入力データセットのサイズの

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null; } O(N)
     

O（N）

     

O（N）は、その性能を直線的に成長するアルゴリズムを説明し、   入力データセットの大きさに正比例しました。例   以下もビッグOは、最悪の場合のパフォーマンスを優先する方法を示しています   シナリオ;一致する文字列は、任意の反復中に見つけることができます   forループと機能が早期に返すだろうが、ランダウの記号がします   常にアルゴリズムが実行されます上限を想定   反復の最大数。

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
}
     

O（N 2 ）

     

O（N 2 ）は、その性能に直接されるアルゴリズムを表します   入力データ・セットのサイズの二乗に比例します。これは   データ上で反復を入れ子に伴うアルゴリズムと共通   セットする。深くネストされた反復はO（N 3 ）、O（N 4 ）などになります。

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}
     

O（2 N ）

     

O（2 N ）は、その成長に各additonと倍増アルゴリズムを表します   入力データ・セット。 O（2 N ）関数の成長曲線であります   指数 - meteorically上昇し、その後、非常に浅いオフ開始。アン   O（2 N ）関数の例は、フィボナッチの再帰的計算であります   数値ます：

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}
     

対数

     

対数はので、私は一般的に使用します説明するために、少しトリッキーです   例：

     

バイナリサーチは、ソートされたデータ・セットを検索するために使用される技術です。できます   データセットの中間要素を選択することによって、本質的に   中央値は、目標値と比較します。値がそれと一致した場合   成功を返します。目標値は、の値よりも高い場合   プローブエレメントは、データ・セットの上半分がかかりますし、   それに対して同じ操作を実行します。同様に、もし目標値   それが実行するプローブ要素の値よりも低いです   下半分に対する操作。これは、データを半減していきます   それができるようになるまで値が発見されるまで反復ごとに設定しますか、   もはやデータセットを分割します。

     

アルゴリズムのこのタイプは、O（Nログ）として記載されています。反復半減   バイナリサーチ例で説明したデータセットの成長を生成します   初めにピークに達し、ゆっくりとサイズのようにして平らに曲線   データセットは、例えば、増加します10個の項目を含む入力データセット   100個のアイテムを含むデータセットを取り、完了するまでに1秒を要します   2秒、3を取る千個のアイテムを含むデータセット   秒。 DOU入力データ・セットのサイズをブリンブリンすることにほとんど影響を与えません   アルゴリズムデータセットの1回の反復後など、その成長   設定された入力データと同等の半減ため、されます半分   サイズ。これは、バイナリサーチのようなアルゴリズムは非常に効率的になります   大規模データセットを扱うときます。

これは非常に単純化した説明ですが、私はそれが最も重要な詳細をカバーして願っています。

のは、それNおよびXを作ってみましょう例えば、の問題に対処するあなたのアルゴリズムは、いくつかの「要因」に依存して言ってみましょう。

NとXに応じて、あなたのアルゴリズムは、それが3(N^2) + log(X)操作だ最悪の場合には、たとえば、いくつかの操作が必要になります。

ビッグ-Oは、一定の係数（別名3）についてはあまり気にしないので、あなたのアルゴリズムのビッグOはO(N^2 + log(X))です。それは基本的に「あなたのアルゴリズムは、最悪の場合に必要な演算量はこれでスケール」翻訳ます。

序文

アルゴリズム:問題を解決するための手順/公式

アルゴリズムをどのように分析し、アルゴリズムを相互に比較するにはどうすればよいですか?

例： あなたと友人は、0 から N までの数値を合計する関数を作成するように求められます。あなたは f(x) を思いつき、友人は g(x) を思いつきます。どちらの関数も結果は同じですが、アルゴリズムが異なります。当社が使用するアルゴリズムの効率を客観的に比較するため ビッグオー表記.

ビッグオー表記: 説明します 入力が任意に大きくなったときに、実行時間が入力に対してどれだけ早く増加するか。

3 つの重要なポイント:

  1. 比較する ランタイムの増加速度 ない 正確な実行時間を比較する (ハードウェアに依存します)
  2. 入力に対する実行時間の増加のみを考慮する (n)
  3. として n は任意に大きくなります。n が大きくなるにつれて (無限大と考えてください) 最も速く増加する項に焦点を当てます。別名 漸近分析

空間の複雑さ: 時間の計算量とは別に、空間の計算量 (アルゴリズムが使用するメモリ/スペースの量) も考慮します。操作時間をチェックする代わりに、メモリ割り当てのサイズをチェックします。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top