0

私はプログラムの実行時間を研究していて、Big O 表記法に出くわしました。すべてT(n)のO(f(n))整数に対して_ x_ _c > 0n >= xT(n) <= cf(n)

私が見た例では、xとの値を「選択」することでこれを証明していcます。値を式に差し込んで正しいかどうかを確認できることは理解していますが、実際に計算する方法はありますxかc? または、少なくとも、値を際限なくプラグインしないように、それらを選択する方法に関するいくつかの経験則はありますか?

4

1 に答える 1

0

値は、アルゴリズムの検査から得られますT。たとえば、単純なループがある場合:

for (i=0; i < n; ++i) {
  sum += i;
}

次に、操作を実行しますi<n、++iおよびsum+=in 回、およびi=01 回。したがってf(n)==n、c==4(4 つの操作の場合、値の正確さのために「1 回」を「n 回」に上げます)、x==1( については、まだとn==0を実行するため、式は機能しません)。これにより、O(n) パフォーマンスが得られます (入力数に比例します)。i=0i<n

ネストされたループの場合:

for (i=0; i < n; ++i) {
  for (j=0; j<n; ++j) {
    sum += j;
  }
}

計算は と同様で、f(n)==n^2O(n^2) が得られます。

cそのため、との正確な値を伝える簡単な方法はありませんxが、ほとんどの場合、難しい部分が思いつきますf-- そして、その「最小」も (O(n^2) アルゴリズムはまた、提供した定義によると O(n^3) アルゴリズムですが、そのアルゴリズムを O(n^3) ではなく O(n^2) で特徴付けたいと考えています)。sの順序付けは、が無限大に近づくfときの成長に基づいています。小さなs の場合、前者が後者よりも大きい場合でも、は より遅く成長します。nf(n)=n^3f(n)=2^nn

理論上、 と の実際の値は無限大に近づくにつれて無関係になるxことに注意してください。そのため、表記自体には表示されません。ただし、これは (比較的) 小さい値 ifの場合、命令の数がそれほど多くないことを意味するわけではありません(たとえば、for ループ内に 1000 の命令があります)。cnO(n)nf(n)

また、O(n) 表記では最悪のパフォーマンスが得られます。これは、たとえば、実際の生活 (平均ケースのコスト) やデータ構造の全体的な使用 (償却コスト) で観察されるものよりもはるかに高くなる可能性があります。

于 2012-04-06T16:09:22.657 に答える