三重嵌套循环的Big-O

Question

这种算法的时间复杂度（Big-O）是多少

for (int i = 1; i < n; i++) {
    for (int j = 1; j < i; j++) {
        for (int k = 1; k < j; k++) {
            x++;
        }
    } 
}

它是指数的吗？

假设输入为n

谢谢！

Answer 1

for (int i = 1; i < n; i++) { // O(n) time complexity
    for (int j = 1; j < i; j++) { // O(n) time complexity
        for (int k = 1; k < j; k++) { // O(n) time complexity
            x++;
        }
    } 
}

第一个循环执行n大量计算。您的第二个循环继续进行直到i达到其条件，即n，并k继续进行直至j达到其条件。每个循环都达到相同的条件，n

因此，每个循环的时间复杂度为O(n)；因为它们是嵌套的，所以您将每个n相乘，结果总时间复杂度为O(n^3)