algorithm - 程序的运行时间

Question

for i from 1 to n*n do
 j=n
 while j > 0 do
   j--

如果我们使用求和，我发现运行时间严格为 $$\Theta(n^6)$$，但我不确定这是否正确。有什么指点吗？

Answer 1

运行时间的计算是这样的:

• 第一个 for 循环 for i from 1 to n*n do 总共迭代 n*n 次。
• 第二个while循环
  j=n 当 j > 0 时 j--
  总共迭代 n 次。

因此，总运行时间相当于 O(n*n)*O(n) = O(n^3)。