algorithm - 需要帮助计算该算法的操作复杂性

Question

该算法取自 Alexander Shen 的伟大著作《算法与编程:问题与解决方案》(即练习 1.1.28)。

以下是我从俄语翻译的内容，如有错误或歧义，请原谅。如果您有这样的感觉，请纠正我。

算法应该做什么

With given natural n algorithm calculates the number of solutions of inequality

x*x + y*y < n 

in natural (non-negative) numbers without using manipulations on real numbers

以帕斯卡为单位

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成正比，可以计算”。所以我问你如何用严格的数学来计算它。

Answer 1

你有两个循环，一个在另一个循环内。

外部有这样的条件:k*k < n所以k来自0高达SQRT(n)

并且内部循环具有以下条件:k*k + l*l < n所以l来自0高达SQRT(n-k^2) 。但这比 SQRT(n) 小

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