algorithm - 三重嵌套for循环的运行时推导

Question

我不得不做一个问题，需要我弄清楚这段代码的运行时间：

for (i = 1; i <= log(n); i = i + 1) {
    for (j = 1; j <= 2*i; j = 2*j) {
        for (k = 1; k <= log(j); k = k + 1) {
            print("[some arbitrary string]");
        }
    }
}

通过检查很明显这是Θ((log(n)^3)，因为每个for循环都是Θ(log(n))，但我不确定严格证明这一点的最佳方法是什么（例如，使用总和）。

标签： algorithmfor-loopbig-onested-loops

Answer 1

让我们log(n)用x( x = log(n)) 代替。然后

for (i = 1; i <= x; i = i + 1) {
    for (j = 1; j <= 2*i; j = 2*j) {
        for (k = 1; k <= log(j); k = k + 1) {
            print("[some arbitrary string]");
        }
    }
}

在第二个循环j中运行2. 让我们使用另一个替换来进行另一个具有相同渐近性的循环y = log(j)：

for (i = 1; i <= x; i = i + 1) {
    for (y = 0; y <= log(i); ++y) {
        for (k = 1; k <= y; k = k + 1) {
            print("[some arbitrary string]");
        }
    }
}

复杂度是O(x * log(x)^2) = O(log(n) * log(log(n))^2)。