1

这是我们教授的幻灯片。

示例 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 来自哪里！实际答案是什么？

4

2 回答 2

5

发生一次的事情：设置s为 0 和设置i为 1。

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

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

于 2013-09-13T21:04:53.860 回答
1

(a*(n^2) + b*n + c) / (a*(n^2)) = 1 + b/(a*n) + c/(a*(n^2)) -> 1作为 n -> 无穷大。

于 2013-09-13T21:06:42.723 回答