Таким образом, если в списке есть элементы N, выполнение дедупликации для элемента i потребует i сравнения (за ним стоит i значения). Таким образом, мы можем установить общее количество сравнений как sum[i = 0 to N] i. Это суммирование оценивается как N(N+1)/2, что строго меньше N^2 для N > 1.
Редактировать :
Чтобы решить суммирование, вы можете подойти к нему следующим образом.
1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n Отсюда вы можете сопоставлять числа с противоположных сторон. Это может стать
2 + 3 + ... + (n-1) + (n+1) путем сопоставления 1 в начале с n в конце. Сделайте то же самое с 2 и (n-1).
3 + ... + (n-1+2) + (n+1) упростить до
3 + ... + (n+1) + (n+1)
Вы можете повторить это n/2 раз, поскольку вы каждый раз сопоставляете два числа. Это оставит нас с n/2 вхождениями термина (n+1). Умножая их и упрощая, мы получаем (n+1)(n/2) или n(n+1)/2.
См. здесь для более подробного описания.
Кроме того, этот предполагает, что это суммирование все еще имеет бета-тета n^2.