时间复杂度分析算法

Question

我正在分析一个算法，我只想知道我是否在正确的轨道上。

对于这个算法，我只计算其中包含*的直线上的乘法。

下面是算法：

​

​

因此，我从最里面的一行开始，我可以看到那里有两个操作(我正在查看的两个multiplications).

• Now --

1. 循环)，所以我可以判断p=p*20*z被执行了(j) + (j-1)+(j-2)+(j-3)...1时间。这恰好等于j(j+1)/2.
2. So，因为有两个乘法，所以它是2 * (j(j+1)/2)。最后，"i“循环恰好发生了n次，因此，总的来说，它是n(2 * (n(n+1)/2)).

这是我的思维过程。我说的对吗？谢谢。

Answer 1

你的思维过程是正确的。您需要将j项替换为n (n是j可以假定的最大值)，但这可能是一个错误。

此外，您可以进一步简化您所处的位置：

n(2*(n(n+1)/2))
2*n*(n^2+n)/2
n^3+n^2

=> O(n^3)

最后一步是因为n立方项将以比n平方项大得多的速度增长，我们可以说它将主导大n的运行时。我要提到的其他一点是，也许您应该考虑将存储p作为一个运算以及两个乘法，尽管这显然不会改变简化的大o运行时。

Answer 2

如果可以发现所有三个循环都有相同的退出条件，则可以简化此示例中的计算up to n。

1. i <= n
2. j <= n
3. k <= j

基本上，第三个循环也会运行n迭代，因为j <= n所以k <= n，这意味着复杂性将是n * n * n = O(n ^ 3)。

Answer 3

这就是如何有条不紊地获得算法增长顺序的方法：

​

​