c - 关于代码时间复杂度计算的问题

Question

我知道所有符号(大 O 和小 o、大 Omega、小 omega)边界和一切。但我在这方面还是个新手，我读了这段代码:

   void Function(int n)
    {  int i=1, s=1;
       while(s<=n) 
        { 
          i++;
          s=s+i;
          printf("*");
        }
     }

书上说运行时间是sqrt(n)或者O(sqrt(n))。谁能帮我看看这是怎么回事？

Answer 1

在这个算法中，关键是计算while循环执行了多少次。我们称它为 x。要找到 x，我们必须了解 s 在 x 方面的行为。

变量 s 最多是序列 (1, 2, 3...) 前 x 项的总和。即:

s = x*(x+1)/2

现在我们必须理解 x 是如何根据 n 表现的。即我们需要找到x，如:

x*(x+1)/2 <= n

x*x+x <= 2n

x <= 1/2 * (sqrt(8n+1)-1)

因此，给定一些 n，循环将迭代 O(1/2 * (sqrt(8n+1)-1)) = O( sqrt(n)) 次。