1

大きなシータを計算する方法のリアルタイムの例を教えてください。

大きなシータは平均的なケース (最小-最大)/2 のようなものですか?

つまり (最小時間 - 大きな O)/2

間違っていたら訂正してください、ありがとう

4

3 に答える 3

7

ビッグ シータ表記は、次のルールを表します。

任意の 2 つの関数 についてf(n)、が無限大になるにつれてとが両方とも有界g(n)である場合、と. その場合、は の成長の上限と下限の両方です。f(n)/g(n)g(n)/f(n)nf = Θ(g)g = Θ(f)gf

アルゴリズムの例を次に示します。

def find-minimum(List) 
  min = +∞
  foreach value in List 
    min = value if min > value
  return min

入力リストのサイズであるc(n)コスト関数を評価したいと思います。nこのアルゴリズムは、リスト内のすべての項目に対して 1 つの比較を実行するため、 c(n) = n.

c(n)/n = 1nこれは無限大に向かうにつれて制限されたまま であるためc(n)、 より速く成長することはありませんn。これが big-O 記法 の意味c(n) = O(n)です。逆に、n/C(n) = 1も制限されたままであるためc(n)、 よりも遅くはなりませんn。遅くも速くも成長しないため、同じ速度で成長する必要があります。これがシータ表記の意味c(n) = Θ(n)です。

c(n)/n²も有界であることに注意してくださいc(n) = O(n²)— big-O 記法は複雑さの上限にすぎないため、O(n)関数は O(n²), O(n³)...

ただし、n²/c(n) = nは有界ではないので、c(n) ≠ Θ(n²). これは、ビッグ シータ表記の興味深い特性です。これは、複雑さの上限と下限の両方です。

于 2011-09-17T10:31:04.033 に答える
1

ビッグ シータは、関数T(n): if:のタイト バウンドです。その場合Omega(f(n))<=T(n)<=O(f(n))、Theta(f(n)) は T(n) のタイト バウンドです。

言い換えれば、Theta(f(n)) は、関数 T(n) を「記述」します。O [big O] と Omega の両方が、同じ T を同じ f で「記述」する場合です。

たとえば、[正しい中央値の選択による] クイックソートは、常に最大で O(nlogn)、少なくとも Omega(nlogn) を取るため、[適切な中央値の選択による] クイックソートは Theta(nlogn) です。

編集: コメントに議論を追加:
配列の検索は依然として Theta(n) です。シータ関数は、最悪/最良のケースを示すのではなく、望ましいケースの動作を示します。つまり、配列を検索します。T(n)=最悪の場合の演算数です。ここでは、明らかT(n)<=O(n)に だけでなくT(n)>=n/2、最悪の場合、配列全体を反復処理する必要があるためT(n)>=Omega(n)、したがって Theta(n) は漸近的に制限されます。

于 2011-09-17T10:21:39.523 に答える
0

http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notationsから、"Big O" は上限を表し、"Big Theta" は上限と下限、つまりn無限に向かう極限を表すことがわかります。

f(n) = O(g(n))      -->    |f(n)| < k.g(n)

f(n) = Theta(g(n))  -->    k1.g(n) < f(n) < k2.g(n)

したがって、Big O から Big Theta を推測することはできません。

于 2011-09-17T10:19:14.340 に答える