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

50
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цикл выполняется n раз. Думаю, я просто не понимаю, как мы пришли к такому выводу на основании ifзаявления.

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

user11452926
источник
5
Вы можете уменьшить сложность этого кода за счет нескольких крупных факторов. Подсказка : сумма чисел от 1 до n равна ((n + 1) * n) / 2. Подсказка 2 : for (j = i; j < i *i; j += i)тогда вам не нужно проверять модуль (потому что jгарантированно делится на i).
Эллиот Фриш
1
Функция O () является функцией парковки, поэтому любой цикл в этом примере добавляет сложности. Второй цикл работает до п ^ 2. операторы if игнорируются.
Кристоф Бауэр
11
ifЗаявления @ChristophBauer абсолютно не игнорируются. Это ifутверждение означает, что сложность составляет O (n ^ 4) вместо O (n ^ 5), потому что это заставляет самый внутренний цикл выполнять только iвремена вместо i*iвремен для каждой итерации второго цикла.
kaya3
1
@ kaya3 полностью пропустил часть. Так что k < n^2это O (n ^ 5), но знание (понимая if) предполагает O (n ^ 4).
Кристоф Бауэр
1
Если это не просто классное упражнение, измените второй цикл на for (int j = i; j <i * i; j + = i)
Cristobol Polychronopolis

Ответы:

49

Давайте обозначим петли 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++;
            }
        }
    }
}
  • Цикл A повторяется O ( n ) раз.
  • Цикл B итерацию O ( я 2 ) раз в итерации . Для каждой из этих итераций:
    • j % i == 0 оценивается, что занимает O (1) время.
    • На 1 / i из этих итераций цикл C повторяется j раз, выполняя O (1) работу за итерацию. Поскольку j в среднем равно O ( i 2 ), и это делается только для 1 / i итераций цикла B, средняя стоимость равна O ( i 2).  /  i ) = O ( i ).

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


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

В принципе, почему я не могу пойти на я * я, а не я?

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

В кратные iпределах являются i, 2*i, 3*i..., (i-1) * i. Они есть i - 1, поэтому цикл C достигается i - 1раз, несмотря на то, что цикл B повторяется i * i - 1.

kaya3
источник
2
В O (n × i ^ 2 × (1 + i)) почему 1 + i?
Солей
3
Поскольку ifусловие занимает O (1) времени на каждую итерацию цикла B. Здесь преобладает цикл C, но я посчитал его выше, поэтому он просто «показывает мою работу».
kaya3
16
  • Первый цикл потребляет nитерации.
  • Второй цикл потребляет n*nитерации. Представьте себе случай, когда i=n, тогда j=n*n.
  • Третий цикл использует nитерации, потому что он выполняется только iраз, где в худшем случае iограничен n.

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

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

Мухаммед Дейфалла
источник
6

Все остальные ответы верны, я просто хочу изменить следующее. Я хотел посмотреть, было ли сокращение выполнения внутреннего k-цикла достаточным, чтобы уменьшить реальную сложность ниже. 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⁴и сложностью этого сегмента кода является асимптотическим фактором к значению вокруг0.124... (фактически 0,125). Хотя это не дает нам точное значение, мы можем вывести следующее:

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

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

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

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

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

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

TreffnonX
источник
5
Конечно, O (n⁴) * 0,125 = O (n⁴). Умножение времени выполнения на положительный постоянный коэффициент не меняет асимптотическую сложность.
Ильмари Каронен
Это правда. Однако я пытался отразить фактическую сложность, а не оценку сверху. Поскольку я не нашел другого синтаксиса для выражения сложности времени, кроме О-нотации, я вернулся к этому. Тем не менее, это не на 100% разумно, чтобы написать это так.
TreffnonX
Вы можете использовать нотацию о-о, чтобы сказать, что сложность времени есть n⁴/8 + o(n⁴), но в n⁴/8 + O(n³)любом случае можно дать более строгое выражение с большим О.
kaya3
@TreffnonX big OH - это математически обоснованная концепция. То, что вы делаете, в корне неверно / бессмысленно. Конечно, вы можете переопределять математические концепции, но это большая банка червей, которую вы открываете. Способ определить его в более строгом контексте - это то, что описал kaya3, вы идете на порядок «ниже» и определяете его таким образом. (Хотя в математике вы обычно используете взаимность).
paul23
Ты прав. Я исправил себя снова. На этот раз я использую асимтотический рост до того же предела, как определено в нотациях семейства Бахман-Ландау на en.wikipedia.org/wiki/Big_O_notation#Little-o_notation . Я надеюсь, что теперь это математически правильно, чтобы не
вызывать
2

Удалить 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 переменную, чтобы каждая переменная цикла увеличивалась на 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;
}

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

Закрытое выражение формы

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

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

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

Первый простой, он цикличен от 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)

Сильвиу Бурча
источник
Я знаю, как вычислить сложность для всех циклов, за исключением того, почему последний цикл выполняется i раз, основываясь на операторе мода ... Я просто не понимаю, как это я. В принципе, почему я не могу пойти на я * я, а не я?
user11452926
1
@ user11452926 скажем, что я был 5. j будет идти от 1 до 25 во 2-м цикле. Тем не менее, j % i == 0только когда j составляет 5, 10, 15, 20 и 25. 5 раз, как значение i. Если бы вы записали числа от 1 до 25 в квадрате 5 x 5, только 5-й столбец будет содержать числа, кратные 5. Это работает для любого числа i. Нарисуйте квадрат n на n, используя числа от 1 до n ^ 2. N-й столбец будет содержать числа, кратные n. У вас есть n строк, поэтому n чисел от 1 до n ^ 2 делится на n.
Сильвиу Бурча
Спасибо! имеет смысл! Что если это будет произвольное число, например 24, а не 25, будет ли работать квадратный трюк?
user11452926
25 наступает при iпопадании 5, поэтому в jциклах от 1 до 25 вы не можете выбрать произвольное число. Если ваш 2-й цикл будет идти к фиксированному числу, например 24, вместо этого i * i, это будет постоянное число и не будет привязано к нему n, так было бы O(1). Если вы думаете о j < i * iпротив j <= i * i, это не будет иметь большого значения, так как будут nи n-1операции, но в нотации Биг-о, оба означаютO(n)
Сильвиу Бурча