Не можете понять, почему сложность двух вложенных циклов равна O (n)? - PullRequest
Новая
       20

Не можете понять, почему сложность двух вложенных циклов равна O (n)?

5 голосов
/ 26 апреля 2019

Таким образом, в следующем коде j выполняется n раза, когда i = 0.Как только я повторяю один раз (i = 0,2,3....n), j никогда не выполняется, так как условие оператора if истинно и n добавляется к j.i продолжает повторяться до n, когда цикл (оба цикла) прекращает выполнение и метод завершается. 

public static void main(String[] args) {
        int x = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(j < i) j = j + n;
                else x = x+1;
            }
        }
    }

Моя путаница заключается в том, почему сложность времени равна O(n), когда оба циклаитерация до n в некоторый момент, i всегда итерация до n и j итерация до n, когда i = 0 ... Разве это не должно быть O(n^2), поскольку мы умножаем nxn?

Ответы [ 2 ]

5 голосов
/ 26 апреля 2019

Самое внутреннее условие, if (j < i), всегда истинно, когда i >= 1, так как j инициализируется как 0. Поскольку вы увеличиваете j на n внутри оператора if, это эквивалентно вызову break;, таким образом выходя из самого внутреннего цикла for после одной итерации.

Итак, чтобы ответить на ваш вопрос, сложность времени равна O(n), потому что самый внутренний цикл for будет повторяться только 2n - 1 раз:

  • Итерация к n, когда i == 0.
  • Когда i > 0, он повторяется только один раз.

Спасибо за Phoenix1355 за указание на это ниже в комментариях.

1 голос
/ 26 апреля 2019

Вы также можете анализировать сложность времени, передавая различные входные данные (n). Я скопировал тот же код и создал отдельную функцию: 

private static void testComplexity(int n) {
    int x = 0;
    int N1 = 0, N2 = 0;
    for (int i = 0; i < n; i++) {
            N1++;
        for (int j = 0; j < n; j++) {
                N2++;
            if(j < i) j = j + n;
            else x = x+1;
        }
    }
    System.out.println("input is : " + n + " and N1 " + N1 + " and N2 : " + N2);
}

public static void main(String[] args) {
    int[] inputs = new int[]{10, 100, 1000, 10000};
    for(int input : inputs) testComplexity(input);
}

Вывод:

ввод: 10 и N1: 10 и N2: 19
ввод: 100 и N1: 100 и N2: 199
ввод: 1000 и N1: 1000 и N2: 1999
ввод: 10000 и N1: 10000 и N2: 19999

Я создал другую функцию для QUADRATIC 

    private static void testComplexity2(int n) {
    int N1 = 0, N2 = 0;
    for (int i = 0; i < n; i++) {
            N1++;
        for (int j = 0; j < n; j++) {
                N2++;
        }
    }
    System.out.println("input is : " + n + " and N1 " + N1 + " and N2 : " + N2);
}

Вывод:

ввод: 10 и N1 10 и N2: 100
ввод: 100 и N1 100 и N2: 10000
ввод: 1000 и N1 1000 и N2: 1000000
ввод: 10000 и N1 10000 и N2: 100000000

Видите разницу?

...