c - 我的老师声称这个代码块在 O(n) 时间内运行……这是为什么呢？

Question

我的老师声称这个代码块将花费 O(n) 的时间来执行。我想弄清楚为什么。我意识到捆绑在一起的两个 for 循环将是一个算术级数.....我的逻辑方法是如果 K = 3，则内部循环将运行三次，然后两次，然后一次。如果 K = 2，则内部循环将运行两次，一次，然后停止。

用数学术语来说，对于 k = 3，它将是 N、N-1、N-2

后来我能够使用等差级数公式得到N*(N + (N-(N-1))/2..

我不知道如何处理 while 循环。

我所能推测的是，当 N =4 时，循环运行两次，直到 N = 9，循环运行三次......我将如何进行数学设置？

最终结果是N*(N+(N-(N-1)))/2 + O(while循环)得到O(N)？

如有任何建议，我们将不胜感激。

void doit(int n) {
     int k = 0; int m = n; int s = 0;
     while (m <= n) {
         k = k + 1;
         m = k * k;
     }

     for (int i = 0; i < k; i++) {
         for (int j = i; j < k; j++) {
             s = s + m;
             m = m - 1;
         }
     }
 }

Answer 1

循环本身是 O(k^2)，但事情是在它之前发生的。 while 循环找到大于 n 的最小平方数 m = k^2，所以基本上是因为 m 与 n 相关，最终结果实际上变为 O(n)。