рекуррентное отношение медленное Сортировка

Question

Итак, я участвую в классе анализа алгоритмов, и мы должны проанализировать отношение повторения медленной сортировки, которое, как мы обнаружили, T (N) = 2T (N/2) + T (N -1) +2. Я не понимаю, как это решить, поскольку у него есть несколько повторных вызовов, которые расширяются каждый раз, когда я пытаюсь найти шаблон. Какой был бы лучший способ решить проблему такого рода? Спасибо заранее.

Answer 1

Медленный алгоритм сортировки:

(1) найти максимум 2 номера и

(2) сортировка остальные.

(1,1) найти максимум из первых п 2 элементов /,

(1,2) найти максимум из оставшихся N 2 элементов /, и

(1,3) найти самый большой из этих двух максимумы.

T(0) = 0

T(1) = 0

T(2) = 2 // так как вы сравнить 2 элементы и поменять их местами, если один больше, чем другие.

Так дело в том, что если у вас есть для сортировки N элементов вы должны найти самый большой в первой половине, которая принимает T(N/2), а затем во второй половине, которая принимает другую T(N/2) (отсюда первый 2T(N/2)), то нужно сравнить их и поменять, если один больше другого, что принимает T(2) = 2 (следовательно, +2), после чего вы должны продолжить работу над остальными элементами N-1, потому что вы делаете только 1 из N, поэтому у вас осталось N-1, поэтому вам нужно сделать то же самое для остальных ваших элементов N-1, и в этом случае у вас есть + T(N-1).