2

アルゴリズムの時間は、次の定義によってT(n)制限される可能性があることを理解しています。O(g(n))

T(n) is O(g(n)) iff there is a c > 0, n0 > 0, such that for all n >= n0:

サイズn,A のすべての入力に対して、多くのc * g(n)ステップがかかります。 T(n)は、サイズ n のすべての入力の中で最も長い時間です。

しかし、私が理解していないのは の定義ですΩ(g(n))。定義は、サイズ n の入力に対して、 A が少なくともc * g(n)ステップを実行することです。

しかし、Ωそれが定義である場合、上限と同じアルゴリズムの下限を見つけることができませんでしたか? たとえば、最悪の場合の並べ替えに時間がかかる場合、手順を実行する任意のサイズ n に対して少なくとも 1 つの悪い入力が必要であるO(nlogn)ことを簡単に示すことができないでしょうか? について話しているとしましょう。ここで何が欠けているのかよくわかりません。なぜなら、新しいアルゴリズムを教えられているときはいつでも、特定の方法の時間がどちらかであるからです。Ω(nlogn)nlognheapsortƟ(g(n)) or O(g(n))Ɵ or O

私が言ったことが十分に明確であることを願っています。私は本当にこの混乱を解消する必要があります。ありがとうございました。

4

2 に答える 2

1

Oは上限です。つまりO(n lg n)、漸近的にn lg n、最悪の場合でも最大で定数倍のステップを取るアルゴリズムがわかっていることを意味します。

Ωは下限です。つまり、最悪の場合でも、Ω(n lg n)アルゴリズムが漸近的に a ステップ未満になることはあり得ないことがわかっています。n lg n

Ɵは厳密Ɵ(n lg n)な境界です: たとえば、アルゴリズムがO(n lg n)n lg nΩ(n lg n)n lg n

あなたの議論に欠陥があるのは、実際Ɵ(n lg n)には だけでなくも知っていると仮定しているからですO(n lg n)。

たとえば、Ω(n lg n)比較ソートには一般的な制限があることがわかっています。したがって、マージソートが証明さO(n lg n)れると、それはマージソートが であることを意味しƟ(n lg n)ます。よりも遅くないため、mergesortも であることに注意してください。(それは人々がそれを通常どのように説明するかではありませんが、それが正式な表記法が意味するものです。)O(n^2)n^2

一部のアルゴリズムでは、厳密な境界がわかりません。単純な計算モデルにおける一般的な3SUM 問題は、並べ替えの実行に使用できるためであることが知られていますが、アルゴリズムΩ(n lg n)しかありません。Ɵ(n^2)この問題に最適なアルゴリズムは と の間n lg nですn^2。O(n^2)とであると言えますΩ(n lg n)が、 はわかりませんƟ。

またo(f)、厳密に より小さいことを意味するfとω(f)、厳密に大きいことを意味する もありfます。

于 2012-04-13T05:03:58.703 に答える
0

私がよく知っている定義は、 T(n) は Ω(g(n)) if for some n0, for all n>n0, T(n) >= g(n)*kfor some k.

O(g(n)) と Ω(g(n)) の両方である場合、何かは Θ(n) です。

于 2012-04-13T05:03:48.810 に答える