Я создал идеальный алгоритм сортировки расческой?

Question

Код:

public static void raschestkaSort(int[] a){
    for(int d = a.length - 2; d >= 0; d--){
        for(int i = 0; i <= (a.length - 2) - d; i++){
            if(a[i] > a[i + d + 1]){
                swap(a, i, i + d + 1);
            }
        }
    }
}
private static void swap(int[] a, int from, int to) {
    int temp = a[from];
    a[from] = a[to];
    a[to] = temp;
}

В наихудшем случае сложность алгоритма должна быть равна O(1 + 2 + 3 + ... + (n - 1)). В вики же - O(n^2). Может, я неправильно считаю сложность?

P.S.: И действительно, если запустить сортировку с таким кодом:

public static void raschestkaSort(int[] a){
    int countOfComparing = 0;
    for(int d = a.length - 2; d >= 0; d--){
        for(int i = 0; i <= (a.length - 2) - d; i++){
            countOfComparing++;
            if(a[i] > a[i + d + 1]){
                swap(a, i, i + d + 1);
            }
        }
    }
    System.out.println(countOfComparing);
}

То для 14 элементов сравнений будет 91. А это близко не O(n^2)

Answer 1

Во-первых,

Т.е. чистое O(n^2)

Далее, O(n^2) не означает, что надо возвести n в квадрат, и это и будет число сравнений. Попробуйте несколько раз увеличить n раз в 5 и посмотрите на результаты...

Почитайте, что означает запись O(f(n)).

И 1000000000n^2+100n, и n^2/100000000+100n - это все O(n^2).

P.S. И вообще, давно и строго доказано, что алгоритм сортировки, основанный на сравнениях, не может быть лучше O(N * log N)...

Answer 2

В асимптотической сложности константы нужно отбрасывать. Асимптотическая сложность - это относительная величина. Она определяет кол-во единиц времени. которое понадобится для выполнения алгоритма.
Думаю, это нужно проиллюстрировать - например, у нас есть ф-ция f(n), принимающая количество раз, которое нужно вывести строку "Hello world". Кол-во единиц времени, которое займет выполнение зависит только от числа n. И зависит напрямую - значит сложность будет напрямую зависеть от числа n, и, соответственно, будет равна O(n).
Зависит же кол-во единиц времени в случае с сортировкой массива алгоритмом raschestkaSort(a) ТОЛЬКО от размерности a. Возьмем размерность за число n. Кол-во единиц времени, которое займет выполнение зависит только от числа n. И зависит оно в следующем отношении - (1 + (n - 1)) * n/2 = n * n / 2 - это и есть O. То есть O(n * n / 2). Вспомним, в асимптотической сложности константы нужно отбрасывать. Тогда O(n * n). То есть та же сложность. что и в вики.