c - 算法每行中的计算/步骤数

Question

我这里有一个函数，我可以看到它是 O(N^2)。但是，我想弄清楚每行到底使用了多少步/计算。

void hi(int n){
  for (int i=1; i <= n; i++) {        //line 1
    for (int k = i; k <= n; k++) {    //line 2
      puts("hi");                     //line 3
    }
  }
}

对于第 1 行，我相信它是 1+(N+1)+1。

第 2 行和第 3 行应该都是 sum(i=1 到 n)(3i+2)，但我不知道如何计算。这个总和是从哪里来的？

Answer 1

外部 for 语句执行一次……尽管它迭代了 n 次(由于开始条件、结束条件和更新部分)。这是“第 1 行”。

内部的 for 语句将在外部循环的每次迭代中执行一次。外层循环迭代n 次，因此内部for 语句执行n 次。这是“第 2 行”。

"hi" 将为内循环的每次迭代写入一次。对于外循环的每次迭代，内循环将迭代 n-i+1 次(产生 i 的值)。这意味着打印 "hi" 的次数是 n(对于 i == 1)+ n-1(对于 i == 2)+ .... 1(对于 i==n)。将它们相加，等于 n*(n+1)/2 次。这是“第 3 行”。