algorithm - 嵌套循环时间分析

Question

好的，我正在学习算法课并且正在准备考试......不幸的是......我无法理解嵌套循环时间分析背后的概念

这段代码中有三个循环

for (i=1->n)
 for (j=1->i)
   for (k=1->i)
     x=x+1;

我不明白如何找出答案：s任何答案都会有很大帮助谢谢大家:)

Answer 1

您需要总结循环，这只是需要计算的多个 sigma：

内 sigma 中的1是您在最内层循环中所做的事情的复杂性。

Answer 2

当 时i=1，k-loop 运行 1 次，j-loop 运行 1 次。Total=1.1=1 time
当 时i=2，k-loop 运行 2 次，j-loop 运行 2 次。Total=2.2=4 times
当 时i=3，k-loop 运行 3 次，j-loop 运行 3 次。Total=3.3=9 次
当 时i=n，k-loop 运行 n 次，j-loop 运行 n 次。总计=nn=n^2 次

因此，算法的时间复杂度为 O(1+2^2+3^2+...n^2)=O(n(n+1)(2n+1)/6) =O(n^3)