algorithm - 我们的教授说对于双循环，T(n) 是 a*(n^2) + b*n + c。我认为这只是一个*(n^2)。确切答案是什么？

Question

这是我们教授制作的幻灯片。

示例 4:考虑这个简单的程序:

s = 0 
for i = 1 to n do
  for j = 1 to n do
    s= s+i+j
  endfor
endfor

T(n) = ?

即使对于这个非常简单的程序，也很难得到 T(n) 的精确表达式。 可以看到:循环迭代了n²次，循环体取 恒定的指令数。所以 T(n) = a*(n^2) + bn + c 对于一些常量 a、b、c。

下面是我的想法。让我们假设主体循环需要常数时间“a”。然后它本身将循环 a*(n^2) 次。所以，我不明白 b*n + c 是从哪里来的!实际答案是什么？

Answer 1

只发生一次的事情:设置s为0，设置i为1。

发生n次的事情:递增i，检查i是否小于n，设置j到 1，跳回到第 2 行。

发生n^2次的事情:递增j，检查j是否小于n，计算s+i+j并将结果存入s，跳转到第3行。