Поясните сложность данного алгоритма?

Question

[Антон Кривохижин]

Изучаю книгу "Алгоритмы. Теория и практическое применение" Рода Стивенса. Там приводится алгоритмы по нахождению дубликатов.

boolean containsDuplicate(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] == array[i]) {
                return true;
            }
        }
    }
    return false;
}

В книге указано, что сложность данного алгоритма O(n^2). Так как сложность внешнего цикла O(n). А если сложить все итерации внутреннего N + (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2 = (N^2 - N) / 2, что и означает, что сложность равна O(n^2).

Собственно прошу лишь объяснить вот это вот математическое преобразование внутреннего цикла. Так как совсем не понимаю почему так получается. N + (N - 1) + (N - 2) + ... + 1 = N * (N - 1) / 2 = (N^2 - N) / 2

Comments

[Денис Загаевский]

Школа, математика, 5-7 класс. Арифметическая прогрессия. А потом эти странные люди спрашивают, зачем математика....

[Антон Кривохижин]

Денис Загаевский: я не спрашивал, зачем нужна математика.

[Денис Загаевский]

Антон Кривохижин: а я и не говорил конкретно про тебя. Но тебе явно надо задаться этим вопросом.

Answer 1

[vvovas]

Как мне кажется, лишняя N в начале - внутренний цикл отработает (N-1)+(N-2)+...+1 раз. А по сути, вы сравниваете 2 числа и если обратиться к комбинаторике, то первое можно взять N вариантов, а второе (N-1). Так как нам не важен порядок, то делим пополам - вот и получается N*(N-1)/2

Answer 2

[Stalker_RED]

Если у вас на входе массив {a, b, c} то при проверке мы переберем сочетания ab ac bc.
Проверим, сходится ли с формулой:
(3^2 - 3) / 2 = 3

Если на входе {a, b, c, d} то переберем сочетания ab ac ad bc bd cd
Проверим, сходится ли с формулой:
(4^2 - 4) / 2 = 6

Можно продолжить и дальше, и тоже сойдется. Вообще сочетания считаются так:

(в нашем случае k = 2).

Внимательный читатель мог бы заметить, что 3^2 = 9 и при этом 9 ! = 4 но при оценке сложности постоянные множители зачастую опускают, и вместо O(2N^2) или вместо O(N^2 / 2) пишут O(N^2), так как отличия в сложности в несколько раз не так важны, как отличия на порядок, типа O(N^2) и O(N^3) или O(N!).

Или ваш вопрос про раскрытие скобок?

Comments

[Антон Кривохижин]

Спасибо за Ваш очень развернутый ответ. Вы ответили на то, что нужно

Answer 3

[Dimonchik]

для детей:
это известная байка про Гаусса, она хреново описана тут и тут и хорошо описана в хз каком учебнике: Гаусс заметил, что в ряду N чисел сумма первого и последнего равна сумме второго и предпоследнего, равна сумме N[3] и N[n-2] и т.д.
т.е. N[1]+N[n] = N[2]+N[n-1] = N[3]+N[n-2] и т.п., всего таких "пар" - N/2 , значит сумма всех равна (N[1]+N[n]) * N/2 что эквивалентно (N+1)*N/2
единицей пренебрегаем, получаем квадратичную сложность

ну а для взрослых: это типичная запись ряда, для наметанного глаза все очевидно