2

このアルゴリズムは、アレクサンダー・シェンによる偉大な「アルゴリズムとプログラミング: 問題と解決策」から取られています (つまり、演習 1.1.28)。

以下はロシア語からの私の翻訳ですので、間違いや曖昧さをお許しください. そう感じたら訂正してください。

アルゴリズムは何をすべきか

与えられた自然なnアルゴリズムを使用して、不等式の解の数を計算します

x*x + y*y < n

実数の操作を使用しない自然数 (非負数)

パスカルで

k := 0; s := 0;

{at this moment of execution
 (s) = number of solutions of inequality with
 x*x + y*y < n, x < k}
while k*k < n do begin
  l := 0; t := 0;

  while k*k + l*l < n do begin
    l := l + 1;
    t := t + 1;
  end;

  {at this line 
   (t) = number of solutions of k*k + y*y < n
   for given (k) with y>=0}
  k := k + 1;
  s := s + t;
end;

{k*k >= n, so s = number of solutions of inequality}

さらに、テキストの中でシェンは、このアルゴリズムによって実行される操作の数は「計算できるようにnに比例する」と簡単に述べています。ですから、厳密な数学でそれを計算する方法をお尋ねします。

4

3 に答える 3

2

ネストされたループによって実行される操作の数は、2 つの長さの乗算です。

例えば：

for i=1 to 5
 for j = 1 to 10
  print j+i
 end
end

5*10 = 50 回印刷されます

あなたの例では、外側のループは sqrt(n) 回実行されます-つまり、k^2=n または k=sqrt(n) までです。内側のループも sqrt(n) 回実行されます。k はループ内で定数であり、 k^2+l^2>n のときに停止します。実行できる最大の回数は k=0 -> l^2>n => l>sqrt(n) です。したがって、反復の合計回数は最大で sqrt(n)*sqrt(n) - O(n) です。

于 2012-08-09T12:55:09.207 に答える
2

2 つのループがあり、一方が他方の内側にあります。

外部にはこの条件がありk*k < nます。k0SQRT(n)

内部ループには次の条件がk*k + l*l < nあります。しかし、これはより卑劣ですl0SQRT(n-k^2)SQRT(n)

したがって、最大反復回数はSQRT(n) * SQRT(n)whichよりも少なく、n反復ごとに一定数の操作が実行されます。

于 2012-08-09T12:56:04.463 に答える
1

アルゴリズムにかかる時間は、行われた操作の数に比例します。したがって、アルゴリズムにかかる時間が入力 (n) のサイズの増加に比例することを計算する必要があります。これを行うには、広範囲の n でアルゴリズムの完了のタイミングを計り、n vs timeグラフをプロットします。そうすることで、線形グラフが得られるはずです。

于 2012-08-09T12:40:35.793 に答える