ビッグオー記法とは？使いますか？
私はこの大学のクラスを逃したと思います:D
誰かがそれを使用し、それを使用した場所の実例を挙げていますか?
Brian
質問する
28356 次
12 に答える
41
Big-O について話すとき、ほとんどの人が忘れがちな重要なことを 1 つ挙げておきます。
Big-O を使用して2 つのアルゴリズムの速度を比較することはできません。Big-O は、処理されるアイテムの数を 2 倍にした場合にアルゴリズムが (おおよそ) どれだけ遅くなるか、または数を半分に減らした場合にどれだけ速くなるかを示しているだけです。
ただし、まったく異なる 2 つのアルゴリズムがあり、一方 ( A) がO(n^2)で、もう一方 ( B) がである場合、は より遅いO(log n)とは言えません。実際、100 個のアイテムを使用すると、よりも 10 倍高速になる可能性があります。200個のアイテムで、係数で成長が遅くなり、係数で成長が遅くなるとだけ言っています。したがって、両方のベンチマークを実行し、100 個のアイテムを処理するのにかかる時間と、同じ 100 個のアイテムを処理するのに必要な時間がわかっている場合、およびよりも高速である場合、速度が追い越されるアイテムの量を計算できます(速度としての減少は、の減少よりもはるかに遅いABABAn^2Blog nABABBABAA、遅かれ早かれ追い越すでしょう—これは確かです)。
于 2008-09-25T12:57:10.350 に答える
9
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;
}
次に、これが実際に何をしているのかを考えてください。入力のすべての文字を調べて、それらを足し合わせます。これは簡単なようです。問題は、Stringが不変であるということです。したがって、文字列に文字を追加するたびに、新しい文字列を作成する必要があります。これを行うには、古い文字列から新しい文字列に値をコピーして、新しい文字を追加する必要があります。
これは、最初の文字をn回コピーすることを意味します。ここで、 nは入力の文字数です。キャラクターn-1タイムをコピーするので、全部で(n-1)(n/2)コピーがあります。
これは(n^2-n)/2、Big O表記の場合、（通常は）最大の大きさの係数のみを使用し、それを掛けた定数をすべて削除すると、最終的にはになりO(n^2)ます。
aのようなものを使用することStringBuilderは、O（nLog（n））の線に沿ったものになります。最初に文字数を計算し、の容量を設定すると、StringBuilderを取得できますO(n)。
したがって、1000文字の入力がある場合、最初の例では約100万回の操作StringBuilderを実行し、10,000回の操作を実行し、StringBuilderwithsetCapacityは1000回の操作を実行して同じことを実行します。これは概算ですが、O(n)表記は桁違いであり、正確な実行時間ではありません。
それは私が定期的に言うことではありません。しかし、何かをするための最良のアルゴリズムを見つけようとするとき、それは常に私の心の奥底にあります。
于 2008-09-25T12:51:05.167 に答える
4
非常によく似た質問がBig-O for Eight Year Olds ですでに出されていますか? . そこにある答えがあなたの質問に答えてくれることを願っています.
于 2008-09-25T12:32:46.647 に答える
3
すべてのプログラマーは Big O 記法とは何か、それが共通のデータ構造とアルゴリズムを使用するアクションにどのように適用されるか (したがって、解決しようとしている問題に対して正しい DS とアルゴリズムを選択する)、および独自のアルゴリズムでそれを計算する方法を認識する必要があります。
1) データ構造を操作するときのアルゴリズムの効率を測定する順序です。
2) 'add' / 'sort' / 'remove' のようなアクションは、異なるデータ構造 (およびアルゴリズム) で異なる時間がかかる可能性があります。たとえば、'add' と 'find' はハッシュマップの O(1) ですが、O (ログ n) 二分木の場合。単純な配列を扱う場合、並べ替えは QuickSort では O(nlog n) ですが、BubbleSort では O(n^2) です。
3) 計算は、一般的にアルゴリズムのループ深度を調べることで実行できます。ループなし、O(1)、すべてのセットを反復するループ (ある時点で発生したとしても) O(n)。ループが反復ごとに検索スペースを半分にする場合は? O(log n)。ループのシーケンスで最大の O() を取り、ループをネストするときは O() を乗算します。
ええ、それはそれよりも複雑です。興味のある方は教科書を手に入れてください。
于 2008-09-25T12:33:16.553 に答える
3
'Big-O' 表記法は、n が非常に大きくなるにつれて、変数 (たとえば n) の 2 つの関数の成長率を比較するために使用されます。関数 f が関数 g よりもはるかに速く成長する場合、g = O(f) と言って、n が十分に大きい場合、f は常にスケーリング係数まで g よりも大きくなります。
これは、コンピューター サイエンス、特にアルゴリズムの分析において非常に有用なアイデアであることが判明しました。たとえば、2 つの異なるアルゴリズムにかかる時間を表す関数の成長率を正確に考慮することがよくあるためです。非常に大雑把に言えば、実行時間 t1(n) のアルゴリズムは実行時間 t2(n) のアルゴリズムよりも効率的であると判断できます。十分に大きな n に対して t1 = O(t2) の場合です。問題 - 配列の長さやグラフ内のノードの数など。
n が十分に大きくなるというこの規定により、多くの便利なトリックを引き出すことができます。おそらく最も頻繁に使用されるのは、最も急速に成長する項まで関数を単純化できるというものです。たとえば、n^2 + n = O(n^2) は、n が十分に大きくなると、n^2 項がn よりもはるかに大きくなるため、n 項は実質的に重要ではなくなります。したがって、検討から外すことができます。
ただし、これは、大きな O 表記が小さな n に対してあまり役に立たないことを意味します。なぜなら、私たちが忘れていたゆっくりと成長する項は、依然として実行時間に影響を与えるほど重要だからです。
私たちが今持っているのは、2 つの異なるアルゴリズムのコストを比較するためのツールであり、一方が他方よりも速いか遅いかを示すための省略表現です。Big-O 記法は悪用される可能性があり、これはすでに十分に不正確であるため残念です! 関数の成長速度が他の関数より遅く、2 つの関数が同じ速度で成長することを表す用語があります。
ああ、私はそれを使いますか？はい、いつでも - 自分のコードがどれほど効率的であるかを把握しているときに、コストの「封筒の裏側」の優れた概算値が得られます。
于 2008-09-26T16:35:03.160 に答える
3
Big-Oの背後にある「直感」
x が無限大に近づくにつれて、x をめぐる 2 つの関数 f(x) と g(x) の間の「競合」を想像してください。
ここで、ある時点 (ある x) から、一方の関数が常に他方よりも高い値を持っている場合、この関数を他方よりも「高速」と呼びましょう。
したがって、たとえば、x > 100 ごとに f(x) > g(x) である場合、f(x) は g(x) よりも「高速」です。
この場合、g(x) = O(f(x)) となります。f(x) は g(x) の一種の「速度制限」をもたらします。
これはbig-O 記法の正確な定義ではなく、f(x) は定数 C に対して C*g(x) よりも大きくなければならないことも示しています (これは、 g(x) に一定の係数を掛けることで競争に勝つことができます - f(x) は常に最後に勝ちます)。正式な定義でも絶対値が使用されます。しかし、私はそれを直感的にすることができたと思っています。
于 2009-06-03T04:34:44.967 に答える
2
多くのアルゴリズムの複雑さは、特に多次元の問題では、複数の変数に基づいていることも考慮する価値があります。たとえば、私は最近、次のアルゴリズムを作成する必要がありました。n個のポイントとm個のポリゴンのセットが与えられた場合、任意のポリゴンにあるすべてのポイントを抽出します。複雑さは、2つの既知の変数nとmに基づいており、各ポリゴンにいくつのポイントがあるかは不明です。ここでの大きな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）です。もちろん、実世界の座標をミリメートル単位の精度で処理する場合は、ほぼ無限のストレージが必要になるという欠点があります。
于 2008-09-27T16:06:30.960 に答える
2
最悪の場合だけでなく、償却時間を考慮することも価値があるかもしれません。これは、たとえば、アルゴリズムをn回実行すると、平均してO（1）になることを意味しますが、場合によってはさらに悪化する可能性があります。
良い例は動的テーブルです。これは基本的に、要素を追加すると拡張する配列です。単純な実装では、追加される要素ごとに配列のサイズが1ずつ増加します。つまり、新しい要素が追加されるたびにすべての要素をコピーする必要があります。この方法を使用して一連の配列を連結する場合、これによりO（n 2）アルゴリズムが生成されます。別の方法は、より多くのストレージが必要になるたびにアレイの容量を2倍にすることです。追加はO（n）操作である場合もありますが、追加されるn要素ごとにO（n）要素をコピーするだけでよいため、操作は平均してO（1）になります。これは、StringBuilderやstd::vectorが実装されています。
于 2008-09-27T16:19:44.627 に答える
2
ビッグオー記法とは？
Big O表記は、入力データのサイズに関連してアルゴリズムが必要とする多くのステップ間の関係を表現する方法です。これは、アルゴリズムの複雑さと呼ばれます。たとえば、バブル ソートを使用してサイズ N のリストをソートするには、O(N^2) ステップかかります。
Big O表記を使用しますか?
私は時折 Big O 記法を使用して、アルゴリズムの複雑さを仲間のプログラマーに伝えます。どのアルゴリズムを使用するかを考えるときは、常に基礎となる理論 (Big O 分析手法など) を使用します。
具体例？
複雑性分析の理論を使用して、メモリの再割り当てを必要とせず、インデックス作成に O(N) の平均時間をサポートする効率的なスタック データ構造のアルゴリズムを作成しました。アルゴリズムを他の人に説明するために Big O 記法を使用しました。また、複雑さの分析を使用して、線形時間ソート O(N) が可能な場合を理解しました。
于 2009-10-18T14:27:14.667 に答える
1
ウィキペディアより……
Big O 表記は、アルゴリズムを効率的に分析する場合に役立ちます。たとえば、サイズ n の問題を完了するのにかかる時間 (またはステップ数) は、T(n) = 4n² − 2n + 2 であることがわかる場合があります。
n が大きくなると、n² 項が支配的になるため、他のすべての項は無視できます。たとえば、n = 500 の場合、項 4n² は 2n 項の 1000 倍になります。後者を無視すると、ほとんどの目的で式の値にほとんど影響がありません。
もちろん使ったことはありませんが..
于 2008-09-25T12:34:46.580 に答える
1
アルゴリズムの複雑さを評価できる必要があります。これを、必要な要素の数に関する知識と組み合わせると、そのタスクに適していないかどうかを判断するのに役立ちます。
于 2008-09-25T12:39:58.423 に答える
0
アルゴリズムが最悪の場合に何回反復するかを示します。
リスト内のアイテムを検索するには、アイテムを取得するまでリストをトラバースできます。最悪の場合、商品は最後尾です。
リストに n 個の項目があるとします。最悪の場合、n回の反復を行います。Big O 表記では O(n) です。
アルゴリズムがどれほど効率的であるかを実際に示しています。
于 2008-09-25T12:34:45.830 に答える