0

私は試験の準備をしていますが、これらは昨年の試験の問題の一部です。タスクは、正確な複雑さと漸近的な複雑さの両方を計算することです。どのように解決しますか？可能であれば、普遍的に。

for ( i = j = 0; i < n; j ++ ) {
  doSomething ();
  i += j / n;
  j %= n;
}

for ( i = 0; i < 2 * n; i += 2 )
  for ( j = 1; j <= n; j <<= 1 )
    if ( j & i )
      doSomething ();

for (i = 0; i < 2*n; i++) {
  if ( i > n )
    for (j = i; j < 2 * i; j ++ ) doSomething();
  else
    for (j = n; j < 2 * n; j ++ ) doSomething();
}

前もって感謝します

4

3 に答える 3

2

3番目のループの私の解決策は

t(n) = [ (n-1)*n +  ((n-1)*n)/2 ] *D  + [ n^2 +n ] *D + [ 2n ]*I

したがって、 は一定の時間を持ち、O(n^2)とは整数です。doSomething()ij

第 2 項 ( [ n^2 +n ] *D) はかなり簡単です。

ループ

for (j = n; j < 2 * n; j ++ ) doSomething();

while が呼び出されるため、0 から始まるため、何度i <= nも呼び出されます。n+1

ループは時間をfor (j = n; j < 2 * n; j ++ )呼び出すdoSomething() nので、(n+1)*n*D = [n^2+n] *D. doSomething()私はそれに等しい一定の時間を持っていると仮定しますD

最初の項はもう少し複雑です。

for (j = i; j < 2 * i; j ++ ) doSomething();

いつ呼び出されるi>nので、n-1何回も呼び出されます。ループはdoSomething()i 回呼び出します。最初に が呼び出されn+1、2 回目は 'n+2' というように、2n-1と等しくなるまで繰り返されn + (n-1)ます。したがって、このようなシーケンスが得られます{n+1, n+2, n+3, ... , n+(n-1)}。

シーケンスを合計すると、 n-1timesnと sumが得られ1+2+3+...+ (n-1)ます。最後の項は「Gaußsche Summenformel」で解くことができます(申し訳ありませんが、英語の名前はありませんが、ドイツ語の wiki リンクで式を見ることができます)。((n-1)*n)/2

したがって、最初の項は(n-1) * n + ((n-1)*n)/2 *D

したがって、最後の項は と呼ばれる2*n*IifIステートメントです。 は If ステートメントを実行する時間です。

于 2013-01-10T12:08:59.457 に答える
1

リクエストに応じて、最初のループが次のような構造に等しいという結果に至った経緯を説明します。

int i, j;
for (i=0; i < n; i++) {
    for (j=0; j <= n; j++) {
        doSomething();
    }
}

まず、実際に考える前に、3つのforループの最初の部分を含む小さなサンプルプログラムを作成したことを認めなければなりません。これには、反復中に出力さiれます。結果を見た後、どうしてjこんな結果になるのか考えていました。

コメントで、私が定義したことを追加するのを忘れましたn=200。

説明

j反復のステップごとに定期的にインクリメントされますが、値を超えることはありませんn。なんで？n反復後、 j==n。インクリメントされた後0、ステートメントでに設定されます。ステートメントでは、は時間単位で増分され、その時点で、は。単位で増分されます。これは、まで最初からやり直します。j %= n ii += j / ni0 n-1n1i >= n

于 2013-01-08T13:16:07.783 に答える
1

ここでの問題は、3 つのループ構造すべてについて、反復回数が に比例してどのように変化するかということnですよね? それでは、ループを見てみましょう。あなたはすでにそれを解決したので、私は最初のものを省略します。

for ( i = 0; i < 2 * n; i += 2 )
  for ( j = 1; j <= n; j <<= 1 )
    if ( j & i )
      doSomething ();

外側の for ループは明らかに正確なn回数実行されます。log_2(n)ビットごとのシフト操作のため、内側のループの実行時間が長くなります。if 句は一定時間で実行されるため、ループ全体も一定時間内にO(n * log_2(n))あると仮定するdoSomething()と、 になります。

それはそれをより明確にしますか？:)

于 2013-01-08T13:12:08.077 に答える