我们的教授说双环,T(n)是*(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'.然后,它本身将被循环一段时间*(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行.