Максимальная и минимальная глубина сортировки

Question

Это была проблема CLR (Введение в алгоритмы) Вопрос идет следующим образом:

Предположим, что расщепляется на каждом уровне сортировки находятся в пропорции 1 - а к а, где 0 < α ≤ 1/2 является константой. Покажите, что минимальная глубина листа в дереве рекурсии приблизительно равна lg n/lg α, а максимальная глубина приблизительно -lg n/lg (1 - α). (Не беспокойтесь о целочисленном округлении.) http://integrator-crimea.com/ddu0043.html

Я не понимаю, как достичь этого решения. по ссылке они показывают, что при соотношении 1: 9 максимальная глубина равна log n/log (10/9) и минимальному log n/log (10). Тогда как доказать указанную выше формулу. Пожалуйста, помогите мне в том, где я буду ошибаться, поскольку я новичок в курсах Algorithms and Data Structures.

Answer 1

Во-первых, рассмотрим эту простую проблему. Предположим вам число n и долю (от 0 до 1) p. Сколько раз вам нужно умножить n на p так, чтобы итоговое число было меньше или равно 1?

n*p^k <= 1 
log(n)+k*log(p) <= 0 
log(n) <= -k*log(p) 
k => -log(n)/log(p) 

Теперь давайте рассмотрим вашу проблему. Предположим, вы отправляете более короткий из двух сегментов в левый ребенок и дольше до нужного ребенка. Для самой левой цепочки длина задается заменой \ alpha как p в приведенном выше уравнении. Для правой цепочки длина вычисляется путем подстановки 1- \ alpha как p. Вот почему у вас есть эти числа в качестве ответов.