正式な定義はできるだけ少なく、簡単な数学を好む.
質問する
767624 次
43 に答える
6932
簡単に言うと、私の答えはほぼ確実に、Big Oh 表記(上限) と Big Theta 表記 "Θ" (両側境界) を混同しています。しかし、私の経験では、これは実際には非学術的な設定での議論の典型です. 混乱を招きましたことをお詫び申し上げます。
BigOh の複雑さは、次のグラフで視覚化できます。
Big Oh表記について私が与えることができる最も簡単な定義は次のとおりです。
Big Oh 記法は、アルゴリズムの複雑さを相対的に表したものです。
その文には、いくつかの重要で意図的に選択された単語があります。
- relative:リンゴとリンゴのみを比較できます。算術乗算を行うアルゴリズムを、整数のリストをソートするアルゴリズムと比較することはできません。しかし、算術演算 (1 つは乗算、1 つは加算) を行う 2 つのアルゴリズムを比較すると、意味のあることがわかります。
- 表現: BigOh (最も単純な形式) は、アルゴリズム間の比較を 1 つの変数に減らします。その変数は、観測または仮定に基づいて選択されます。たとえば、並べ替えアルゴリズムは通常、比較操作 (2 つのノードを比較して相対的な順序を決定する) に基づいて比較されます。これは、比較が高価であることを前提としています。しかし、比較は安くても、スワップが高価な場合はどうでしょうか? 比較を変更します。と
- 複雑さ: 10,000 個の要素を並べ替えるのに 1 秒かかる場合、100 万個の要素を並べ替えるのにどれくらいの時間がかかるでしょうか? この場合の複雑さは、他のものに対する相対的な尺度です。
残りを読んだら、戻ってきて上記を読み直してください。
私が考えることができる BigOh の最も良い例は、算術を行うことです。2 つの数字 (123456 と 789012) を取ります。学校で学んだ基本的な算術演算は次のとおりです。
- 添加;
- 減算;
- 乗算; と
- 分割。
これらはそれぞれ操作または問題です。これらを解く方法をアルゴリズムと呼びます。
追加は最も簡単です。数字を (右に) 並べて列に数字を追加し、その追加の最後の数字を結果に書き込みます。その数の「十」の部分は、次の列に繰り越されます。
これらの数値の加算が、このアルゴリズムで最もコストのかかる操作であると仮定しましょう。これらの 2 つの数字を足し合わせるには、6 桁を足し合わせる必要があります (7 桁になる可能性もあります)。100 桁の数を 2 つ足すと、100 回足す必要があります。10,000 桁の数を2 つ足すと、 10,000 回足す必要があります。
パターンが見えますか？複雑さ(操作の数) は、大きい方の桁数nに正比例します。これをO(n)または線形複雑度と呼びます。
減算も同様です (ただし、キャリーの代わりに借りる必要がある場合があります)。
乗算は異なります。数字を並べて、一番下の数字の最初の数字を取り、それを一番上の数字の各数字に対して順番に掛けます。したがって、2 つの 6 桁の数を掛けるには、36 回の掛け算を行う必要があります。最終結果を得るためにも、10 または 11 の列を追加する必要がある場合があります。
100 桁の数字が 2 つある場合、10,000 回の乗算と 200 回の加算を行う必要があります。2 つの 100 万桁の数字の場合、1 兆 (10 12 ) 回の乗算と 200 万回の加算を行う必要があります。
アルゴリズムは n の2 乗でスケーリングされるため、これはO(n 2 )または2 次複雑度になります。ここで、もう 1 つの重要な概念を紹介します。
複雑さの最も重要な部分だけを気にします。
鋭い人は、操作の数を n 2 + 2nのように表現できることに気付いたかもしれません。しかし、それぞれが 100 万桁の 2 つの数字を持つ例からわかるように、第 2 項 (2n) は重要ではなくなります (その段階までの合計操作の 0.0002% を占めます)。
ここで最悪のシナリオを想定していることに気付くでしょう。6 桁の数を掛ける場合、そのうちの 1 つが 4 桁で、もう 1 つが 6 桁の場合、掛け算は 24 回しかありません。それでも、その「n」の最悪のシナリオ、つまり両方が 6 桁の場合を計算します。したがって、Big Oh 表記は、アルゴリズムの最悪のシナリオに関するものです。
電話帳
私が考えることができる次の最良の例は電話帳で、通常はホワイトページまたは類似のものと呼ばれますが、国によって異なります. しかし、私が話しているのは、姓の次にイニシャルまたは名、場合によっては住所、そして電話番号の順で人をリストするものです。
1,000,000 の名前を含む電話帳で "John Smith" の電話番号を検索するようにコンピューターに指示するとしたら、どうしますか? S がどこまで始まったかを推測できるという事実を無視して (推測できないと仮定しましょう)、どうしますか?
典型的な実装は、真ん中まで開き、500,000番目を取り、それを「スミス」と比較することです。それがたまたま「スミス、ジョン」だったら、本当にラッキーだった。「John Smith」がその名前の前後にある可能性がはるかに高いです。それが後である場合は、電話帳の後半を半分に分割して繰り返します。それより前であれば、電話帳の前半を半分に分割して繰り返します。等々。
これは二分探索と呼ばれ、意識しているかどうかにかかわらず、プログラミングで毎日使用されています。
したがって、100 万の名前の電話帳から名前を見つけたい場合、これを最大 20 回実行するだけで実際に任意の名前を見つけることができます。検索アルゴリズムを比較する際に、この比較が「n」であると判断します。
- 3 つの名前の電話帳の場合、(多くても) 2 回の比較が必要です。
- 7 の場合、最大で 3 つかかります。
- 15 の場合は 4 かかります。
- …</li>
- 1,000,000の場合、20かかります。
それは驚くほど良いですね。
BigOh の用語では、これはO(log n)または対数複雑度です。問題の対数は、ln (底 e)、log 10、log 2、またはその他の底になる可能性があります。O(2n 2 ) と O(100n 2 ) が両方とも O(n 2 )であるように、O(log n) でもかまいません。
この時点で、BigOh を使用してアルゴリズムで 3 つのケースを判断できることを説明する価値があります。
- 最良のケース:電話帳検索では、1 回の比較で名前が見つかるのが最良のケースです。これはO(1)または一定の複雑さです。
- 予想されるケース:上で説明したように、これは O(log n) です。と
- 最悪のケース:これも O(log n) です。
通常、最良のケースは気にしません。予想される最悪のケースに関心があります。場合によっては、これらのいずれかがより重要になります。
電話帳に戻ります。
電話番号を持っていて、名前を知りたい場合はどうしますか? 警察は逆電話帳を持っていますが、そのような検索は一般大衆には拒否されています。それとも彼らですか？技術的には、通常の電話帳の番号を逆引きすることができます。どのように？
最初の名前から始めて、番号を比較します。一致すればOK、一致しなければ次へ進みます。電話帳は（とにかく電話番号順で）順序付けされていないため、このようにする必要があります。
電話番号から名前を検索するには (逆引き):
- 最良のケース: O(1);
- 予想されるケース: O(n) (500,000 の場合); と
- 最悪の場合: O(n) (1,000,000)。
巡回セールスマン
これは、コンピュータ サイエンスでは非常に有名な問題であり、言及する価値があります。この問題では、N 個の町があります。これらの町のそれぞれは、一定距離の道路で 1 つ以上の他の町とつながっています。巡回セールスマン問題は、すべての町を訪れる最短のツアーを見つけることです。
シンプルに聞こえますか？もう一度考えてみて。
A、B、C の 3 つの町があり、すべてのペアの間に道路がある場合は、次のようになります。
- A→B→C
- A→C→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
- …</li>
- 25！= 25 × 24 × … × 2 × 1 = 15,511,210,043,330,985,984,000,000
- …</li>
- 50！= 50 × 49 × … × 2 × 1 = 3.04140932 × 10 64
したがって、巡回セールスマン問題の BigOh はO(n!)または階乗または組み合わせの複雑さです。
200 の町にたどり着くまでに、宇宙には従来のコンピューターで問題を解決するのに十分な時間が残っていません。
考えるべきこと。
多項式時間
私が簡単に言及したかったもう 1 つの点は、O(n a )の複雑さを持つアルゴリズムは、多項式の複雑さを持つと言われるか、多項式の時間で解けるということです。
O(n)、O(n 2 ) などはすべて多項式時間です。多項式時間では解決できない問題もあります。このため、特定のものが世界で使用されています。公開鍵暗号化はその代表的な例です。非常に大きな数の 2 つの素因数を見つけるのは計算上困難です。そうでなければ、私たちが使用している公開鍵システムを使用できませんでした。
とにかく、BigOh (改訂版) の説明は以上です。
于 2009-01-28T11:18:57.817 に答える
778
入力サイズに基づいてアルゴリズムがどのようにスケーリングするかを示します。
O(n 2 ) :二次複雑度として知られる
- 1アイテム：1操作
- 10項目：100回
- 100アイテム：10,000回
項目数は 10 倍に増加しますが、時間は 10 2倍に増加することに注意してください。基本的に、n=10 であるため、O(n 2 )は 10 2であるスケーリング係数 n 2を与えます。
O(n) :線形複雑度として知られる
- 1アイテム：1秒
- 10項目：10秒
- 100件：100秒
今回は項目数が 10 倍に増え、時間も 10 倍になります。n=10 なので、O(n) の倍率は 10 です。
O(1) :一定の複雑さとして知られています
- 1アイテム：1操作
- 10項目：1操作
- 100件：1回の操作
アイテムの数は依然として 10 倍に増加していますが、O(1) の倍率は常に 1 です。
O(log n) :対数複雑度として知られています
- 1アイテム：1操作
- 10項目：2操作
- 100件：3回
- 1000アイテム：4オペレーション
- 10,000アイテム：5オペレーション
計算回数は、入力値の対数だけ増加します。したがって、この場合、各計算に 1 秒かかると仮定すると、入力のログはn所要時間、したがってlog n.
それが要点です。彼らは数学を縮小するので、正確にn 2または彼らが言うものではないかもしれませんが、それがスケーリングの支配的な要因になります.
于 2009-01-28T11:28:23.523 に答える
433
于 2011-07-08T04:46:50.113 に答える
254
編集：簡単な注意、これはほぼ確実にBig O表記（上限）とTheta表記（上限と下限の両方）を混同しています。私の経験では、これは実際、非学術的な設定での議論の典型です。混乱を招きましたことをお詫び申し上げます。
一言で言えば、仕事の規模が大きくなると、完了するのにどのくらいの時間がかかりますか?
明らかに、それは入力として「サイズ」を使用し、出力として「所要時間」のみを使用しています。メモリ使用量などについて話したい場合も同じ考えが適用されます。
乾燥させたい N 枚の T シャツがある例を次に示します。それらを乾燥位置に置くのは信じられないほど速いと仮定します（つまり、人間の相互作用はごくわずかです）。もちろん実生活ではそうではありませんが…
屋外で洗濯ラインを使用する: 無限に広い裏庭があると仮定すると、洗濯物は O(1) 時間で乾きます。どんなにたくさん持っていても、同じ太陽と新鮮な空気を得ることができるので、サイズは乾燥時間に影響しません.
回転式乾燥機の使用: 1 回の積み込みに 10 枚のシャツを入れ、1 時間後に完了します。(実際の数値は無視してください。これらは無関係です。) したがって、50 枚のシャツを乾燥させるには、10 枚のシャツを乾燥させる場合の約5 倍の時間がかかります。
すべてを風通しの良い戸棚に入れる: すべてを 1 つの大きな山に入れ、一般的な暖かさに任せると、真ん中のシャツが乾くまでに長い時間がかかります。詳細を推測したくはありませんが、これは少なくとも O(N^2) であると思われます。洗濯量を増やすと、乾燥時間が速くなります.
「big O」表記の重要な側面の 1 つは、特定のサイズに対してどのアルゴリズムが高速になるかを示していないことです。ハッシュテーブル (文字列キー、整数値) とペアの配列 (文字列、整数) を比較します。文字列に基づいて、ハッシュテーブルまたは配列内の要素のキーを見つける方が速いですか? (つまり、配列の場合、「文字列部分が指定されたキーと一致する最初の要素を見つけます。」) ハッシュテーブルは一般に償却されます (~= "平均") O(1) — 設定が完了すると、約1,000,000 エントリ テーブルの場合と同じように、100 エントリ テーブルのエントリを検索するのと同じ時間です。配列内の要素の検索 (インデックスではなく内容に基づく) は線形です。つまり、O(N) です。平均すると、エントリの半分を調べる必要があります。
これにより、ハッシュテーブルはルックアップの配列よりも高速になりますか? 必ずしも。エントリのコレクションが非常に小さい場合は、配列の方が高速である可能性があります。見ているもののハッシュコードを計算するのにかかる時間で、すべての文字列をチェックできる場合があります。ただし、データセットが大きくなるにつれて、ハッシュテーブルは最終的に配列を打ち負かします。
于 2009-01-28T11:16:57.163 に答える
136
Big O は、入力が大きくなったときの関数の成長動作 (プログラムの実行時間など) の上限を表します。
例:
O(n): 入力サイズを 2 倍にすると、ランタイムが 2 倍になります
O(n 2 ): 入力サイズが実行時の 4 倍の 2 倍の場合
O(log n): 入力サイズが 2 倍になると、実行時間が 1 増加します
O(2 n ): 入力サイズが 1 増えると、実行時間は 2 倍になります
入力サイズは通常、入力を表すために必要なビット単位のスペースです。
于 2009-01-28T11:23:07.620 に答える
109
Big O 表記法は、入力セットのサイズの関数として表される、計算 (アルゴリズム) が完了するまでにかかる時間のおおよその尺度として、プログラマーによって最も一般的に使用されます。
Big O は、入力数の増加に伴って 2 つのアルゴリズムがどれだけスケールアップするかを比較するのに役立ちます。
より正確には、関数の漸近的な動作を表現するためにBig O 記法が使用されます。これは、無限大に近づくにつれて関数がどのように動作するかを意味します。
多くの場合、アルゴリズムの「O」は次のいずれかのケースに該当します。
- O(1) - 入力セットのサイズに関係なく、完了までの時間は同じです。例として、インデックスによる配列要素へのアクセスがあります。
- O(Log N) - 完了までの時間は、log2(n) にほぼ比例して増加します。たとえば、Log2(1024) = 10 および Log2(32) = 5 であるため、1024 項目は 32 項目の約 2 倍の時間がかかります。例として、二分探索木(BST) で項目を見つける場合があります。
- O(N) - 入力セットのサイズに比例してスケーリングする完了までの時間。つまり、入力セットの項目数を 2 倍にすると、アルゴリズムの所要時間は約 2 倍になります。例として、リンクされたリスト内のアイテムの数を数えます。
- O(N Log N) - 完了までの時間は、Log2(N) の結果の項目数倍になります。この例は、ヒープ ソートとクイック ソートです。
- O(N^2) - 完了するまでの時間は、アイテム数の 2 乗にほぼ等しくなります。この例は、バブル ソートです。
- O(N!) - 完了までの時間は、入力セットの階乗です。この例は、巡回セールスマン問題のブルート フォース ソリューションです。
Big O は、入力サイズが無限大に向かって増加するにつれて、関数の成長曲線に意味のある方法で寄与しない要因を無視します。これは、関数に加算または乗算される定数が単純に無視されることを意味します。
于 2011-09-05T16:31:43.940 に答える
88
Big O は、「自分のコードを実行するのにどれくらいの時間/スペースが必要ですか?」という一般的な方法で自分自身を「表現」する方法にすぎません。
O(n)、O(n 2 )、O(nlogn) などをよく見かけますが、これらはすべて単なる表示方法です。アルゴリズムはどのように変化しますか?
O(n) は Big O が n という意味ですが、「n って何!?」と思うかもしれません。さて、「n」は要素の量です。配列内のアイテムを検索するイメージング。各要素を調べて、「正しい要素/アイテムですか?」と確認する必要があります。最悪の場合、アイテムは最後のインデックスにあり、リスト内のアイテムと同じくらい時間がかかったことを意味します。一般的に言うと、「n は与えられた値の量です!」と言えます。 .
したがって、「n 2 」が何を意味するかを理解するかもしれませんが、さらに具体的に言うと、単純で最も単純なソートアルゴリズムがあると考えて遊んでください。バブルソート。このアルゴリズムは、項目ごとにリスト全体を調べる必要があります。
私のリスト
- 1
- 6
- 3
ここでの流れは次のようになります。
- 1 と 6 を比較して、どちらが大きいか? OK 6 は正しい位置にあり、前進しています!
- 6 と 3 を比較すると、3 の方が少ないです。それを動かしましょう。リストが変更されました。今すぐ最初から始める必要があります。
これは On n 2です。リスト内のすべての項目を調べる必要があるため、"n" 個の項目があります。各アイテムについて、すべてのアイテムをもう一度見て比較します。これも「n」なので、すべてのアイテムを「n」回見て、n*n = n 2を意味します。
これがあなたが望むのと同じくらい簡単であることを願っています。
しかし覚えておいてほしいのは、Big O は時間と空間を体験するための手段にすぎないということです。
于 2009-01-28T11:14:21.850 に答える
58
Big O は、アルゴリズムの基本的なスケーリングの性質を表しています。
特定のアルゴリズムについて Big O が教えてくれない情報がたくさんあります。これは骨の折れる部分であり、アルゴリズムのスケーリングの性質に関する情報のみを提供します。具体的には、アルゴリズムのリソース使用 (思考時間またはメモリ) が「入力サイズ」に応じてどのようにスケーリングするかです。
蒸気機関とロケットの違いを考えてみましょう。それらは単に同じものの異なる種類 (たとえば、プリウス エンジンとランボルギーニ エンジンのように) ではなく、根本的に劇的に異なる種類の推進システムです。蒸気エンジンはおもちゃのロケットよりも速いかもしれませんが、蒸気ピストン エンジンは軌道ロケットの速度を達成することはできません。これは、これらのシステムが、特定の速度 (「入力サイズ」) に到達するために必要な燃料 (「リソース使用量」) の関係に関して、異なるスケーリング特性を持っているためです。
なぜこれが重要なのですか？ソフトウェアは、サイズが最大 1 兆倍も異なる可能性がある問題を処理するためです。ちょっと考えてみてください。月への移動に必要な速度と人間の歩行速度の比率は 10,000:1 未満であり、ソフトウェアが直面する可能性のある入力サイズの範囲と比較すると、非常に小さいものです。また、ソフトウェアは入力サイズが天文学的な範囲に直面する可能性があるため、アルゴリズムが非常に複雑になる可能性があります。これは基本的なスケーリングの性質であり、実装の詳細よりも優先されます。
正規ソートの例を考えてみましょう。バブルソートは O(n 2 ) ですが、マージソートは O(n log n) です。バブル ソートを使用するアプリケーション A とマージ ソートを使用するアプリケーション B の 2 つの並べ替えアプリケーションがあるとします。入力サイズが約 30 要素の場合、アプリケーション A は並べ替えでアプリケーション B よりも 1,000 倍高速であるとします。30 を超える要素を並べ替える必要がない場合は、これらの入力サイズではるかに高速であるため、アプリケーション A を優先する必要があることは明らかです。ただし、1,000 万個のアイテムを並べ替える必要がある場合は、アプリケーション B がアプリケーション A よりも数千倍高速になることを期待できます。これは、完全に各アルゴリズムのスケーリング方法によるものです。
于 2009-01-28T13:12:24.403 に答える
45
Big-O の一般的な種類を説明するときに私がよく使う平易な英語の寓話集を次に示します。
いずれの場合も、リストの下位にあるアルゴリズムよりも上位にあるアルゴリズムを優先します。ただし、より高価な複雑性クラスに移行するコストは大きく異なります。
O(1):
成長無し。どんなに大きな問題でも、同じ時間で解決できます。これは、ブロードキャスト範囲内にいる人の数に関係なく、特定の距離をブロードキャストするのに同じ量のエネルギーが必要なブロードキャストにいくらか似ています。
O(ログn ):
この複雑さはO(1)と同じですが、少し悪いだけです。実際には、これを非常に大きな一定のスケーリングと見なすことができます。1,000 個のアイテムを処理する場合と 10 億個のアイテムを処理する場合の作業の違いは、わずか 6 分の 1 です。
O( n ):
問題を解決するためのコストは、問題のサイズに比例します。問題のサイズが 2 倍になると、ソリューションのコストは 2 倍になります。ほとんどの問題は、データ入力、ディスク読み取り、またはネットワーク トラフィックなど、何らかの方法でコンピューターにスキャンインする必要があるため、これは一般的に手頃なスケーリング ファクターです。
O( nログn ):
この複雑さはO( n )とよく似ています。実際には、この 2 つは等価です。このレベルの複雑さは、通常、スケーラブルであると見なされます。仮定を微調整することで、一部のO( n log n )アルゴリズムをO( n )アルゴリズムに変換できます。たとえば、キーのサイズを制限すると、ソートがO( n log n )からO( n )に減少します。
O( n 2 ):
正方形として成長します。ここで、nは正方形の一辺の長さです。これは、ネットワーク内の全員がネットワーク内の他の全員を知っている可能性がある「ネットワーク効果」と同じ成長率です。成長には費用がかかります。ほとんどのスケーラブルなソリューションは、かなりの体操を行わなければ、このレベルの複雑さを持つアルゴリズムを使用できません。これは一般に、他のすべての多項式の複雑さ - O( n k ) - にも当てはまります。
O(2 n ):
スケーリングしません。自明でないサイズの問題を解決する見込みはありません。何を避けるべきかを知り、専門家がO( n k )にある近似アルゴリズムを見つけるのに役立ちます。
于 2014-01-27T23:09:37.870 に答える
38
Big O は、アルゴリズムがその入力のサイズに対してどれだけの時間/空間を使用するかの尺度です。
アルゴリズムが O(n) の場合、時間/空間はその入力と同じ割合で増加します。
アルゴリズムが O(n 2 ) の場合、時間/空間は入力の 2 乗の割合で増加します。
等々。
于 2009-01-28T11:19:29.500 に答える
37
ソフトウェア プログラムの速度を測定することは非常に困難です。試してみると、答えは非常に複雑で、例外や特殊なケースでいっぱいになる可能性があります。これは大きな問題です。なぜなら、2 つの異なるプログラムを比較してどちらが「最速」かを調べたい場合、これらすべての例外と特殊なケースは気が散り、役に立たないからです。
この役に立たない複雑さの結果として、人々はソフトウェア プログラムの速度を可能な限り最小で単純な (数学的) 表現を使用して記述しようとします。これらの式は非常に大雑把な概算ですが、運が良ければ、ソフトウェアの一部が速いか遅いかの「本質」を捉えることができます。
これらは概算であるため、極端な単純化を行っていることを読者に知らせる慣例として、式に文字「O」(ビッグ オー) を使用します。(そして、式が正確であると誰も誤解しないようにするため)。
「おお」を「おおよそ」または「おおよそ」という意味で読んでも、それほど間違いはありません。（Big-Ohの選択はユーモアの試みだったのかもしれません）.
これらの「Big-Oh」表現がやろうとしている唯一のことは、ソフトウェアが処理する必要があるデータの量を増やすと、ソフトウェアがどれだけ遅くなるかを説明することです. 処理する必要があるデータの量を 2 倍にすると、ソフトウェアはその作業を完了するのに 2 倍の時間を必要とするでしょうか? 10倍くらい？実際には、非常に限られた数の Big-Oh 式に遭遇し、心配する必要があります。
いいもの：
O(1)定数: 入力の大きさに関係なく、プログラムの実行には同じ時間がかかります。O(log n)対数: 入力のサイズが大幅に増加しても、プログラムの実行時間はゆっくりとしか増加しません。
悪い人：
O(n)Linear : プログラムの実行時間は、入力のサイズに比例して増加します。O(n^k)多項式: - 入力のサイズが大きくなるにつれて、処理時間は多項式関数としてどんどん速くなります。
...そして醜い：
O(k^n)指数関数プログラムの実行時間は、問題のサイズがわずかに増加しても非常に急速に増加します。指数関数アルゴリズムを使用して小さなデータ セットを処理する場合にのみ実用的です。O(n!)Factorialプログラムの実行時間は、非常に小さくて些細に見えるデータセットを除いて、待機できる時間よりも長くなります。
于 2013-05-29T13:51:20.603 に答える
36
Big Oの分かりやすい英語の説明は何ですか? 可能な限り正式な定義はなく、単純な数学で。
Big-O表記の必要性についての平易な英語の説明：
プログラミングをするとき、私たちは問題を解決しようとしています。私たちがコーディングするものは、アルゴリズムと呼ばれます。Big O 表記を使用すると、標準化された方法でアルゴリズムの最悪の場合のパフォーマンスを比較できます。ハードウェアの仕様は時間の経過とともに変化し、ハードウェアの改善により、アルゴリズムの実行にかかる時間を短縮できます。ただし、ハードウェアを交換しても、アルゴリズムが同じであるため、時間の経過とともにアルゴリズムが改善されたり改善されたりするわけではありません。そのため、異なるアルゴリズムを比較して、どちらが優れているかを判断できるようにするために、Big O 表記を使用します。
Big O Notation とは何かについての平易な英語の説明:
すべてのアルゴリズムが同じ時間で実行されるわけではなく、入力の項目数 ( nと呼びます) によって異なる場合があります。これに基づいて、最悪の場合の分析、またはnがどんどん大きくなるときの実行時間の上限を検討します。Big O 表記の多くは n を参照しているため、nが何であるかを認識しておく必要があります。
于 2013-02-22T01:00:27.490 に答える
32
わかりました、私の 2 セント。
Big-O は、プログラムによって消費されるリソースの増加率であり、問題インスタンスのサイズに関して
リソース : 合計 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」回の反復の速度で成長しています。したがって、Big-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」回の反復の速度で成長しています。したがって、Big-O はO(n 2 )として表される N 2です。
于 2011-08-23T04:06:03.963 に答える
31
簡単で率直な答えは次のとおりです。
Big O は、そのアルゴリズムで考えられる最悪の時間/空間を表します。アルゴリズムは、その制限を超えてより多くのスペース/時間を使用することはありません。Big O は、極端な場合の時間/空間の複雑さを表します。
于 2013-11-13T10:23:28.960 に答える
29
Big O 記法は、スペースまたは実行時間に関してアルゴリズムの上限を記述する方法です。n は問題の要素の数です (つまり、配列のサイズ、ツリー内のノードの数など)。 n が大きくなったときの実行時間を記述することに関心があります。
あるアルゴリズムが O(f(n)) であると言うとき、そのアルゴリズムの実行時間 (または必要なスペース) は常に f(n) の定数倍よりも短いということです。
二分探索の実行時間が O(logn) であるということは、log(n) を掛けることができる定数 c が存在し、常に二分探索の実行時間よりも大きくなるということです。この場合、常に log(n) 比較の一定の係数が得られます。
つまり、g(n) がアルゴリズムの実行時間である場合、g(n) <= c*f(n) の場合、n > k の場合、g(n) = O(f(n)) と言います。 c と k は定数です。
于 2010-07-17T02:29:35.880 に答える
26
アルゴリズムの例 (Java):
public boolean search(/* for */Integer K,/* in */List</* of */Integer> L)
{
for(/* each */Integer i:/* in */L)
{
if(i == K)
{
return true;
}
}
return false;
}
アルゴリズムの説明:
このアルゴリズムは、リストを項目ごとに検索し、キーを探します。
リスト内の各項目を反復処理し、それがキーの場合は True を返します。
キーが見つからないままループが終了した場合は、False を返します。
Big-O 表記は、複雑さ (時間、空間、..) の上限を表します。
The Big-O on Time Complexity を見つけるには:
最悪の場合にかかる時間 (入力サイズに関して) を計算します。
最悪のケース: キーがリストに存在しません。
時間 (最悪の場合) = 4n+1
時間: O(4n+1) = O(n) | Big-O では、定数は無視されます
O(n) ~ 線形
Best-Case の複雑さを表す Big-Omega もあります。
最良のケース: キーは最初の項目です。
時間 (最良の場合) = 4
時間: Ω(4) = O(1) ~ Instant\Constant
于 2013-03-23T15:19:15.313 に答える
21
Big O 記法は、任意の数の入力パラメーター ("n" と呼びます) が与えられた場合に、アルゴリズムがどれだけ速く実行されるかを表す方法です。異なるマシンは異なる速度で動作するため、コンピューター サイエンスで役立ちます。4.5 Ghz オクトコア プロセッサを搭載したシステムを実行している間に、私が実行している可能性があるため、単純にアルゴリズムに 5 秒かかると言ってもあまり意味がありません。 15 年前の 800 Mhz システムで、アルゴリズムに関係なく、さらに時間がかかる可能性があります。したがって、アルゴリズムの実行速度を時間で指定する代わりに、入力パラメーターの数、つまり「n」で実行速度を指定します。このようにアルゴリズムを記述することで、コンピューター自体の速度を考慮しなくても、アルゴリズムの速度を比較することができます。
于 2014-06-25T20:32:59.110 に答える
20
ビッグオー
f (x) = O( g (x)) x が a になるとき (たとえば、a = +∞) は、次のような関数kがあることを意味します。
f (x) = k (x) g (x)
k は a のある近傍で制限されます (a = +∞ の場合、これは、x > N ごとに | k (x)| < M となるような N と M の数があることを意味します)。
言い換えれば、平易な英語で: f (x) = O( g (x)), x → a は、a の近傍で、fがgと何らかの有界関数の積に分解されることを意味します。
小○
ところで、小さい o の定義を比較のために示します。
f (x) = o( g (x)) x が a になるとき、次のような関数 k があることを意味します。
f (x) = k (x) g (x)
x が a になると、 k (x) は 0 になります。
例
x → 0 の場合、sin x = O(x) です。
sin x = O(1) x → +∞のとき、
x 2 + x = O(x) x → 0 の場合、
x 2 + x = O(x 2 ) x → +∞のとき、
x → +∞のとき、ln(x) = o(x) = O(x)。
注意！等号「=」を使用した表記は、「疑似等価」を使用します。o(g(x)) = O(g(x)) は true ですが、O(g(x)) = o(g) は false です。 （バツ））。同様に、「x → +∞ のとき ln(x) = o(x)」と書いても問題ありませんが、「o(x) = ln(x)」という式は意味をなしません。
その他の例
O(1) = O(n) = O(n 2 ) (n → +∞ の場合) (ただし、その逆ではなく、等式は「偽物」です)
O(n) + O(n 2 ) = O(n 2 ) n → +∞の場合</p>
O(O(n 2 )) = O(n 2 ) n → +∞の場合</p>
O(n 2 )O(n 3 ) = O(n 5 ) n → +∞の場合</p>
ウィキペディアの記事は次のとおりです: https://en.wikipedia.org/wiki/Big_O_notation
于 2013-03-15T21:18:33.570 に答える
14
ビッグオーについて知っておくべきことをすべて知りたいですか？私もそうです。
ですから、ビッグオーについて話すには、ビートが 1 つしかない単語を使用します。単語ごとに 1 つの音。小さな言葉は素早い。あなたはこれらの言葉を知っていますし、私もそうです。彼らは小さい。私たちが使用するすべての言葉を知っていると確信しています！
では、あなたと私で仕事の話をしましょう。ほとんどの場合、私は仕事が好きではありません。仕事は好きですか？あなたはそうかもしれませんが、私はそうではないと確信しています。
私は仕事に行くのが好きではありません。私は仕事に時間を費やすのが好きではありません。やりたいことがあるなら、ただ遊んで、楽しいことをしたいです。私と同じように感じますか？
今、時々、私は仕事に行かなければなりません。悲しいですが、本当です。ですから、私が仕事をしているときは、仕事を減らすというルールがあります。私ができる限り仕事はほとんどありません。じゃあ遊びに行きます！
ここで大きなニュースがあります。大きな O は、仕事をしないのに役立ちます。大きなOを知っていれば、もっと遊べます。それがビッグオーが私を助けてくれるものです。
今、仕事があります。私はこのリストを持っています: 1、2、3、4、5、6。このリストにすべてを追加する必要があります。
うーん、仕事嫌い。でもまぁ、これはやらなきゃ。だからここに行きます。
1 足す 2 は 3…足す 3 は 6…そして 4 は…わかりません。迷子になりました。頭の中でやるのは難しすぎる。私はこの種の仕事にはあまり関心がありません。
だから仕事はやめましょう。あなたと私はそれがどれほど難しいか考えてみましょう。6 つの数を足すには、どれだけの作業をしなければならないでしょうか?
さて、見てみましょう。1 と 2 を足して、それを 3 に足してから 4 に足す必要があります。これを解決するには、6 つの追加を行う必要があります。
ここで大きな O が登場し、この数学がいかに難しいかを教えてくれます。
Big O は次のように述べています。これを解決するには、6 つの追加を行う必要があります。1 から 6 までのそれぞれについて、1 つ追加します。6 つの小さな作業...それぞれの作業は 1 つの追加です。
まあ、今はそれらを追加する作業はしません。しかし、私はそれがどれほど難しいかを知っています。それは6つの追加になります。
いやいや、仕事が増えました。おいおい。こんなもの誰が作るの!?
今、彼らは私に1から10まで足すように頼んでいます! なぜ私はそれをするのですか？1 を 6 に追加したくありませんでした。1 から 10 まで足すのは…まあ…それはさらに難しいでしょう!
それはどれほど難しいでしょうか？あとどれくらいの仕事をしなければなりませんか？必要な手順は多いですか、それとも少ないですか?
ええと、私は 10 個の追加を行う必要があると思います... 1 から 10 までの各項目に対して 1 つずつ。10 は 6 以上です。1 から 6 に足すよりも、1 から 10 に足すのにもっと多くの作業が必要です。
今は追加したくありません。それだけ追加するのがどれほど難しいかを考えたいだけです。そして、できるだけ早くプレーできることを願っています。
1 から 6 まで追加するには、多少の作業が必要です。しかし、1 から 10 まで足すと、それはより多くの作業であることがわかりますか?
Big O はあなたの友人であり、私の友人です。Big O は、私たちがしなければならない仕事の量を考えるのを助けてくれるので、計画を立てることができます。そして、私たちがビッグオーと友達なら、彼は私たちがそれほど難しくない仕事を選ぶのを手伝ってくれます!
今、私たちは新しい仕事をしなければなりません。大野。私はこの仕事がまったく好きではありません。
新しい作業は、1 から n までのすべてのものを追加することです。
待って！んとは？私はそれを逃しましたか？n が何か教えてくれなかったら、どうやって n に 1 を足すことができますか?
うーん、nが何かわかりません。言われませんでした。あなたでしたか？いいえ？しかたがない。だから私たちは仕事をすることができません。うわー。
しかし、今はその仕事をしませんが、もし n を知っていたら、それがどれほど難しいかは推測できます。n 個のことを合計しなければなりませんよね？もちろん！
ここに大きなOが来て、この仕事がどれほど難しいかを教えてくれます。彼は次のように言います: 1 から N までのすべてのものを 1 つずつ追加すると、O(n) になります。これらすべてを足すには、[n 回足さなければならないことはわかっています][1] それは大きなおお! 彼はある種の仕事をするのがいかに難しいかを私たちに話します。
私にとって、ビッグ オーは大きくてゆっくりした上司のようなものだと思います。彼は仕事について考えるが、それをしない。彼は「その仕事は速い」と言うかもしれません。あるいは、「その仕事はとても遅くて大変だ！」と言うかもしれません。しかし、彼はその仕事をしません。彼は作品を見て、どれくらいの時間がかかるか教えてくれます。
私は大きなOをとても気にかけています。なぜですか？働きたくない！働くのが好きな人はいません。それが、私たちがビッグオーを愛する理由です！彼は、私たちがどれだけ速く仕事ができるかを教えてくれます。彼は私たちが仕事がどれほど難しいかを考えさせてくれます。
うーん、もっと仕事。さて、仕事はやめましょう。しかし、それを行うための計画を段階的に立てましょう。
彼らは私たちに 10 枚のカードのデッキをくれました。それらはすべて混同されています: 7 つ、4 つ、2 つ、6 つ… まったくまっすぐではありません。そして今...私たちの仕事はそれらを分類することです。
うーん。大変な作業ですね。
このデッキをどのように並べ替えることができますか? 私は計画があります。
カードの各ペアを、ペアごとに、デッキを通して最初から最後まで見ていきます。あるペアの最初のカードが大きく、そのペアの次のカードが小さい場合、それらを交換します。それ以外の場合は、次のペアに進みます...そして、すぐにデッキが完成します。
デッキが完成したら、私は尋ねます: そのパスでカードを交換しましたか? なら、もう一度、上からやり直さなければならない。
ある時点で、ある時点で、スワップがなくなり、私たちのようなデッキが完成するでしょう. たくさんの仕事！
さて、それらのルールでカードを並べ替えるには、どれだけの作業が必要でしょうか?
私は10枚のカードを持っています。そして、ほとんどの場合、つまり、運があまり良くない場合は、デック全体を最大 10 回確認し、毎回最大 10 枚のカードを交換する必要があります。
ビッグオー、助けて！
Big O が来て、次のように言います。
なぜ彼は n の 2 乗と言うのですか?
n の 2 乗は n かける n です。さて、私はそれを理解しました：n枚のカードがチェックされ、デッキをn回通過する可能性があります。これは、それぞれ n ステップの 2 つのループです。これは、やるべき仕事の n の 2 乗です。確かに、たくさんの仕事があります！
さて、大きな O が O(n 二乗) の作業が必要だと言うとき、彼は n 二乗の足し算を意味するのではありません。場合によっては、少し少ないかもしれません。しかし、最悪の場合、デッキを並べ替えるのにほぼ n 乗ステップの作業が必要になります。
ここでビッグオーが私たちの友達です。
Big O は次のように指摘しています。n が大きくなると、カードを並べ替えると、これらをただ追加するだけの古い作業よりもはるかに難しくなります。どうすればこれを知ることができますか?
n が非常に大きくなった場合、n または n の 2 乗に何を足してもかまいません。
大きな n の場合、n の 2 乗は n よりも大きくなります。
Big O は、物を並べ替えるのは、物を追加するよりも難しいことを教えてくれます。O(n 二乗) は、大きな n の O(n) よりも大きくなります。つまり、n が本当に大きくなった場合、n 個の混合物を単に追加するよりも、n 個の混合デッキをソートするのにより多くの時間がかかる必要があります。
Big O は私たちの仕事を解決しません。Big O は仕事の大変さを教えてくれます。
私はトランプを持っています。私はそれらを並べ替えました。あなたは助けました。ありがとう。
カードをすばやく並べ替える方法はありますか? 大きなオーは私たちを助けることができますか?
はい、もっと速い方法があります！習得するのに少し時間がかかりますが、うまくいきます...そしてとても速く動きます。あなたもそれを試すことができますが、各ステップで時間をかけて、あなたの場所を失うことはありません.
デッキをソートするこの新しい方法では、少し前に行った方法でカードのペアをチェックしません。このデッキを並べ替えるための新しいルールは次のとおりです。
1枚：現在取り組んでいるデッキの一部のカードを1枚選びます。よろしければ、私のために 1 つ選んでもかまいません。（もちろん、これを初めて行うときは、「現在取り組んでいるデッキの一部」はデッキ全体です。）
2:あなたが選んだそのカードでデッキを広げます。この広がりは何ですか。どうやってスプレーするの？そうですね、スタートカードから1枚ずつ下に行って、スプレイカードよりも高いカードを探します。
3: エンド カードから上に移動し、スプレイ カードよりも低いカードを探します。
これらの 2 枚のカードを見つけたら、それらを交換し、さらに交換するカードを探します。つまり、ステップ 2 に戻り、あなたが選んだカードにさらにスプレーします。
ある時点で、このループ (2 から 3 へ) が終了します。この検索の両方の半分がスプレイカードで出会うと終了します。次に、ステップ 1 で選択したカードをデッキに広げました。現在、開始近くのすべてのカードは、スプレイ カードよりも低くなっています。終わりに近いカードは、スプレイ カードよりも高くなっています。クールなトリック！
4 (これは楽しい部分です): 私は今、2 つの小さなデッキを持っています。1 つはスプレイ カードよりも低く、もう 1 つは高いです。ステップ 1 に進みます。それぞれの小さなデッキで行います。つまり、最初の小デッキのステップ 1 から開始し、その作業が完了したら、次の小デッキのステップ 1 から開始します。
私はデックをパーツに分解し、各パーツをより小さく、より小さく並べ替えます。すべてのルールを考えると、これは遅いように思えるかもしれません。しかし、私を信じてください、決して遅くはありません。物事を並べ替える最初の方法よりもはるかに少ない作業です!
この種類は何と呼ばれていますか？クイックソートといいます！そのソートはCAR Hoareという男によって作られ、彼はそれを Quick Sort と呼んだ。今、クイックソートは常に使用されています！
クイックソートは、大きなデッキを小さなデッキに分割します。つまり、大きなタスクを小さなタスクに分割します。
うーん。そこにルールがあるのかもしれませんね。大きなタスクを小さくするには、それらを分割します。
このソートは非常に高速です。どのくらい速いですか？Big O は次のことを教えてくれます。
最初のソートより多かれ少なかれ高速ですか？ビッグオー、助けてください！
最初のソートは O(n 二乗) でした。しかし、クイックソートは O(n log n) です。大きな n の場合、n log n は n の 2 乗より小さいことをご存知ですか? これで、クイック ソートが高速であることがわかります。
デッキを並べ替える必要がある場合、最善の方法は何ですか? まあ、あなたはやりたいことをすることができますが、私はクイックソートを選びます.
クイック ソートを選択する理由 もちろん、私は働くのが好きではありません！仕事は出来るだけ早く終わらせたい。
クイック ソートのほうが手間がかからないことはどうすればわかりますか? O(n log n) が O(n 二乗) より小さいことはわかっています。O の方が小さいので、クイック ソートの作業が少なくなります。
さて、私の友人である Big O をご存知でしょう。そして、ビッグオーを知っていれば、仕事を減らすこともできます!
あなたは私と一緒にそれをすべて学びました！あなたはとても賢いです！どうもありがとう！
仕事が終わったら遊びに行こう！
[1]: 1 から n までのすべてのものを一度にすべてごまかして追加する方法があります。ガウスという名前の子供が 8 歳のときにこれを発見しました。私はそれほど賢くないので、彼がどうやってそれをしたのか私に聞かないでください。
于 2015-12-27T10:34:52.030 に答える
13
この件にさらに貢献しているかどうかはわかりませんが、それでも共有したいと思います:このブログ投稿には、Big O に関する非常に役立つ (非常に基本的な) 説明と例があることがわかりました。
例を介して、これはべっ甲のような頭蓋骨に基本的なことを理解するのに役立ちました.
于 2012-09-29T20:54:23.713 に答える
12
時間の複雑さを理解するためのより簡単な方法があります。時間の複雑さを計算するための最も一般的なメトリックは Big O 表記です。これにより、すべての定数要素が削除されるため、N が無限大に近づくにつれて、実行時間が N に関連して推定されます。一般的には、次のように考えることができます。
statement;
定数です。ステートメントの実行時間は、N に関連して変化しません。
for ( i = 0; i < N; i++ )
statement;
線形です。ループの実行時間は N に正比例します。N が 2 倍になると、実行時間も 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 次であり、作業領域を半分に分割することは対数です。立方、指数、平方根などの Big O メジャーは他にもありますが、それほど一般的ではありません。Big O 表記は O ( ) と記述され、ここで は測定値です。クイックソート アルゴリズムは O ( N * log ( N ) ) と記述されます。
注: これはいずれも、最良、平均、および最悪の場合の対策を考慮していません。それぞれに独自の Big O 記法があります。また、これは非常に単純化された説明であることにも注意してください。Big O が最も一般的ですが、私が示したよりも複雑です。他にもビッグオメガ、リトルオー、ビッグシータなどの表記があります。おそらく、アルゴリズム分析コース以外では遭遇しないでしょう。
- 詳細はこちら:こちら
于 2015-01-30T07:00:50.920 に答える
11
頭の中に無限という適切な概念がある場合は、非常に簡単な説明があります。
Big O 表記は、無限大の問題を解決するためのコストを示します。
そしてさらに
定数要因は無視できる
アルゴリズムを 2 倍の速さで実行できるコンピューターにアップグレードすると、大きな O 表記はそれに気付かないでしょう。定数係数の改善は小さすぎて、大きな O 表記が機能するスケールでは気付かれません。これは、大きな O 表記の設計の意図的な部分であることに注意してください。
ただし、一定の係数よりも「大きい」ものは何でも検出できます。
サイズがほぼ無限大と見なされるほど「大きい」計算を行うことに関心がある場合、大きな O 表記は、問題を解決するためのコストとほぼ同じです。
上記が意味をなさない場合は、頭の中に互換性のある直感的な無限の概念がなく、おそらく上記のすべてを無視する必要があります。これらのアイデアを厳密なものにしたり、まだ直感的に役に立たない場合に説明したりする唯一の方法は、最初に Big O 表記法または類似のものを教えることです。(ただし、将来ビッグ O 表記をよく理解したら、これらのアイデアを再検討する価値があるかもしれません)
于 2015-05-16T16:02:02.267 に答える
11
Amazon で Harry Potter: Complete 8-Film Collection [Blu-ray] を注文し、同時に同じ映画コレクションをオンラインでダウンロードするとします。どちらの方法が速いかをテストしたいとします。配信は到着までほぼ 1 日かかり、ダウンロードは約 30 分早く完了しました。すごい！だから、それはタイトなレースです。
ロード オブ ザ リング、トワイライト、ダーク ナイト トリロジーなどのブルーレイ映画をいくつか注文し、すべての映画をオンラインで同時にダウンロードした場合はどうなりますか? 今回は、配信が完了するまでにまだ 1 日かかりますが、オンライン ダウンロードは完了するまでに 3 日かかります。オンラインショッピングの場合、購入数（入力）は納期に影響しません。出力は一定です。これをO(1)と呼びます。
オンライン ダウンロードの場合、ダウンロード時間はムービー ファイルのサイズ (入力) に正比例します。これをO(n)と呼びます。
実験から、オンライン ショッピングはオンライン ダウンロードよりも優れていることがわかっています。アルゴリズムのスケーラビリティと効率を分析するのに役立つため、Big O 表記を理解することは非常に重要です。
注: Big O 表記は、アルゴリズムの最悪のシナリオを表しています。O(1)とO(n)が上記の例の最悪のシナリオであると仮定しましょう。
于 2015-12-06T06:01:13.677 に答える
5
Big O は関数のクラスを記述しています。
大きな入力値に対して関数がどれだけ速く成長するかを説明します。
与えられた関数 f に対して、O(f) は、n >= n0 である g(n) のすべての値が c*f 以下になるように、n0 と定数 c を見つけることができるすべての関数 g(n) を記述します。 (ン)
あまり数学的な言葉ではなく、O(f) は関数のセットです。つまり、ある値 n0 以降のすべての関数は、ゆっくりまたは f と同じくらい速く成長します。
f(n) = n の場合
g(n) = 3n は O(f) にあります。定数係数は問題にならないため、h(n) = n+1000 は O(f) に含まれます。入力が重要です。
ただし、二次関数は線形関数よりも速く成長するため、i(n) = n^2 は O(f) にはありません。
于 2016-10-31T23:57:42.280 に答える
4
平易な英語の Big O は <= (以下) のようなものです。2 つの関数 f と g について、f = O(g) と言うとき、それは f <= g を意味します。
ただし、これは任意の nf(n) <= g(n) についてという意味ではありません。実際に意味することは、成長に関して f が g 以下であるということです。c が定数の場合、ポイントf(n) <= c*g(n)の後であることを意味します。そして、ポイントの後は、n0が別の定数であるすべての n >= n0 よりも意味します。
于 2016-07-04T20:46:32.063 に答える
3
これを 6 歳の子供に説明したい場合は、たとえば関数 f(x) = x と f(x) = x^2 を描き始め、どの関数が一番上の関数になるかを子供に尋ねます。ページ。次に、描画を続行し、x^2 が勝つことを確認します。「誰が勝つか」は、実際には、x が無限大になる傾向があるときに、より速く成長する関数です。したがって、「関数 x は x^2 の Big O にある」ということは、x が無限大になる傾向がある場合、x の成長が x^2 よりも遅くなることを意味します。x が 0 になる傾向がある場合も同じことができます。x に対してこれら 2 つの関数を 0 から 1 まで描くと、x は上位関数になるため、「関数 x^2 は、x が 0 になる傾向がある x の Big O にあります」。子供が年をとるとき、私は、実際に Big O は、より速く成長するのではなく、与えられた関数と同じように成長する関数である可能性があることを付け加えます. また、定数は破棄されます。したがって、2x は x の Big O に含まれます。
于 2015-06-13T15:29:11.090 に答える
3
のような関数があり、無限大に近づいf(n) = n+3たときにグラフがどのように見えるかを知りたい場合n、すべての定数と低次の項を削除するだけnです。ではf(n) = n、なぜこれをそのまま使用できないのでしょうか。なぜ関数の上と下にある関数を探す必要があるのでしょうかf(n) = n+3。大きな O と大きなオメガです。
関数がちょうど無限大に近づいf(n) = nたときであると言うのは正しくないため、正しいために、関数が存在する可能性のある領域を記述します。低次の項と定数はグラフの成長を大幅に変更しないため、グラフが正確にどこにあるかには興味がありません。つまり、上限と下限から囲まれた領域は f(n ) = n+3 関数。nf(n) = n+3
定数項と下位項を単に削除することは、まさに上下にある関数を見つけるプロセスです。
定義上、関数は別の関数の下限または上限であり、関数を掛けることができる定数を見つけてf(n) = n、すべてnの出力が元の関数よりも大きく (または下限の場合は小さく) なります。
f(n) = n*C > f(n) = n+3
はい、そうC = 2するでしょう。したがって、関数は関数f(n) = nの上限になる可能性がありf(x) = x+3ます。
下限についても同じ：
f(n) = n*C < f(n) = n+3
C = -2するだろう
O と Omega の両方が Theta よりも大きい場合、f(x) = nの上限と下限も同様です。これは、しっかりとバインドされていることを意味します。f(x) = x+3
f(x) = x^2条件を満たしているので、とても大きなOもありえますf(n) = n^2*C > f(n) = n+3。グラフより上f(n) = n+3ですが、この上限と下限の間の領域は、以前の境界ほど正確ではありません。
于 2020-06-17T16:13:27.993 に答える
3
すでにいくつかの素晴らしい回答が投稿されていますが、別の方法で貢献したいと思います。すべてが起こっていることを視覚化したい場合は、コンパイラーが 1 秒以内に 10^8 近くの操作を実行できると想定できます。入力が 10^8 で与えられる場合、(ネストされていない for ループのように) 線形に動作するアルゴリズムを設計することができます。以下は、理解したいアルゴリズムのタイプをすばやく把握するのに役立つ表です;)
于 2020-05-13T07:33:10.993 に答える