34

アルゴリズム解析を学んでいます。O、Ω、Θの違いがよくわかりません。

それらの定義方法は次のとおりです。

  • f(n) = O(g(n))c · g(n)は の上限を意味しf(n)ます。したがって、常に ≤で あるcような定数が存在します。f(n)c · g(n)nn ≥ n0n0
  • f(n) = Ω(g(n))c · g(n)は の下限を意味しf(n)ます。したがって、すべての に対して常に ≥となる定数cが存在します。f(n)c · g(n)n ≥ n0
  • f(n) = Θ(g(n))すべてのについて、 はc1 · g(n)の上限でf(n)あり、c2 · g(n)は の下限であることを意味します。 したがって、定数などが存在し、 およびが存在します。これは、 に対して適切でタイトな境界を提供することを意味します。f(n)n ≥ n0c1c2f(n) ≤ c1 ·g(n)f(n) ≥ c2 ·g(n)g(n)f(n)

私がこれを理解した方法は次のとおりです。

  • O(f(n))指定された関数/アルゴリズムの最悪の場合の複雑さを示します。
  • Ω(f(n))与えられた関数/アルゴリズムの最良のケースの複雑さを示します。
  • Θ(f(n))与えられた関数/アルゴリズムの平均的なケースの複雑さを示します。

間違っている場合は修正してください。その場合、各アルゴリズムの時間計算量は、3 つの表記法すべてで表現する必要があります。しかし、O、Ω、または Θ のいずれかで表されることがわかりました。なぜ3つすべてではないのですか？

4

6 に答える 6

42

記法は、O、Ω、または Θ のいずれであっても、関数の漸近成長を表すことを覚えておくことが重要です。本質的にアルゴリズム自体とは何の関係もありません。問題の関数は、アルゴリズムの「複雑さ」(実行時間) であり、最悪の場合、最良の場合、または平均的な場合のいずれかですが、表記法は関数の由来とは無関係です。

たとえば、関数 f(n)=3n 2 +5 は次のとおりです。

  • O(n 2 )、O(n 2 log n)、O(n 3 )、O(n 4 ) などでもありますが、O(n) ではありません。
  • Ω(n 2 )、Ω(n log n)、Ω(n) などでもありますが、Ω(n 3 ) ではありません。
  • Θ(n 2 )。Θ(n 2 log n) でも Θ(n 2 /log n)でもありません。

通常、考慮される関数は、アルゴリズムの最悪の場合の複雑さであり、3 つの表記法のうちどの表記法が使用されるかは、それについて何を言いたいか、および分析をどれだけ慎重に行うかによって異なります。たとえば、入れ子になったループが 2 つあるため、最悪の場合の実行時間は最大でO(n 2 ) であることがわかりますが、これが実際に何らかの入力で達成されるかどうかは気にしません。(通常、それは明らかです。) または、ソートの最悪の場合の実行時間は Ω(n log n) であると言うことができます。これは、少なくとも cn(log n) を必要とする入力がいくつかあるに違いないためです。ステップ。または、特定のマージソート アルゴリズムを見て、最悪の場合でも最大で O(n log n) ステップしかかからないことがわかります。一部の入力によって n log n ステップかかるため、最悪の場合の実行時間は Θ(n log n) です。

上記の 3 つの例すべてで、分析されていたのは同じ (最悪の場合の) 実行時間であったことに注意してください。代わりに最良のケースまたは平均的なケースを分析することもできますが、繰り返しますが、使用する 3 つの表記法は、何を言いたいかによって異なります。同じ機能の成長。

于 2009-12-25T04:43:32.187 に答える
36

Θ は、漸近的にタイトな上限と下限を示します。

O は上限を示しますが、この範囲はきつい場合とそうでない場合があります。
o は、厳密ではない上限を示します。

Ω は下限を表しますが、この範囲はきつい場合とそうでない場合があります。
ω は、きつくない下限を示します。

于 2009-12-25T03:55:45.753 に答える
6

これら 3 つの意味については、Can Berk Güder の回答を参照してください。

また、最良のケース、最悪のケース、平均的なケースとはまったく関係がないことにも注意してください。たとえば、バブル ソートは、最善の場合は Θ(n) (データが既に並べ替えられている場合は n-1 回の比較のみが必要なため)、最悪の場合は Θ(n^2) です。これは、ランダムにシャッフルされた入力を想定した Θ(n^2) 平均ケースです。したがって、その平均的なケースも O(n^2)、O(n^3)、および O(2^n) です。

したがって、O、Θ、および Ω は、それがどのような境界であるかを示します。彼らは、境界が制限されているものを教えてくれません。状況によっては、最良のケース、最悪のケース、平均的なケース、またはアルゴリズム全体 (すべてのケース) に対する制限である可能性があります。

もちろん、アルゴリズムに Ω(g) ベスト ケースがある場合、それ自体が Ω(g) です。O(g) 最悪の場合は O(g) です。だからそこには関係があります。しかし、平均ケースが Θ(g) の場合、最良のケースと最悪のケースについてはほとんど何もわかりません。

「なぜ3つすべてではないのですか？」については。

関数が Θ(g) の場合、それは O(g) と Ω(g) でもあります。したがって、Θ 境界と一緒に他の境界を提供する意味はあまりありません。

他の 1 つを単独で見る場合、それは一般に、上限のみ、または下限のみを気にするためです。したがって、すべての比較ソートは必然的に Ω(n log n) ワースト ケースであり、バブル ソートは O(n^2) ワースト ケースですが、O(n) ベスト ケースであると言えます。時間を完全に記述しようとしていないからです。複雑さ、特定のコンテキストで気にする境界を表現しているだけです。

いずれにせよ、ほとんどの人は怠け者のようで、ギリシャ文字を入力する必要はありません。私は知っています。したがって、比較ソートは「せいぜいO(n log n)」であるとだけ言います。本当に表記の乱用ですが、要点はわかります。

于 2009-12-25T11:00:04.807 に答える
4

これらは、本当に役立つリソースの一部です。

于 2009-12-25T03:56:28.493 に答える
-1

Big-O 表記法は、n が大きくてもアルゴリズムのパフォーマンスが大幅に低下しないことを保証するため、アルゴリズムの複雑さと呼ばれることがよくあります。ただし、先に正しく指摘したように、Big-O は漸近評価を提供し、特定の入力が与えられるとアルゴリズムが異なる動作をする可能性があります。たとえば、配列が既にソートされている場合、クイックソートは O(n^2) になります。OTOH、漸近的な状況は、きちんとした実装で実際に改善される可能性があります。

于 2009-12-26T12:47:17.943 に答える