Выбор Сортировка Рецидивирование Отношения

Question

перед этим это вопрос домашней работы, но у меня возникли трудности с пониманием рекуррентных отношений. Я пробовал интернет для примеров, и они очень расплывчаты для меня. Я понимаю, что рекуррентные отношения для рекурсивных алгоритмов не имеют заданного способа обработки каждого из них, но я теряюсь в том, как их понимать. Вот алгоритм, я должен работать с:

void selectionSort(int array[]) { 
    sort(array, 0); 
} 

void sort(int[] array, int i) { 
    if (i < array.length - 1) 
    { 
     int j = smallest(array, i); T(n) 
     int temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     sort(array, i + 1); T(n) 
    } 
} 

int smallest(int[] array, int j)  T(n - k) 
{ 
    if (j == array.length - 1) 
     return array.length - 1; 
    int k = smallest(array, j + 1); 
    return array[j] < array[k] ? j : k; 
} 

Итак, насколько я понимаю, это то, что я иду с: Т (п) = Т (п - 1) + сп + с Т (n-1) представляет собой рекурсивную функцию сортировки, а добавленная cn представляет собой рекурсивную функцию наименьшей, которая должна уменьшаться по мере уменьшения n, поскольку она вызывается только количество раз, которое остается в массиве каждый раз. Константа, умноженная на n, представляет собой количество времени для запуска дополнительного кода в наименьшем количестве, а дополнительная константа - это количество времени для запуска дополнительного кода в сортировке. Это правильно? Я совсем ушел? Я не объясняю это правильно? Следующий шаг - создать дерево рекурсии из этого, но я не вижу это уравнение как форму T (n) = aT (n/b) + c, которая является формой, необходимой для дерева, если я понимаю это право , Также я не вижу, как мое отношение повторения будет доходить до n^2, если оно будет правильным. Это тоже мой первый пост, поэтому я приношу свои извинения, если я сделал что-то неправильное здесь. Спасибо за помощь!

Answer 1

Самый простой способ вычислить временную сложность состоит в том, чтобы моделировать временную сложность каждой функции с отдельным отношением рекуррентности.

Мы можем моделировать временную сложность функции smallest с отношением рекуррентности S(n) = S(n-1)+O(1), S(1)=O(1). Это, очевидно, решает до S(n)=O(n).

Мы можем моделировать временную сложность функции sort с помощью T(n) = T(n-1) + S(n) + O(1), T(1)=O(1). Термин S(n) приходит, потому что мы вызываем smallest в функции sort. Поскольку мы знаем, что S(n)=O(n) мы можем написать T(n) = T(n-1) + O(n), и выписывая повторение, получаем T(n)=O(n)+O(n-1)+...+O(1)=O(n^2).

Таким образом, общее время работы: O(n^2), как ожидалось.