4

すべてのアルゴリズムにはビッグオメガがありますか?

アルゴリズムが Big O と Big Omega の両方を持つことは可能ですか (ただし、互いに等しくなく、Big Theta ではありません)?

たとえば、Quicksort の Big O - O(n log n) ですが、Big Omega はありますか? もしそうなら、どうやって計算するのですか？

4

3 に答える 3

9

まず、境界とケースを混同しないことが最も重要です。Big-Oh、Big-Omega、Big-Thetaなどの境界は、成長率について何かを示しています。ケースは、アルゴリズムによる処理を現在検討している入力の種類について何かを示しています。

上記の違いを説明するために、非常に簡単な例を考えてみましょう。正規の「線形探索」アルゴリズムについて考えてみます。

LinearSearch(list[1...n], target)
1. for i := 1 to n do
2.    if list[i] = target then return i
3. return -1

サイズの入力に対する最良、最悪、および平均の3つのケースを検討することができますn。最良の場合、探しているのはリストの最初の要素です（実際には、リストの先頭の任意の固定数内にあります）。このような場合、要素を見つけて関数から戻るのに一定の時間しかかかりません。したがって、Big-OhとBig-Omegaは、最良の場合は同じです：O(1)とOmega(1)。と両方OをOmega当てはめると、も言うThetaので、これもそうTheta(1)です。

n最悪の場合、要素はリストになく、アルゴリズムはすべてのエントリを通過する必要があります。f(n) = nたまたま同じクラスの関数（線形関数）によって上と下からバインドされている関数であるため、これはですTheta(n)。

通常、平均的なケース分析は少し注意が必要です。長さの実行可能な入力の確率空間を定義する必要がありますn。すべての有効な入力（たとえば、符号なしモードで32ビットを使用して整数を表すことができる場合）は同じ確率であると言えます。それから、次のようにアルゴリズムの平均パフォーマンスを計算することができます。

  1. リストに表示されていない確率を見つけtargetます。を掛けnます。
  2. それtargetが少なくとも1回リストにあるとするとk、それぞれの位置に表示される確率を見つけます1 <= k <= n。P(k)それぞれに。を掛けますk。
  3. 上記のすべてを合計して、の観点から関数を取得しますn。

上記のステップ1で、確率がゼロ以外の場合、少なくとも線形関数を確実に取得することに注意してください（演習：線形関数以上を取得することはできません）。ただし、ステップ1の確率が実際にゼロの場合、ステップ2の確率の割り当ては、複雑さの決定にすべての違いをもたらします。一部の割り当てには最良の動作、他の割り当てには最悪の動作があり、場合によっては最終的になる可能性があります。最高（一定）または最悪（線形）と同じではない動作をします。

場合によっては、「一般的な」または「普遍的な」ケースについて大まかに話すことがあります。これは、すべての種類の入力（最良または最悪だけでなく）を考慮しますが、入力に特定の重みを与えず、平均を取りません。 。つまり、アルゴリズムのパフォーマンスを、最悪の場合の上限と、最良の場合の下限の観点から検討します。これはあなたがしていることのようです。

ふぅ。さて、あなたの質問に戻りましょう。

異なる境界を持つ関数はOありますか？Omega間違いなく。次の関数について考えてみます。

f(n) = 1 if n is odd, n if n is even.

最良のケースは「n奇数」であり、その場合fはTheta(1);です。最悪の場合は「n偶数」です。この場合fはTheta(n);です。fまた、平均的なケースで32ビットの符号なし整数について話していると仮定すると、平均Theta(n)的なケースでも同様になります。ただし、「ユニバーサル」の場合について言えば、fisO(n)とOmega(1)、であり、何もありませんTheta。ランタイムがに従って動作するアルゴリズムはf、次のようになります。

Strange(list[1...n], target)
1. if n is odd then return target
2. else return LinearSearch(list, target)

ここで、より興味深い質問は、（「ユニバーサル」ケース以外の）いくつかのケースに有効なTheta境界を割り当てることができないアルゴリズムがあるかどうかということかもしれません。これは興味深いですが、過度ではありません。その理由は、分析中に、最良の場合と最悪の場合の動作を構成するケースを選択できるためです。ケースの最初の選択に限界がないことが判明した場合は、目的に応じてTheta「異常」な入力を除外することができます。その意味で、ケースと境界は完全に独立しているわけではありません。多くの場合、「適切な」境界を持つようにケースを選択できます。

しかし、あなたはいつもそれをすることができますか？

わかりませんが、それは興味深い質問です。

于 2013-03-07T17:01:30.303 に答える
7

すべてのアルゴリズムにはビッグ オメガがありますか?

はい。ビッグオメガは下限です。どのアルゴリズムも少なくとも一定の時間がかかると言えるので、どのアルゴリズムもΩ(1).

すべてのアルゴリズムには Big O がありますか?

いいえ、Big O は上限です。(確実に) 終了しないアルゴリズムには Big O がありません。

アルゴリズムには上限があり、絶対的に最悪の場合、アルゴリズムはこれより長くはかからないと言えます。O(∞)は有効な表記法ではないと確信しています。

アルゴリズムの Big O と Big Omega が等しくなるのはいつですか?

実際には、いつそれらが等しくなるかを表す特別な表記があります: Big Theta (Θ)です。

アルゴリズムが入力のサイズに完全に対応する場合、それらは等しくなります (つまり、アルゴリズムが突然より効率的になる入力サイズはありません)。

これは、Big O を可能な限り最小の上限とし、Big Omega を可能な限り最大の下限とすることを前提としています。これは実際には定義上必須ではありませんが、一般的には非公式にそのように扱われます。この仮定を捨てると、どのアルゴリズムでも等しくない Big O と Big Omega を見つけることができます。

力ずくの素数チェック(すべての小さい数をループして目的の数に分割しようとする) は、おそらく、最小の上限と最大の下限が等しくない場合の良い例です。

number があるとしますn。また、当分の間、大きな数ほど除算に時間がかかるという事実を無視しましょう (これを考慮すると、実際の複雑さは異なりますが、同様の議論が成り立ちます)。また、数値のサイズではなく、数値自体に基づいて複雑さを計算しています(これはビット数である可能性があり、ここでの分析をかなり変更する可能性があります)。

nが 2 (またはその他の小さな素数) で割り切れる場合、1 分割 (または定数分割数) の素数であるかどうかを非常に迅速に確認できます。したがって、最大の下限は になりますΩ(1)。

が素数の場合、までの各数値でn割る必要があります (これより高くする必要がない理由は、演習として残しておきます)。これには がかかり、これが最小の上限になります。nsqrt(n)O(sqrt(n))

したがって、アルゴリズムは と にΩ(1)なりO(sqrt(n))ます。

一部の特に複雑なアルゴリズムでは、正確な複雑さを計算するのが難しい場合もあります。そのような場合、合理的に近い下限と上限を単純に計算し、そのままにしておく方がはるかに簡単で許容できる場合があります。ただし、これについては手元に例がありません。

これは、最良のケースと最悪のケースにどのように関係していますか?

最良のケースと最悪のケースの上限と下限を混同しないでください。これはよくある間違いで、少し混乱しますが、同じではありません。これはまったく別のトピックですが、簡単な説明として：

単一の入力サイズごとに、最良のケースと最悪のケース (および平均) を計算できます。上限と下限は、これら 3 つのケースのそれぞれに (別々に) 使用できます。これらのケースのそれぞれを、x 軸に入力サイズ、y 軸に時間を持つグラフ上の線と考えることができます。次に、これらの線のそれぞれについて、上限と下限は厳密に一致する必要がある線です。入力サイズが無限大になる傾向があるため、その線の上または下 (これは 100% 正確ではありませんが、基本的な考え方としては適切です)。

クイックソートには、最悪の場合(すべてのステップで最悪のピボットを選択する場合) と最良の場合(適切なピボットを選択する場合) があります。Big Theta の使用に注意してください。つまり、それらのそれぞれが下限と上限の両方であることを意味します。Θ(n2)Θ(n log n)

クイックソートを上記のプライム チェック アルゴリズムと比較してみましょう。

  • 与えられた数nがあり、それnが 53 であるとします。これは素数であるため、(常に)sqrt(53)素数であるかどうかを判断するための手順が実行されます。したがって、最良のケースと最悪のケースはすべて同じです。
  • size の配列を並べ替えたいとしますがn、nこれは 53 です。これらの 53 個の要素を配置して、クイック ソートが最終的に非常に悪いピボットを選択して前後のステップで実行するか (最悪の場合)、または本当に良いピボットを選択して前後に実行することができます。ステップ（最良のケース）。したがって、最良のケースと最悪のケースは異なります。53253 log 53
  • n上記のそれぞれを 54 とします 。
    • 1素数チェックの場合、54 が素数であると判断するのに約ステップしかかかりません。最良のケースと最悪のケースは同じですが、53 の場合とは異なります。
    • クイック ソートの場合も、最悪の場合のステップ数と最良の場合のステップ数があります。54254 log 54

したがって、クイックソートの場合、最悪のケースは常にステップを回避し、最良のケースは常にステップを回避します。したがって、最悪のケースの下限と上限 (または「タイトな」) 境界は であり、最良のケースのタイトな境界は です。n2n log nΘ(n2)Θ(n log n)

私たちの主なチェックでは、最悪の場合は回避sqrt(n)する場合もあれば、回避する場合もあります1。したがって、最悪の場合の下限は になりΩ(1)、上限は になりますO(sqrt(n))。最良の場合も同様です。

上記で単に「アルゴリズムはΩ(1)andになる」と言ったことに注意してくださいO(sqrt(n))。アルゴリズムが特定の入力サイズに対して常に同じ時間を要するのか、それともステートメントが最良、平均、または最悪のケースのいずれかを参照しているのかが明らかでないため、これは少しあいまいです。

これを計算するにはどうすればよいですか？

境界の証明はアルゴリズムに大きく依存するため、これについて一般的なアドバイスを与えることは困難です。最悪のケースと最良のケースを把握するには、上で行ったのと同様のアルゴリズムを分析する必要があります。

于 2013-03-07T17:05:18.480 に答える
1

Big O と Big Omega Big-oh vs big-thetaでわかるように、すべてのアルゴリズムで計算できます。

于 2013-03-07T16:23:30.020 に答える