分析时间复杂度的算法

Question

我正在分析一个算法，我想知道我是否正确。对于这个算法，我只计算那些带有***的行中的乘法。

以下是该算法：

所以我从最内层开始，可以看到有两个操作（两个乘法）。

现在我正在查看最内层的两个循环，所以我可以确定p = p * 20 * z被执行了（j）+（j-1）+（j-2）+（j-3）... 1次。这恰好等于j（j + 1）/ 2。

因此，在总共有两个乘法的情况下，它会发生2 *（j（j + 1）/ 2）次。

然后最后，“i”循环恰好发生n次，因此总共是n（2 *（n（n + 1）/ 2））。

这是我的思维过程。我正确吗？谢谢。

- 0xSina

---

你不是。最终结果应该只包含 n。你那里有 j。 - Karoly Horvath

谢谢您的快速回复。它应该是n(2 * (n(n+1)/2))吗？ - 0xSina

其实，我认为那只是一个打字错误，因为用 j 替换 n 对于他在那里经历的推导是正确的，因为 n 是最大的 j。@PragmaOnce 是的，尽管显然可以简化很多。 - Charles Keepax

是的，这就是我在原问题中想做的事情，但忘记将j替换成n了。谢谢你们两个。有人想发表答案吗，这样我可以将其标记为正确答案吗？ - 0xSina

Answer 1

您的思路是正确的。您需要用 n（n 是 j 可以假定的最大值）替换 j 项，但这可能是一个笔误。

此外，您可以从您现在的位置进一步简化：

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

=> O(n^3)

最后一步是因为n的立方项将比n的平方项增长得多，我们可以说它将在大n时占据运行时间的主导地位。我想提到的另一个点是，你也许应该把将p存储为一个操作考虑进去，除了两个乘法，尽管显然这不会改变简化后的Big-O运行时间。

- Charles Keepax

---

谢谢，简化加一！ - 0xSina

Answer 2

在这个例子中，如果你能发现所有三个循环都具有相同的退出条件直到n，则可以简化计算：

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

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

- sll

Answer 3

这是如何系统地获得您算法的增长顺序的方法：

- Mohamed Ennahdi El Idrissi