三重嵌套循环的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

每个循环是 O(n) 所以整体是 O(n^3)

Answer 2

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)

Answer 3

这将是 0(n^3) 复杂度，因为有 3 个循环，复杂度为 0(n)。随着循环次数的增加，方法的时间复杂度不断增加。所以你的程序中有 n 个循环，那么你的程序的时间复杂度将为 0(n^n)。您可以参考此http://www.programmerinterview.com/index.php/data-structures/big-o-notation/以获取更多参考。

三重嵌套循环的Big-O

Big-O of Triple Nested Loop

java

big-o