Почему это O (N ^ 3), а не O (N ^ 4)? - PullRequest
Новая
       16

Почему это O (N ^ 3), а не O (N ^ 4)?

0 голосов
/ 08 ноября 2018 
public static int g(LinkedList<Integer> list) {
    int t = 0;

    for (int i = 0; i < list.size(); i++) {
        int tgt = list.get(i);

        for (int j = i + 1; j < list.size(); j++) {
            if (list.get(j) == tgt) 
                t += list.get(j);
        }
    }

    return t;
}

Разве оператор if не должен усложнять O (N ^ 4)?

Ответы [ 2 ]

0 голосов
/ 08 ноября 2018

Если операторы не являются циклами.

Каждое получение может принимать O (n), но операторы в его теле выполняются после условия. Таким образом, оператор if принимает O (n) + O (n) (для двух получает), то есть O (n).

Он вложен в два вложенных цикла по списку размера n, поэтому в целом это O (n ^ 3).

0 голосов
/ 08 ноября 2018

Операторы if не имеют никакого отношения к временной сложности - операция оператора if имеет временную сложность O(1), но работа в операторе if может иметь большую временную сложность.

Это потому что list.get(i) имеет O(n). Чтобы получить n: th элемент LinkedList, вам нужно пройти n раз в списке, чтобы найти его. Это связано с тем, что LinkedList не сохраняет свои индексы, только первый и последний элемент в списке, а затем его непосредственные соседи.

Это сложность времени для каждой из ваших функций: 

public static int g(LinkedList<Integer> list) {
    int t = 0;

    for (int i = 0; i < list.size(); i++) {           // O(n) - loop
        int tgt = list.get(i);                        // O(n)

        for (int j = i + 1; j < list.size(); j++) {   // O(n) - loop
            if (list.get(j) == tgt)                   // O(n)
                t += list.get(j);                     // O(n)
        }
    }

    return t;
}

Поскольку вы выполняете итерации только по 2 циклам, это первоначально сделает сложность времени O(n^2). Каждый из 3 вызовов list.get(i) усложнит время на O(n), что приведет к 3*O(n). Однако по умолчанию он равен O(n), а окончательная сложность по времени равна O(n) * O(n) * 3*O(n) => O(n^3)

.

Extra

На несвязанной ноте : Вы видите, что когда вы дважды вызываете list.get(j) в самом внутреннем цикле, вы заставите программу дважды выполнить итерацию по списку, даже если вы только что получили значение. 

if (list.get(j) == tgt)
    t += list.get(j);

Скорее всего, процессор или компилятор оптимизирует это и сохранит значение в кеше, но все равно неплохо один раз вызвать list.get(j) и сохранить его значение.

...