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最多是序列前x项的总和(1、2、3...)。即:

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)) 次。