Запущенная сложность вставки сортировки - PullRequest
Новая
       47

Запущенная сложность вставки сортировки

0 голосов
/ 20 октября 2018

В книге о структуре данных и алгоритмах есть следующая реализация сортировки вставки: 

int insertionSort(void *data, int size, int esize, int(*compare)(const void *key1, const void *key2)){

    int i,j; 
    void *key,

    char *a = data;

    key = (char *) malloc(esize);

    if(key == NULL){
        return -1;
    }


    for(j=1; j<size; j++){
        memcpy(key, &a[j*esize], esize);
        i = j-1;

        while(i>=0 && compare(&a[i*esize], key)>0){
            memcpy(&a[(i+1)*esize],&a[i*esize], esize);
            i--;
        }

        memcpy(&a[(i+1)*esize], key, esize);


    }
}

Итак, в разделе о сложности говорится следующее:

Сложность вставки сортировки во время выполнения фокусируется на ее вложенных циклах.Имея это в виду, внешний цикл имеет время работы T (n) = n - 1, умноженное на некоторое постоянное количество времени, где n - количество отсортированных элементов.Исследуя внутренний цикл в худшем случае, мы предполагаем, что нам придется пройти весь путь до левого конца массива, прежде чем вставлять каждый элемент в отсортированный набор.Следовательно, внутренний цикл может повторяться один раз для первого элемента, два раза для второго и т. Д., Пока не завершится внешний цикл.Время выполнения вложенного цикла представляется в виде суммирования от 1 до n - 1, что приводит к времени выполнения T (n) = (n (n + 1) / 2) - n, умноженному на некоторую постоянную величинувремени.(Это из известной формулы для суммирования ряда от 1 до n.) Используя правила O-обозначения, это упрощается до O (n ^ 2)

Итак, я погуглилформулу суммирования и понять, почему это (n (n + 1) / 2).Есть также множество видео на YouTube об этой формуле, которые я также смотрел.Но я не мог понять последнюю часть T (n) в книге, которая является частью "-n". Почему минус n в конце ?

...