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+(N+1)+1。

第2行和第3行应该都是sum(i=1到n)(3i+2)，但我不知道如何。这个求和从何而来?

Answer 1

外部的for语句只执行一次…尽管如此，它迭代n次(由于开始条件、结束条件和更新部分)。这是"line 1"

内部的for语句将在每次外部循环迭代时执行一次。外部循环迭代n次，因此内部for语句执行n次。这是"line 2"

"hi"将在每次内循环迭代时写入一次。对于外循环的每次迭代(产生i的值)，内循环将迭代n-i+1次。这意味着"hi"的打印次数是n(用于i == 1) + n-1(用于i == 2) + ....1(用于i==n)。把它们加起来，等于n*(n+1)/2倍。这是"line 3"

Answer 2

第1行执行1次。但是，它执行1次初始化，n次比较和递增。

第2行执行n次。然而，它执行n个初始化，n*(n+1)/2个比较和递增。

第3行执行n*(n+1)/2次。由于http://mathcentral.uregina.ca/qq/database/qq.02.06/jo1.html

因此操作总数为1 + 3n + 3n*(n+1)/2。