アルゴリズムの実行時間については、いくつかのアルゴリズムの本で読んだことがあります。ここでは、として表現されていO(n)ます。たとえば、指定されたコードは、最良の場合はO（n）時間で実行され、最悪の場合はO（n 3 ）で実行されます。それはどういう意味ですか？自分のコードに対してどのように計算しますか？それは線形時間のようなものであり、事前定義された各ライブラリ関数には独自の実行時間があり、呼び出す前に覚えておく必要がありますか？ありがとう...
user837598
質問する
30681 次
3 に答える
9
Big O表記の初心者向けガイドは、開始するのに適した場所かもしれません。
http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
ウィキペディアもご覧ください
http://en.wikipedia.org/wiki/Big_O_notation
stackoverflowにはいくつかの関連する質問と良い答えがあります
と
于 2012-08-04T05:07:26.830 に答える
0
これは数学にすべきではありませんか？
すでにソートされているバブルソート配列でソートしようとしている場合は、配列に沿った移動で何かがチェックされているかどうかを確認できます。そうでない場合は、すべて大丈夫です-完了しました。
よりも、最良の場合にはO（n）の比較（正確にはn-1）があり、最悪の場合（配列が逆になっている）の場合はO（n ^ 2）の比較（n（n-1）/ 2）があります。 、正確には）。
より複雑な例。配列の最大要素を見つけましょう。明らかに、あなたは常にn-1の比較を行いますが、平均していくつの割り当てがありますか？複雑な数学の答え：H（n）-1。
通常、あなたの答えは最良のシナリオと最悪のシナリオを得るのは簡単ですが、平均は多くの数学を必要とします。
Knuth、Volume 1を読むことをお勧めします。しかし、誰が読まないでしょうか。
そして、正式な定義：
f（n）∈O（g（n））は存在することを意味しますn∈N：すべてのm> nf（m）に対して
実際、wikiでO-notationを読む必要があります。
于 2012-08-04T05:08:56.303 に答える
0
big-O表記は、漸近表記の一種です。漸近表記は数学からのアイデアであり、無限大に近づくときの「限界」での関数の動作を記述します。
アルゴリズムの実行にかかる時間を定義する際の問題は、マシンによって異なるため、通常はミリ秒単位で回答を提供できないことです。また、クロックサイクルで、または操作カウントとして回答を提供することはできません。特定のデータに固有すぎて役に立たない。
漸近表記を見る簡単な方法は、関数内のすべての定数因子を破棄することです。基本的に、nが十分に大きい場合、2は常にbnよりも大きくなります（すべてが正であると想定）。定数係数aとbを変更しても、それは変更されません。2が大きい場合はnの特定の値が変更されますが、それが発生することは変更されません。したがって、O（n 2 ）はO（n）よりも大きいと言い、とにかく知ることができない定数を忘れます。
nが大きい場合の問題は、通常、物事が十分に遅くなり、私たちが本当に気にする問題であるため、これは便利です。nが十分に小さい場合、かかる時間は短く、さまざまなアルゴリズムを選択することで得られる利益は小さくなります。nが大きくなると、別のアルゴリズムを選択すると大きな違いが生じる可能性があります。また、現実の世界で発生する問題は、簡単にテストできる問題よりもはるかに大きいことが多く、時間の経過とともに増大し続けることがよくあります（たとえば、データベースがより多くのデータを蓄積するにつれて）。
これは、有用な結果を見つけることができるように扱いにくい詳細を十分に抽象化する有用な数学的モデルですが、完全なシステムではありません。私たちは現実の世界で無限の問題を扱っていません。問題が十分に小さく、それらの定数が現実のパフォーマンスに関連している場合が多く、時計で時間を計る必要がある場合もあります。
MIT OCWのアルゴリズム入門コースは、この種のことには非常に適しています。ビデオやその他の資料は無料で入手できます。コースブック（無料ではありません）は、アルゴリズムで利用できる最高の本の1つです。
于 2012-08-04T05:10:31.123 に答える