算法设计与分析依赖循环时间复杂度分析

Question

我想知道我们如何导出 O(n3)。当然外循环是2 + 3(n+1) + 4n；中间循环是从 ( 2 + 3( i + 1) + 4i ) 的 i =1 开始的所有 n 的总和，但最内层循环的时间复杂度是多少，因为它取决于 k 而不是 i。

我想要分析最里面的循环，这样我就知道如何得到 O(n^3)。

Answer 1

如果分别采用内部两个循环，它们将具有相同的迭代次数 (𝑘)。结合起来，它们生成了 𝑖 和 𝑗 的所有可能组合，并且有 𝑘² 个。这是在没有外循环并且 𝑘 没有改变的情况下调整 sum 变量的次数。

由于外循环 𝑘 从 1 到 𝑛 变化，我们总共执行了 1² + 2² + 3² + ... + 𝑛² 总和更新语句。这是一个方锥体数，并且有这个封闭公式：

      𝑛³/3 + 𝑛²/2 + 𝑛/6

...即 O(𝑛³)。