我的老师声称此代码块是在O（n）时间中运行的……为什么？

Question

我的老师声称此代码块将花费O（n）时间来执行。我试图找出原因。我意识到捆绑在一起的两个for循环将是一个算术序列.....我的逻辑方法是，如果K = 3，则内部循环将运行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环路发现的最小平方数m = k^2是大于n，所以基本上是因为m涉及n最终的结果实际上变得O(n)。