Почему вычислительная сложность O (n ^ 4)? - PullRequest
Новая
       4

Почему вычислительная сложность O (n ^ 4)?

50 голосов
/ 11 февраля 2020 
int sum = 0;
for(int i = 1; i < n; i++) {
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}

Я не понимаю, как, когда j = i, 2i, 3i ... последний for l oop выполняется n раз. Думаю, я просто не понимаю, как мы пришли к такому выводу на основании заявления if.

Редактировать: я знаю, как вычислить сложность для всех циклов, за исключением того, почему последний l oop выполняется i раз, основываясь на операторе мода ... Я просто не вижу, как это я. В принципе, почему j% i go не может до i * i, а не i?

Ответы [ 5 ]

49 голосов
/ 11 февраля 2020

Давайте обозначим циклы A, B и C: 

int sum = 0;
// loop A
for(int i = 1; i < n; i++) {
    // loop B
    for(int j = 1; j < i * i; j++) {
        if(j % i == 0) {
            // loop C
            for(int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
}
  • L oop A повторяется O ( n ) раз.
  • L oop B повторяет O ( i 2 ) раз за итерацию A . Для каждой из этих итераций:
    • j % i == 0 оценивается, что занимает O (1) время.
    • На 1 / i этих итераций, l oop C повторяется j раз, выполняя O (1) работу за итерацию. Поскольку j в среднем равно O ( i 2 ), и это делается только для 1 / i итераций l oop B, средняя стоимость O ( i 2 / i ) = O ( i ).

Умножая все это вместе, мы получаем O ( n × i 2 × (1 + i * 1052) *)) = O ( n × i 3 ). Поскольку i в среднем равно O ( n ), это O ( n 4 ).

Хитрая часть этого говорит, что условие if верно только 1 / i времени:

По сути, почему j% i * 1102 не может * до i * i, а не i?

На самом деле, j делает go до j < i * i, а не только до j < i. Но условие j % i == 0 выполняется в том и только в том случае, если j кратно i.

Кратные значения i в диапазоне составляют i, 2*i, 3*i , ..., (i-1) * i. Их существует i - 1, поэтому l oop C достигается i - 1 раз, несмотря на то, что l oop B повторяется i * i - 1 раз.

16 голосов
/ 11 февраля 2020
  • Первый l oop потребляет n итераций.
  • Второй l oop потребляет n*n итераций. Представьте себе случай, когда i=n, тогда j=n*n.
  • Третья l oop потребляет n итераций, потому что она выполняется только i раз, где i ограничен n в наихудший случай.

Таким образом, сложность кода составляет O (n × n × n × n).

Надеюсь, это поможет вам понять.

6 голосов
/ 11 февраля 2020

Все остальные ответы верны, я просто хочу изменить следующее. Я хотел видеть, было ли уменьшение выполнения внутреннего kl oop достаточным, чтобы уменьшить фактическую сложность ниже O(n⁴).. Поэтому я написал следующее: 

for (int n = 1; n < 363; ++n) {
    int sum = 0;
    for(int i = 1; i < n; ++i) {
        for(int j = 1; j < i * i; ++j) {
            if(j % i == 0) {
                for(int k = 0; k < j; ++k) {
                    sum++;
                }
            }
        }
    }

    long cubic = (long) Math.pow(n, 3);
    long hypCubic = (long) Math.pow(n, 4);
    double relative = (double) (sum / (double) hypCubic);
    System.out.println("n = " + n + ": iterations = " + sum +
            ", n³ = " + cubic + ", n⁴ = " + hypCubic + ", rel = " + relative);
}

После выполнения этого становится очевидным , что сложность на самом деле n⁴. Последние строки вывода выглядят так: 

n = 356: iterations = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0.12383254507467704
n = 357: iterations = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0.12383580700180696
n = 358: iterations = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0.12383905075183874
n = 359: iterations = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0.12384227647628734
n = 360: iterations = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0.12384548432498857
n = 361: iterations = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0.12384867444612208
n = 362: iterations = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0.1238518469862343

Это показывает, что фактическая относительная разница между фактическим n⁴ и сложностью этого сегмента кода является асимптотикой c фактического значения около 0.124... (на самом деле 0,125). Хотя это не дает нам точное значение, мы можем вывести следующее:

Сложность времени n⁴/8 ~ f(n), где f - ваша функция / метод.

  • Википедия на страницах обозначений Big O в таблицах «Семейства обозначений Бахмана – Ландау» указано, что ~ определяет предел двух сторон операнда. Или:

    f асимптотически равен g

(я выбрал 363 в качестве исключенной верхней границы, поскольку n = 362 - последнее значение, для которого мы получаем разумный результат. После этого мы превышаем длинный пробел и относительное значение становится отрицательным.)

Пользователь kaya3 выяснил следующее:

Константа асимптотики c равна точно 1/8 = 0,125, кстати; вот точная формула через Wolfram Alpha .

2 голосов
/ 12 февраля 2020

Удалить if и по модулю без изменения сложности

Вот оригинальный метод: 

public static long f(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < i * i; j++) {
            if (j % i == 0) {
                for (int k = 0; k < j; k++) {
                    sum++;
                }
            }
        }
    }
    return sum;
}

Если вас смущают if и по модулю, вы можете просто выполнить рефакторинг их с расстояния j, прыгающих прямо с i до 2*i до 3*i ...: 

public static long f2(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i; j < i * i; j = j + i) {
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

Чтобы еще проще вычислить сложность, вы можете ввести посредника j2 переменная, так что каждая переменная l oop увеличивается на 1 на каждой итерации: 

public static long f3(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j2 = 1; j2 < i; j2++) {
            int j = j2 * i;
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

Вы можете использовать отладку или old-school System.out.println, чтобы проверить, что триплет i, j, k всегда одинаковые в каждом методе.

Выражение закрытой формы

Как уже упоминалось другими, вы можете использовать тот факт, что сумма первых n целых чисел равна n * (n+1) / 2 (см. три angular числа ). Если вы используете это упрощение для каждого l oop, вы получите: 

public static long f4(int n) {
    return (n - 1) * n * (n - 2) * (3 * n - 1) / 24;
}

Очевидно, что не такой же сложности, как исходный код, но он возвращает те же значения.

Если вы гуглите первые термины, вы можете заметить, что 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731 появляются в "числа Стирлинга первого рода: s (n + 2, n)." , с двумя 0 добавлено в начале. Это означает, что sum является числом Стирлинга первого рода s(n, n-2).

0 голосов
/ 11 февраля 2020

Давайте посмотрим на первые два цикла.

Первый простой, он цикличен от 1 до n. Второй интереснее. Это идет от 1 до я в квадрате. Давайте рассмотрим несколько примеров: 

e.g. n = 4    
i = 1  
j loops from 1 to 1^2  
i = 2  
j loops from 1 to 2^2  
i = 3  
j loops from 1 to 3^2

В сумме i and j loops в совокупности имеют 1^2 + 2^2 + 3^2.
. Существует формула для суммы первых n квадратов, n * (n+1) * (2n + 1) / 6, что примерно равно O(n^3).

У вас есть последний k loop, который повторяется от 0 до j тогда и только тогда, когда j % i == 0. Поскольку j изменяется от 1 до i^2, j % i == 0 верно для i раз. Поскольку i loop повторяется по n, у вас есть один дополнительный O(n).

Таким образом, у вас есть O(n^3) с i and j loops и еще O(n) с k loop на общую сумму O(n^4)

...