1

これは私たちの教授によるスライドです。

例 4: 次の単純なプログラムについて考えてみましょう。

s = 0 
for i = 1 to n do
  for j = 1 to n do
    s= s+i+j
  endfor
endfor

T(n) = ?

この非常に単純なプログラムでも、T(n) の正確な式を取得するのは困難です。ご覧のとおり、ループはn²何度も繰り返され、ループ本体は一定数の命令を受け取ります。したがってT(n) = a*(n^2) + bn + c、いくつかの定数 a、b、c については。

今ここに私が思うものがあります。ボディ ループに一定の時間 'a' がかかるとします。次に、それ自体が a*(n^2) 回ループされます。では、b*n + c がどこから来るのかわかりません! 実際の答えは何ですか？

4

2 に答える 2

1

(a*(n^2) + b*n + c) / (a*(n^2)) = 1 + b/(a*n) + c/(a*(n^2)) -> 1 n -> 無限として。

于 2013-09-13T21:06:42.723 に答える