时间戳

首页 > 解决方案 > 识别小函数的大 O 表示法

c - 识别小函数的大 O 表示法

问题描述

我的教授说这个函数的时间复杂度是O(sqrt(n)). 但是，我不明白他是如何得到这个答案的，也不明白这个逻辑是怎样的sqrt(n)，也许我数学不好。

如何确定此类函数的时间复杂度？


    int foo(int n) {
      int k = 0, sum = 0;
      while (2*sum-k < n) {
         k++;
         sum += k;
       }
      return k;
    }

答案：在第 k 次迭代sum=1+2+3+...+k = k*(k+1)/2
中，while 循环继续，直到2*sum-k = k^2大于 n。
因此，迭代次数等于 sqrt(n)。
在每次迭代中，运行时间为 O(1)。
因此，总运行时间为 O(sqrt(n))。

标签： ctime-complexitybig-o

解决方案

您已经有了自己问题的答案。但是，如果您使用 运行代码N = 100，您会注意到：

 I=1 k=0 (2*sum-k)=0
 I=2 k=1 (2*sum-k)=1
 I=3 k=2 (2*sum-k)=4
 I=4 k=3 (2*sum-k)=9
 I=5 k=4 (2*sum-k)=16
 I=6 k=5 (2*sum-k)=25
 I=7 k=6 (2*sum-k)=36
 I=8 k=7 (2*sum-k)=49
 I=9 k=8 (2*sum-k)=64
 I=10 k=9 (2*sum-k)=81

您可以清楚地看到2*sum-k = k^2，如果您查看N迭代次数I，您可以看到 for N=100，that I=10so I=sqrt(N)。您可以使用其他N尺寸进行测试，但您会注意到相同的模式。

因此，变量sum, 将包含第一个自然数的总和K 

sum=1+2+3+...+k = k*(k+1)/2

因此，2 * sum - k => 2 * (k*(k+1)/2) - k => k * (k + 1) - k => k^2 + k - k => k^2。所以，从2 * sum-k < n，我们现在可以拥有k^2 < n。因此， k = sqrt(n)，因为k基本上是计算迭代次数，

因此，迭代次数等于 sqrt(n)。

现在查看 while 主体，只有语句 k++;and sum += k;，这基本上是2x恒定计算，因此

在每次迭代中，运行时间为 O(1)。

最后：

因此，总运行时间为 O(sqrt(n))。

推荐阅读