2

该算法取自 Alexander Shen 的伟大的“算法和编程：问题和解决方案”（即练习 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}

在文中，Shen 还简要地说，该算法执行的操作数量“与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

你有两个循环，一个在另一个里面。

外部有这个条件：k*k < n所以k从0最多到SQRT(n)

并且内部循环有这个条件：k*k + l*l < n所以l从0up 到SQRT(n-k^2). 但这比SQRT(n)

因此，最大迭代次数小于最大迭代次数SQRT(n) * SQRT(n)，n并且在每次迭代中都会完成恒定数量的操作。

于 2012-08-09T12:56:04.463 回答
1

您的算法所花费的时间与所进行的操作数量成正比。因此，您只需计算算法所花费的时间与输入 (n) 的增加大小成正比。您可以通过使用大范围的 n 对算法的完成进行计时并绘制n vs time图形来做到这一点。这样做应该会给你一个线性图。

于 2012-08-09T12:40:35.793 回答