Как узнать, является ли ваш алгоритм O (n2)? - PullRequest
Новая
       5

Как узнать, является ли ваш алгоритм O (n2)?

0 голосов
/ 18 января 2020

Я создал алгоритм, но я не уверен, что это O (n2). Я знаю, что наличие для l oop в пределах для l oop или вложенного l oop означало бы, что это 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
}

}

1 Ответ

0 голосов
/ 18 января 2020

Рассмотрим, например, что для l oop это O (n): for (int i=0; i<s; i++) {//...}, что означает линейное увеличение сложности с s. Теперь вы повторяете s раза во внешнем для l oop, и для каждой итерации внешнего l oop вы повторяете s раз, следовательно, общее количество итераций становится s*s -> O (n2) , Если бы секунда для l oop не была вложенной, она все равно была бы O (n).

...