三for循环的复杂性[重复]

Question

我想知道下面代码的时间复杂度是O（n^3）还是O（n^2）

public void firstMethod() {
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            secondMethod();
        }
    }
}

public void secondMethod(){
    for (int i = 0; i < 6; i++) {
        System.out.println("This is a test to observe complexity");
    }
}

Answer 1

例如，像O（n³）这样的运行时复杂度意味着，当改变n时，运行时会像n³一样增加。

因此，由于您的代码中没有n，因此您可以随意更改，而不会对运行时产生任何影响。事实上，代码中没有任何变量对其运行时有任何影响，这意味着它是常数，我们将其表示为O（1）。

甚至像O（n²）这样的符号也经常以相当草率的方式使用。它应该始终伴随着一个明确的定义。但是，我们常常被迫假设n可能意味着数组的长度，或输入数中的位数或其他。

综上所述：

• 如果代码的运行时不依赖于某些变量输入，则会得到O（1）
• 在O（xyz）符号中，需要使用定义明确的变量名

Answer 2

这是O（1），因为运行时是恒定的。

现在，你是否写了以下内容：

public void firstMethod(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            secondMethod(n);
        }
    }
}

public void secondMethod(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println("This is a test to observe complexity");
    }
}

那么firstmethod对于运行时复杂度来说将是O（n^3）。