以下代码的 big-theta 是多少？ [我*我 <= n]

Question

for (k = 1; k <= n; k++)
   for (i = 1; i*i <= n; i++)
       // some O(1) operations`

我被要求找到这段代码的大θ。我计算 i*i < n。我可以将其重写为 I < n/I。所以追踪它我得到了以下信息：

I                # of interations
1               n
2               n/2
3               n/3
.                .
.                .
.                .
n/L              1

虽然我不确定如何从这里开始。我应该计算从 i=0 到 n 的 n/i 的总和吗？在这种情况下，当存在变量 (n) 时如何计算总和？

我知道，如果我找到 L，我就找到了所需的迭代次数。当它在 L = N/L 之后终止时，我无法根据 N 计算 L。

我对此很困惑。任何见解将不胜感激。

Answer 1

外循环有N次迭代。内部循环有平方根 ​​(N) 次迭代。将这两个相乘得到答案。