$ f（n）\ in O（g（n））$を数学的に理解しています：$ f（n）$は理解していません$ g（n）$よりも速く成長します。より正式には、$ \ exists c、n_0 $ s.t. $ f（n）\ leq cg（n）\ forall n \ geq n_0 $。
同様に、$ f（n）\ in \ Theta（g（n））$は、$ f（n）$が$ g（n）$とほぼ同じ速さで成長することを意味します。つまり、$ f（n）\ in O（g（n））、\ Omega（g（n））$。
私が得られないのは、人々がの実行時間に大きなOhを使用する理由です。アルゴリズム？大きなシータを使うべきではありません。アルゴリズムの「実行時間」とは、最悪の場合の実行時間を指します。つまり、$ T（n）= max \ {ALG（x）：| x | = n \} $。
つまり、例：サイズ$ n $（$ n $要素とターゲット値）の入力での線形検索の最悪の場合の実行時間は$ \ Theta（n）です。 $と$ O（n）$ですが、$ \ Theta（n）$はより多くの情報を提供します。では、なぜアルゴリズムブックは$ \ Theta（n）$ではなく$ O（n）$を使用するのですか。
コメント
- 多くの場合'は、アルゴリズムの実行時間に厳密なビッグシータ境界を設定できないためです。'アルゴリズムが十分に複雑な場合、実行時間は$ O（n ^ {n！}）$と言うのが最善の方法である可能性がありますが、実際には$ \ Theta（2 ^ {n \ log n \ log \ log n}）$。
- 歴史的な理由。
- "私がしていないこと'なぜ人々はアルゴリズムの実行時間に大きなああを使用するのですか？ '大きなシータを使用するべきではありません。"-はい。待ってはいけません、もっと正確な発言をする必要があります。しかし、選択する必要がある場合は、はい、$ \ Theta $！
回答
2つの理由があります。人々はビッグシータよりもビッグオーを好みます：
- アルゴリズムの実行時の複雑さは、最悪の場合の実行時の複雑さとして定義される必ずしもとは限りません。また、長さが$ n $の任意のインスタンスのランタイムと見なされる場合もあります。次に、たとえば、アルゴリズムのランタイム$ t（n）$が$ \ mathcal {O}（n ^ 2）$にあると書くと、これは、選択した長さ$ n $の入力が何であれ、常に大きくなることを意味します。ある定数$ c $に対して関数$ c \ cdot n ^ 2 $よりも漸近的に遅いので、明らかに最悪の場合のランタイムについてステートメントを作成します。
- ランタイムを分析するときもあります。与えている最悪の場合の複雑さが本当にきついかどうかわからないアルゴリズムの複雑さ。たとえば、実行時の行列乗算の複雑さを考えてみましょう。 。ランタイム$ n ^ {2.3728639} $が本当に最悪の場合であるかどうかはまだ明らかではありません。したがって、ランタイムは$ \ mathcal {O}（n ^ {2.3728639}）$にあることがわかっています。」 $ \ Theta（n ^ {2.3728639}）$にあるかどうかはわかりません。
しかし、場合によっては、BigThetaを提供したほうがよい場合もあります。ビッグオーバウンドよりもバウンド。
コメント
- 広告1：読者、注意あまり読みすぎないように！
回答
（ずさんな）上限は、厳密な上限よりも証明するのが簡単です。上限と下限は言うまでもありません。
一部のアルゴリズムのランタイムはできません em>上限/下限と同じ機能で与えられます。例えば。単純なソートアルゴリズムは$ O（n ^ 2）$ですが、下限は$ \ Omega（n）$です。
$ \ sim $を介して漸近的にパフォーマンスを提供するように努力することを主張する人もいます。ここで、$ f（n）\ sim g（n）$ if
$$ \ lim_ {n \ to \ infty} \ frac {f（n）} {g（n）} = 1 $$
（ソート時の比較など、いくつかの重要な操作の数に関して、平均または最悪の場合と言います）。つまり、部屋を小刻みに動かしますが、（おそらく巨大な）定数は敷物の下を掃引しませんでした。
コメント
- runtime "は、ベストケースの実行時間、ワーストケースの実行時間、平均ケースの実行時間などを指します。例：クイックソートには、$ \ Theta（n ^ 2）$の最悪の場合の実行時間と$ \ Theta（n）$の最良の場合の実行時間があります。漸近解析は関数で正しく定義されます。
回答
bigの場合-bigの代わりにThetaを使用できます-ああ、それが理解するのに不必要な困難を加えない限り、それは使われるべきです。 big-Thetaをbig-Ohの代わりに使用できない微妙なケースがいくつかあります。例：
次の問題を検討してください：偶数の長さの配列を並べ替えます。この問題を解決するプログラムは次のようになります。配列の長さが奇数の場合はすぐに終了し、配列の長さが偶数の場合はバブルソートを実行します。このアルゴリズムの最悪の実行時間はどれくらいですか？
確かに$ O（n ^ 2）$ですが、$ \という意味では$ \ Omega（n ^ 2）$ではありません。通常、オメガ$が定義されますが、その代わりに、最悪の場合の実行時間は、いわば「$ \ Omega（n ^ 2）$無限に頻繁に」です（警告：非標準の用語）。
回答
「アルゴリズムの本がシータではなくビッグオーを使用する理由」の回答：
Big-Ohは最悪の場合の分析に使用され、Big-Omegaは最良の場合にのみ使用されます。 しかし、Big-Thetaの観点から分析すると、両方のBig-Oh & Big-Omegaについて同時に説明します。
すなわち。 Big-Thetaの場合、Big-Oh == Big-Omegaである必要があります。そうしないと、Big-Thetaについて話すことができません。
したがって、どこでも（本/任意のドキュメント）、 Big-Theta、それらは両方のBig-Oh & Big-Omegaの複雑さを与えています（そして両方とも等しい）。しかし、多くの場合、それらは等しくないので、Big-のみを使用します。 最悪の場合のために。