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

Question

我已经创建了一个算法，但我不确定它是否为O(n2)。我知道在for循环或嵌套循环中使用for循环将意味着它是O(n2)。我不确定我创建的这个算法。出于了解Big O符号的目的，我将我的代码留在注释中。我没有使用任何集合或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的线性增加而增加。现在，您在外部for循环中迭代s次数，对于外部循环的每次迭代，您将迭代s次，因此总迭代次数变为s*s->O(n2)。如果第二个for循环没有嵌套，它仍然是O(n)。