java - 如何知道你的算法是否是 O(n2)？

Question

我创建了一个算法，但我不确定它是否是 O(n2)。我知道在 for 循环或嵌套循环中包含 for 循环意味着它的时间复杂度为 O(n2)。我不确定我创建的这个算法。为了只了解大 O 表示法，我将在注释中留下我的代码。我没有使用任何 Collections 或 API。

public class GraphTest {

public static void main(String args[]) {
    int m[][] =
            {
                    //values here...
            };

    if (check(m))
        System.out.print("True");
    else
        System.out.print("False");
}


static int s = 6;


static boolean check(int m[][]) {

    //instances here...


    if (s == 1)
        //return values here...

    if (s == 2)
       // return values here...


    for (int i = 0; i < s; i++) {
        //instance variable
        for (int j = 0; j < s; j++)

        if (){...}

        if (){...}

        else if (){...}

    }

    //return result here
}

}

Answer 1

例如，考虑这个 for 循环的复杂度为 O(n): for (int i=0; i<s; i++) {//...} ，这意味着复杂性以线性方式增加 s 。现在，您迭代 s外部 for 循环中的次数以及您迭代的外部循环的每次迭代 s次，因此迭代总数变为 s*s ->O(n2)。如果第二个 for 循环没有嵌套，它仍然是 O(n)。