ビッグオー表記とは何ですか？使っていますか？[重複]

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

質問

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

ビッグオー表記とは何ですか？使っていますか？

大学の授業を忘れてしまったようです :D

誰かがそれを使用していて、それを使用した実際の例をいくつか挙げていますか?

以下も参照してください。

8歳児向けのBig-O?
Big O、どのように計算/近似しますか?
計算量理論を実生活に適用しましたか?

役に立ちましたか？

解決

Big-O について話すときにほとんどの人が忘れている重要なことが 1 つあります。したがって、それについて言及する必要があると感じます。

Big-O を使用して比較することはできません。 スピード 2 つのアルゴリズムからなる。Big-O は、処理される項目の数が 2 倍になった場合にアルゴリズムが (おおよそ) どれくらい遅くなるか、または数を半分に減らした場合にアルゴリズムがどれくらい速くなるとしか述べていません。

ただし、まったく異なる 2 つのアルゴリズムと 1 つの (A） は O(n^2) そしてもう一つ（B） は O(log n), 、とは言われていません。 A よりも遅いです B. 。実は100個のアイテムがあると、 A よりも10倍速いかもしれません B. 。200項目あるとだけ書いてありますが、 A その要因によって成長が遅くなります n^2 そして B その要因によって成長が遅くなります log n. 。したがって、両方のベンチマークを実行し、どれくらいの時間がかかるかがわかっている場合、 A 100 個のアイテムを処理するのにかかる時間と時間 B 同じ 100 個のアイテムに対するニーズ、および A よりも速いです B, 、アイテムの量を計算できます B 追い越します A 速度で（速度として） B の減少よりもはるかにゆっくりと減少します A, 、追い越していきます A 遅かれ早かれ、これは確実です）。

他のヒント

Big O 表記は、アルゴリズムの制限要因を示します。これは、アルゴリズムの実行時間が入力に応じてどのようにスケールされるかを単純化して表現したものです。

例 (Java の場合):

/** Takes an array of strings and concatenates them
  * This is a silly way of doing things but it gets the 
  * point across hopefully
  * @param strings the array of strings to concatenate
  * @returns a string that is a result of the concatenation of all the strings
  *          in the array
  */
public static String badConcat(String[] Strings){
    String totalString = "";
    for(String s : strings) {
        for(int i = 0; i < s.length(); i++){
            totalString += s.charAt(i);
        }
    }
    return totalString;
}

ここで、これが実際に何をしているのか考えてみましょう。入力のすべての文字を調べてそれらを加算します。これは簡単なようです。問題はそれです 文字列は不変です. 。したがって、文字列に文字を追加するたびに、新しい文字列を作成する必要があります。これを行うには、古い文字列の値を新しい文字列にコピーし、新しい文字を追加する必要があります。

これは、最初の文字をコピーすることを意味します n どこで n 入力内の文字数です。キャラクターをコピーすることになります n-1 回なので、合計すると (n-1)(n/2) コピー。

これは (n^2-n)/2 Big O 表記の場合、(通常は) 最も高い振幅係数のみを使用し、それに乗算される定数を削除すると、次のようになります。 O(n^2).

のようなものを使用して、 StringBuilder O(nLog(n)) の線に沿ったものになります。先頭の文字数を計算して容量を設定すると、 StringBuilder そうすることができます O(n).

したがって、1000 文字の入力がある場合、最初の例ではおよそ 100 万回の操作が実行されることになります。 StringBuilder 10,000 回実行すると、 StringBuilder と setCapacity 同じことを行うために 1000 回の操作を実行することになります。おおよその目安ではありますが、 O(n) 表記は桁違いのものであり、正確な実行時間ではありません。

それは私が定期的に使用するものではありません。しかし、何かを行うための最適なアルゴリズムを見つけようとするとき、それは常に頭の片隅にあります。

非常によく似た質問がすでに次の場所で行われています 8歳児向けのBig-O?. 。そこにある答えがあなたの質問に答えてくれることを願っていますが、質問者はそれについて少しの数学的知識を持っていましたが、あなたが持っていないかもしれないので、より完全な説明が必要な場合は明確にしてください。

すべてのプログラマは、Big O 表記とは何か、一般的なデータ構造とアルゴリズムを使用したアクションに Big O 表記がどのように適用されるか (つまり、解決している問題に適した DS とアルゴリズムを選択する)、および独自のアルゴリズムで Big O 表記を計算する方法を認識している必要があります。

1) データ構造を扱う際のアルゴリズムの効率を測定するための順序です。

2) 「追加」/「並べ替え」/「削除」などのアクションは、データ構造 (およびアルゴリズム) が異なるとかかる時間が異なります。たとえば、ハッシュマップの場合、「追加」と「検索」は O(1) ですが、O (log n) は二分木の場合です。単純な配列を扱う場合、並べ替えは QuickSort では O(nlog n) ですが、BubbleSort では O(n^2) になります。

3) 計算は、一般的にアルゴリズムのループの深さを調べることで実行できます。ループなし、O(1)、すべてのセットを反復するループ (ある時点で中断される場合でも) O(n)。ループが反復ごとに検索スペースを半分にする場合は?O(log n)。一連のループの最大の O() を取得し、ループをネストするときに O() を乗算します。

ええ、それよりも複雑です。本当に興味があるなら教科書を買ってください。

「Big-O」表記は、n が非常に大きくなったときに、変数 (たとえば n) の 2 つの関数の増加率を比較するために使用されます。関数 f が関数 g よりもはるかに速く成長する場合、g = O(f) と言い、n が十分に大きい場合、f は いつも スケール係数までは g より大きくなければなりません。

これは、コンピューター サイエンス、特にアルゴリズムの分析において非常に役立つアイデアであることがわかりました。なぜなら、私たちは、たとえば 2 つの異なるアルゴリズムにかかる時間を表す関数の増加率を正確に気にすることが多いからです。非常に大まかに言えば、十分に大きい n (通常、問題は、配列の長さやグラフ内のノードの数などです。

n が十分に大きくなるというこの条件により、多くの便利なトリックを実行できるようになります。おそらく最も頻繁に使用される方法は、関数を最も急速に成長する用語まで単純化できることです。たとえば、n^2 + n = O(n^2) は、n が十分に大きくなると、n^2 項が とても大きい n よりも、n 項は実質的に重要ではありません。したがって、検討から外すことができます。

ただし、これは、big-O 表記が小さい n に対してあまり役に立たないことを意味します。これは、私たちが忘れていた成長の遅い項が依然として実行時間に影響を与えるほど十分に重要であるためです。

私たちが現在持っているのは、2 つの異なるアルゴリズムのコストを比較するためのツールであり、一方が他方よりも速いか遅いかを示す略語です。Big-O 表記は悪用される可能性がありますが、すでに不正確であるため、これは残念です。ある関数が別の関数よりも成長が遅いこと、および 2 つの関数が同じ速度で成長することを表す同等の用語があります。

ああ、それを使いますか？はい、常に、自分のコードがどの程度効率的であるかを把握しているときは、コストの「封筒の裏側」の優れた概算値が得られます。

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) は最終的に常に勝ちます)。正式な定義では絶対値も使用されます。しかし、なんとか直感的に理解できたと思います。

また、特に多次元問題の場合、多くのアルゴリズムの複雑さは複数の変数に基づいていることも考慮する価値があるかもしれません。たとえば、最近、次のアルゴリズムを作成する必要がありました。n 個の点と m 個のポリゴンのセットが与えられた場合、ポリゴンのいずれかに含まれるすべての点を抽出します。複雑さは、n と m という 2 つの既知の変数と、各多角形にいくつの点があるかという未知数に基づいています。ここでの大きな O 表記は、O(f(n)) や O(f(n) + g(m)) よりもかなり複雑です。Big O は、多数の同種のアイテムを扱う場合には適していますが、常にそうであるとは期待しないでください。

データに対する実際の反復回数は多くの場合データに依存することにも注意してください。クイックソートは通常は高速ですが、事前に並べ替えられたデータを与えると速度が低下します。私のポイントとポリゴンのアルゴリズムは、データがどのように編成される可能性があるか、および n と m の相対的なサイズに関する事前の知識に基づいて、O(n + (m log(m)) に近い非常に高速な結果になりました。相対的なサイズが異なるランダムに編成されたデータでは、ひどく落ちてしまいます。

最後に考慮すべきことは、アルゴリズムの速度とアルゴリズムが使用するスペースの量の間には直接のトレードオフがあることが多いということです。 鳩穴選別 はその良い例です。ポイントとポリゴンの話に戻りますが、すべてのポリゴンはシンプルですぐに描画でき、それぞれ一定の時間で画面上に、たとえば青色で塗りつぶすことができたとします。したがって、黒い画面に m 個のポリゴンを描画すると、O(m) 時間がかかります。n 個の点のいずれかが多角形内にあるかどうかを確認するには、その点のピクセルが緑か黒かを確認するだけです。したがって、チェックは O(n) で、分析の合計は O(m + n) です。もちろん欠点は、実世界の座標をミリ単位の精度で扱う場合、ほぼ無限のストレージが必要になることです。...ほーん。

検討する価値もあるかもしれません 償却された 最悪の場合ではなく、これは、たとえば、アルゴリズムを実行すると、 n 回、そうなります ○(1) 平均的には良いですが、場合によってはもっと悪い場合もあります。

良い例は動的テーブルです。これは基本的に要素を追加すると拡張される配列です。単純な実装では、要素が追加されるたびに配列のサイズが 1 ずつ増加します。これは、新しい要素が追加されるたびにすべての要素をコピーする必要があることを意味します。これにより、 の上2) このメソッドを使用して一連の配列を連結する場合は、アルゴリズムを使用します。別の方法としては、追加のストレージが必要になるたびにアレイの容量を 2 倍にすることです。追加するのは の上） 操作をコピーするだけで済む場合もあります。 の上） あらゆる要素 n 要素が追加されるため、操作は次のようになります。 ○(1) 平均して。このように物事は次のようになります 文字列ビルダー または std::vector が実装されています。

ビッグオー表記とは何ですか？

Big O 表記法は、アルゴリズムが入力データのサイズに関連して必要とする多くのステップ間の関係を表現する方法です。これはアルゴリズムの複雑さと呼ばれます。たとえば、バブル ソートを使用してサイズ N のリストを並べ替えるには、O(N^2) ステップが必要です。

Big O記法を使用しますか?

私はアルゴリズムの複雑さを他のプログラマに伝えるために、時々 Big O 記法を使用します。私は基礎となる理論を使用します（例：Big O 分析テクニック) を使用するアルゴリズムを常に考えています。

具体例は？

私は複雑さ分析の理論を使用して、メモリの再割り当てを必要とせず、インデックス作成に平均 O(N) 時間をサポートする効率的なスタック データ構造のアルゴリズムを作成しました。私はアルゴリズムを他の人に説明するために Big O 記法を使用しました。また、複雑度分析を使用して、線形時間ソート O(N) がいつ可能になるかを理解しました。

ウィキペディアより……

Big O 記法は、アルゴリズムを効率的に分析するときに役立ちます。たとえば、サイズ n の問題を完了するのにかかる時間 (またはステップ数) は、T(n) = 4n² − 2n + 2 であることが判明する場合があります。

n が大きくなるにつれて、n² 項が優勢になるため、他の項はすべて無視できます。たとえば、n = 500 の場合、4n² 項は 2n 項の 1000 倍になります。後者を無視しても、ほとんどの場合、式の値に与える影響はごくわずかです。

もちろん使ったことないんですが…

アルゴリズムの複雑さを評価できる必要があります。これに必要な要素の数に関する知識を組み合わせると、そのタスクに適さないかどうかを判断するのに役立ちます。

最悪の場合にアルゴリズムが何回反復するかを示します。

リスト内の項目を検索するには、項目が見つかるまでリストをたどることができます。最悪の場合、商品は最下位になります。

リストに n 個の項目があるとします。最悪の場合、n 回の反復が必要になります。Big O 表記では O(n) です。

これは、アルゴリズムがどれほど効率的であるかを実際に示しています。

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