5

私は本から漸近記法を研究していますが、著者が何を意味するのか理解できません。私はそれを知っていif f(n) = Θ(n^2) then f(n) = O(n^2)ます。しかし、著者の言葉から、挿入ソート関数のアルゴリズムf(n) = Θ(n)とf(n)=O(n^2)。

なんで？ビッグオメガまたはビッグシータは、入力が異なると変化しますか？

彼はこう言った：

「しかし、挿入ソートの最悪の場合の実行時間に制限されたΘ（n ^ 2）は、すべての入力の挿入ソートの実行時間に制限されたΘ（n ^ 2）を意味するものではありません。」

ただし、ビッグオー表記では異なります。彼はどういう意味ですか？それらの違いは何ですか？

私は困惑している。以下にコピーして貼り付けています。

O表記は上限を表すため、これを使用してアルゴリズムの最悪の場合の実行時間を制限すると、すべての入力でアルゴリズムの実行時間に制限があります。したがって、挿入ソートの最悪の場合の実行時間に制限されたO（n ^ 2）は、すべての入力の実行時間にも適用されます。ただし、挿入ソートの最悪の場合の実行時間に制限されたΘ（n ^ 2）は、すべての入力の挿入ソートの実行時間に制限されたΘ（n ^ 2）を意味するものではありません。たとえば、入力がすでにソートされている場合、挿入ソートはΘ（n）時間で実行されます。

4

5 に答える 5

4

ビッグオメガまたはビッグシータは、入力が異なると変化しますか？

はい。より簡単な例を示すために、左から右への配列での線形探索を考えてみましょう。最悪の平均的なケースでは、このアルゴリズムは、いくつかの定数aおよびbに対してf（ n）= a × n / 2+ bの予想されるステップを取ります。ただし、左側の要素が常に探しているキーを保持することが保証されている場合は、常に+ bステップを実行します。

Θは厳密な境界を示し、Θ（n）！=Θ（n²）であるため、2種類の入力のΘは異なります。

編集：Θとbig-Oが同じ入力で異なる場合、はい、それは完全に可能です。次の（明らかに些細な）例を考えてみましょう。

nを5に設定すると、 n =5とn <6の両方が真になります。しかし、nを1に設定すると、n = 5は偽になりますが、n <6はまだ真です。

同様に、big-Oは数値の<のように単なる上限ですが、Θは=のように厳密な境界です。

（実際、Θは定数aおよびbのa < n < bに似ています。つまり、数値の範囲に類似したものを定義しますが、原理は同じです。）

于 2012-10-10T09:29:40.713 に答える
0

CLRSエディション3ページ-44（漸近表記、関数、および実行時間）を参照してください。

漸近表記を使用してアルゴリズムの実行時間に適用する場合でも、we need to understand which running time we mean。worst-case実行時間に関心がある場合があります。Often, however, we wish to characterize the running time no matter what the input. In other words, we often wish to make a blanket statement that covers all inputs, not just the worst case.

上記のパラグラフからの引用：

  • 最悪の場合、アルゴリズムの実行時間に最大の制限があります。したがって、挿入ソートの最悪の場合の実行時間に制限されたO（n ^ 2）は、すべての入力の実行時間にも適用されます。

  • ただしTheta(n^2)、挿入ソートの最悪の場合の実行時間に 拘束されることTheta(n^2) は、すべての入力での挿入ソートの実行時間に拘束されることを意味するわけではありません。挿入ソートのベストケース実行時間が得られるためTheta(n)です。（リストがすでにソートされている場合）

  • 通常worst case、アルゴリズムの時間計算量を記述しますが、最良の場合と平均的な場合が説明責任を果たす場合、時間計算量はこれらの場合によって異なります。

于 2017-02-06T15:02:54.413 に答える
0

簡単に言うと、プログラムの実行時間は、入力サイズ、つまりf（n）の関数として記述されます。

は=非対称であるため、an + b = O（n）は、f（n）がセットO（g（n））に属することを意味します。したがって、an + b = O（n ^ 2）と言うこともできます。これは、a、b、およびnの値のf（n）がセットO（n ^ 2）に属しているためです。

したがって、Big-Oh（O）は上限のみを与えるか、表記がを与えると言うことができますblanket statement。これは、特定の入力サイズのすべての入力が、最悪の場合だけでなくカバーされることを意味します。たとえば、挿入の場合、サイズnの配列を逆の順序でソートします。

したがって、n = O（n ^ 2）は真ですが、アルゴリズムの最悪の場合の実行時間を定義する場合は悪用されます。最悪の場合の実行時間は、任意の入力の実行時間の上限を示します。そして、私たち全員が知っているように、挿入ソートの場合、実行時間は、固定サイズの特定の配列で入力がどれだけソートされているかに依存します。したがって、配列がソートされている場合、実行は線形になります。

したがって、最悪の場合を記述するために厳密な漸近境界表記が必要です。これは、Θ表記によって提供されます。したがって、挿入ソートの最悪の場合はΘ（n ^ 2）になり、最良の場合はΘ（n）になります。

于 2021-12-30T07:44:36.360 に答える
-1

すべての入力でアルゴリズムの実行時間に制限があります

これは、実行時間のある入力のセットがあり、n^2他の入力のセットが少ない場合、アルゴリズムはO(n^2)です。

ただし、挿入ソートの最悪の場合の実行時間に制限されたΘ（n ^ 2）は、すべての入力の挿入ソートの実行時間に制限されたΘ（n ^ 2）を意味するものではありません。

彼はその逆は真実ではないと言っています。アルゴリズムがO(n^2)である場合、すべての入力が2次時間で実行されることを意味するわけではありません。

于 2012-10-10T09:28:08.273 に答える
-4

挿入ソートアルゴリズムに関する私の学術理論は過去には遠いですが、あなたのコピーアンドペーストで私が理解していることから：

big-O表記は常に最悪のケースを表しますが、big-Thetaは典型的なデータのある種の平均を表します。

これを見てください：Θ（n）とO（n）の違いは何ですか？

于 2012-10-10T09:29:02.330 に答える