时间戳

首页 > 解决方案 > 这个伪代码的渐近运行时间是多少？

time-complexity - 这个伪代码的渐近运行时间是多少？

问题描述

在下面的代码中，f()任何函数都需要花费 Θ(1) 的时间。时间复杂度应该是 Θ(n 4/3 )，有人能解释为什么吗？

for(int i = 1; i ≤ n; i = 2∗i) {
    for(int j = 1; j∗j∗j ≤ n; j = j+1) { 
        for(int k = 1; k ≤ i∗i; k = k + i) {
            f();
        }
    }
}

根据我的分析，第一个for循环需要 Θ(log 2 n) 时间，第二个for循环是 Θ(n 1/3 )，第三个for循环是 Θ(i)。所以我们总共有 Θ((log 2 n) × n 1/3 × i)。

因为 i 可以是 n，所以我们有 Θ((log 2 n) × n 1/3 × n) = Θ(n 4/3 log 2 n)。我的错误在哪里？

标签： time-complexitybig-o

解决方案

您的界限并不紧密，因为您算作iΘ(n)，但i平均而言不是 Θ(n)。考虑取值的序列i，并将它们相加以计算内部循环的迭代总数。我们现在可以忽略中间循环j，因为它独立于iand k。

的值序列i是 1、2、4、8、... 直到 n。如果我们说某个 r 的 n = 2 r，这是一个几何级数，总和为 2 r+​​1 - 1，大约是 n 的两倍，所以它是 Θ(n)。这包括外循环和内循环；中间的循环给出了另一个因子 Θ(n 1/3 )，因此整体复杂度是所需的 Θ(n 4/3 )。

推荐阅读