这个嵌套三元组for循环的复杂性是多少？

Question

我已经在StackOverflow上进行了一些搜索,并且已经了解了j循环的复杂性,即.然而,随着k循环的嵌套添加,我很困惑为什么复杂性变得复杂.有人能帮助我理解这个吗？O(n2)O(n3)

从我的理解,i-循环有n次迭代和第j环具有1 + 2 + 3 + ... + n次迭代n*(n+1)/2是.O(n2)

for(i = 1; i < n; i++) {   
    for(j = i+1; j <= n; j++) {
        for(k = i; k <= j; k++) {
           // Do something here...
        }
    }
}

编辑:谢谢你所有的帮助人:) Balthazar,我写了一段代码,根据它们所处的循环增加计数器,有点粗略的逐步方式:

#include <iostream>

int main(int argc, const char * argv[])
{
    int n = 9;
    int index_I = 0;
    int index_J = 0;
    int index_K = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
                index_K++;
            }
            index_J++;
        }
        index_I++;
    }
    std::cout << index_I << std::endl;
    std::cout << index_J << std::endl;
    std::cout << index_K << std::endl;
    return 0;
}

我将此代码从n = 2运行到n = 9,增量为1,并得到以下序列:

因此,从计数器可以看出:i = n-1给出O(n)和j =((n-1)*n)/ 2的复杂度,给出了复杂性.K的模式难以发现,但众所周知K取决于J,因此:O(n2)

k = ((n+4)/3)*j = (n*(n-1)*(n+4))/6 给予复杂性 O(n3)

我希望这将有助于未来的人们.

EDIT2:感谢Dukeling的格式化:)在最后一行也发现了一个错误,现在纠正了

Answer 1

如果您习惯使用Sigma Notation,这是一种推断算法时间复杂度的正式方法(精确的嵌套循环):

注意:公式简化可能包含错误.如果您发现任何问题,请告诉我.

Answer 2

k循环具有O(ji)复杂度

j循环具有O((ni)*(ni))复杂度

i循环具有O(n*n*n)= O(n ^ 3)复杂度

无论如何,你知道它不是O(n ^ 2),因为前两个循环是O(n ^ 2)并且它不超过O(n ^ 3),因为只有3个循环

Answer 3

看一下这个示例来评估最坏情况的复杂性。

本质上，如果你逐行评估它，你将得到类似 O(n^3 / C) 的结果，其中 C 是某个常数，通常在此类评估中跳过，导致 O(n^3)。