2

宿題の質問があります：

  1. ステートメント x = x + 1 が実行される回数のシータ表記を見つけます。（10点）。
i = n
while (i >= 1)
{
   for j = 1 to n
   {
      x = x + 1
   }
   i = i/2
}

これは私がやったことです：

では、まず簡単にしましょう。最初に、次の成長の順序を見つけます。

while (i >= 1)
{
   x = x + 1
   i = i/2
}

成長の順序を持O(log(n)) ​​つ実際には対数ベース2

もう一方の内側の for ループは n 回実行されるため、アルゴリズムは次の順序である必要があります。

O(log(n)*n)

私が混乱する部分は、theta 表記が big-O ではないことを見つけることになっていることです。シータ表記は、上限と下限で関数をバインドすると想定されていることを知っています。正解はTheta(log(n)*n)？

このリンクで答えを見つけましたが、その答えにたどり着く方法がわかりません。答えが Theta(n) であると彼らが主張するのはなぜですか?

4

3 に答える 3

2

これで、それも証明する必要がありOmega(nlogn)ます。

宿題なので、正確な方法は示しませんが、あなたが示しているのと同じ原則を使用していますO(nlogn)。関数の漸近的振る舞いが少なくともと同じくらい速く成長していることを[非公式に説明：]示す必要がありますnlogn。[大きなOの場合、最大で]の速度で成長していることを示しますnlogn。

関数がとの両方O(nlogn)である場合Omega(nlogn)、それはTheta（nlogn）[およびその逆]であることを忘れないでください。

psあなたの予感は真実です、そうでないことを示すのは簡単ですOmega(n)、そしてそれ故にそうではありませんTheta(n)

ps 2：他の回答の作者は別のプログラムと混同していると思います：

i = n
while (i >= 1)
{
   for j = 1 to i //NOTE: i instead of N here!
   {
      x = x + 1
   }
   i = i/2
}

上記のプログラムは確かTheta(n)にですが、あなたが提供したものとは異なります。

于 2012-03-04T16:55:57.743 に答える
2

シグマ記法を使用して簡単に表現できるように、コードフラグメントをより正式な方法で言い換えます。

for (i = n; i >= 1; i = i/2 ) {
    for j = 1; j <= n; j ++) {
        x = x + 1; // instruction of cost 'c'
    }
}

私達は手に入れました：

ここに画像の説明を入力

于 2014-04-23T22:23:25.533 に答える
0

@amitが言及しているように、私はすでに関数の上限を持っており、それは実際にはO（n * lgn）であるBig-Oです。その関数の表をプロットすると、次のようになります。

n   n*lng
1   0
2   2
3   4.754887502
4   8
5   11.60964047
6   15.509775
7   19.65148445
8   24
9   28.52932501
10  33.21928095

それはbig-Oであるため、実際の関数はこれらの値によって制限されることを意味します. つまり、実際の値は表の値よりも小さくなければなりません。たとえば、表を見てn=9、答えが以下であることがわかっている場合にポイントを取得します28.52932501

だから今、私たちはオメガを見つけることができず、それが別の限界です. 下限関数はそうあるべきだと思います。そうすれ Omega(n) ば、テーブルが得られます

n   Omega(n)
1    1
2    2
3    3
4    4
5    5
6    6
7    7
8    8
9    9
.......

それがもう一方の境界になります。たとえば、再びポイントを取るn = 9と、9 が得られます。これは、実数関数が 9 以上の値を与える必要があることを意味します。big-O 関数に基づいて、それが les 未満またはに等しい28.52932501

于 2012-03-04T17:28:29.313 に答える