Повторение для наихудшего времени работы Quicksort

Question

Предположим, что мы построили quicksort, а значение поворота принимает линейное время. Найдите повторение для наихудшего времени работы.

Мой ответ: Т (п) = Т (п-1) + T (1) + тета- (п)

В худшем случае происходит, когда подмассивы полностью несбалансированным. В другом подмассиве есть один элемент в одном подмассиве и (n-1) элементы. theta (n), так как для определения точки поворота требуется время n.

Я делаю это правильно?

Answer 1

Ваше повторение в основном верное, но на самом деле у вас нет двух рекурсивных вызовов. В худшем случае для быстрой сортировки стержень будет самым большим или наименьшим элементом в массиве, поэтому вы будете возвращаться к одному гигантскому массиву размером n - 1. Другой подмассив имеет длину 0, поэтому никаких рекурсивных вызовов не производится. В довершение всего, общая работа равна Θ (п) на уровне, так что рекуррентное соотношение было бы более целесообразно

Т (п) = Т (п - 1) + Θ (п)

Это, в свою очередь, затем решается до Θ (n).

Надеюсь, это поможет!

Answer 2

вы не можете наблюдать, потому что, согласно моим исследованиям T (N) = T (NK) + T (K-1) + п мы не можем наблюдать точное значение, пока мы не значение к,