计算函数的时间复杂度

Question

需要有关如何计算时间复杂度的帮助

int func(int n) {
    int a = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= n - i; ++j) {
            for (int k = 0; k <= n - i; ++k) {
                for (int o = 1; o <= i; ++o) {
                    a++;
                }
            }
        }
    }
}

这是我得到的，但我不确定这是否正确，也不知道如何继续。

Answer 1

3 个外循环（索引为

i

、

j

和

k

）将简单地执行 O(n) 次，因此它们的总复杂度为 O(n^3)。

内部循环（带有索引

o

）需要更多分析。

想象一下只有 1 个外循环的函数的简化版本：

for (int i = 1; i <= n; ++i) {
   for (int o = 1; o <= i; ++o) {
      a++;
   }
}

最里面的循环体将执行 1+2+3+...+n 次，即 n*(n+1)/2，即 O(n^2)，这就是这个简化版本的复杂度。

以此类推，你整个函数的整体复杂度是O(n^4)。