algorithm - 嵌套几何序列的复杂性

Question

下面的代码实际上受 O(n^2) 限制，谁能解释一下原因？

for (int i = 1; i < n; i++) {
    int j = i;
    while (j < n) {
        do operation with cost O(j)
        j = j * 3;
    }
}

Answer 1

没那么棘手。

---

你的内部循环的复杂性形成了一个 geometric progression总复杂度 O(n)。

没有一路填写细节(这似乎是一个硬件问题)，请注意几何序列的公式是

a_0 (q^k - 1)/q - 1, (a_0 = 第一个元素，q = 乘数，k = num 个元素)。

你的 q^k 是 O(n)。

---

你的外循环是 O(n)。

---

由于它是一个嵌套循环，并且内部项不依赖于外部索引，因此可以相乘。