math - 当 n > 0 时，n 可以 floor(sqrt(n)) - 1 多少次？

Question

完整的问题是

假设我们有一个函数

void foo(int n){
  int i = n;
  while(i > 0){
    //do an O(n) operation
    //do some O(1) operations
    i = sqrt(i) - 1;
  }
}

我只需要找到渐近边界，但在我弄清楚循环实际运行了多少次之前我无法做到这一点。我猜这是另一个涉及平方根的求和，但我不确定如何开始。

Answer 1

您想知道循环将执行多少次。

如果 i < 2，则循环最多执行两次。

因此如果 i < 4 循环将最多执行 3 次。

因此如果 i < 16 循环将最多执行 4 次。

因此如果 i < 256 循环将最多执行 5 次。

...

等等

你看到如果 i < 2^(2^m)，那么循环最多执行 (m+2) 次。

这意味着它会执行的次数的顺序是log(log(n)),

因为 i 从 n 开始。

因此整体复杂度为O(n*log(log(n))。

(如果每次迭代中的 O(1) 操作数是常数。)