Понимание повторяемости для времени выполнения

Я выполняю упражнения по введению в алгоритм с помощью CLR. Это не оценочное домашнее задание или что-то еще, я просто пытаюсь понять проблему.

Задача состоит в следующем:

Мы можем выразить сортировку вставки как рекурсивную процедуру следующим образом. В порядок сортировки A[1..n], рекурсивно сортируем A[1..n-1] и затем вставьте A[n] в отсортированный массив A[1..Н-1]. Написать повторение для времени выполнения этой рекурсивной версии вставки сортировать.

Решение задачи:

Так как в худшем случае требуется O(n) времени, чтобы вставить A[n] в сортированный массив A[1. .n -1], получаем рекуррентность T (n) = O (1), Если n = 1 , T(n-1)+ O (n), если n > 1 . Решение этой рекурренции - T(n) = O (n^2).

Таким образом, я получаю, что если n=1, то он уже отсортирован, поэтому он занимает O(1) времени. Но я не понимаю второй части рецидива: Часть O (n) - это шаг, на котором мы вставляем элемент сортируется в массив, который занимает в худшем случае O (n) времени - случай, когда мы должны пройти через весь массив и вставить в конце его.

Мне трудно понять рекурсивную часть этого (T(n-1)). Означает ли T(n-1), что при каждом рекурсивном вызове мы сортируем на один элемент массива меньше? Это кажется неправильным.

2 8
sorting algorithm recursion recurrence

2 ответа:

Да, это следует из:

Для сортировки a[1..n], рекурсивно сортируем A[1..n-1] и затем вставьте A[n] в отсортированный массив A[1..n-1]

" рекурсивная сортировка A[1..N-1]" часть занимает T (n-1) времени(это легко: мы определяем T(n), чтобы означать "время, необходимое для сортировки n элементов", поэтому время, необходимое для сортировки N-1 элементов, тривиально T (n-1)), в то время как "вставить A[n] в сортируемый массив A[1..N-1]" часть занимает (в худшем случае) O (n) времени. Сложить их вместе, чтобы получить

T (n) = T(n-1) + O (n)

9

Я объясню, что я понимаю с помощью кода python для сортировки вставки с помощью рекурсии следующим образом:

Def insert_sort_r (A,n) 

if n==1:

    pass

else:------------------------------------ c1
    insert_sort_r(A,n-1) ---------------- T(n-1)

    key = A[n-1]------------------------- c2
    i = n-2 ------------------------------c3

    while i>-1 and A[i] > key:------------c4*(n)
        A[i+1] = A[i]---------------------c5*(n-1)
        i = i-1---------------------------c6*(n-1)
    A[i+1] = key--------------------------c7

Время, затраченное на каждый шаг, представлено значениями" c " while, а также показано количество выполненных шагов. Мы представляем время, затраченное на сортировку (n-1) элементов на шаге " insert_sort_r(A,n-1)" как T (n-1), потому что мы не знаем точно, каким будет это значение в терминах n. это идея рекурсии. Чтобы представлять уравнение для случая, когда значение равно n, и для случая, когда значение равно (n-1).

0