Решение рекуррентных отношений с двумя рекурсивными вызовами

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

Чтобы сделать это, я задаю себе вопрос, каким будет время выполнения , если быстрая сортировка всегда происходила с разбиением на некоторую дробь такую ​​что элементы находятся в левой части, а - в правой части (оставляя 1 элемент, стержень, посередине).$T(n, p)$$0 < p \leq {1\over 2}$$\lfloor{p(n-1)}\rfloor$$\lceil(1 - p)(n - 1)\rceil$$1$

Нетрудно понять, что $T(n, p)$ дает верхнюю границу для наихудшего случая, когда $p$ - максимально несбалансированный раздел, поскольку любой раздел с дробью $> p$ будет более сбалансированным и будет иметь меньшее время выполнения, и любая дробь $<p$ не допускается.

Очевидно, что $T(n, {1 \over 2})$ - лучший случай, а $T(n, 0)$ - худший случай быстрой сортировки. Оба имеют легко повторяющиеся отношения, которые можно найти в любом образовательном ресурсе. Но я понятия не имею, как изучать $T(n, p)$ в целом. Очевидное отношение будет:

Здесь я застреваю. Я пытался искать, но вся литература, которую я мог понять об алгоритмах «разделяй и властвуй», воспринимала «разделить» буквально и «обманула» анализ, используя тот факт, что разделы всегда равны по размеру, объединяя термины в один раз. постоянная.

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

PS: меня не интересует асимптотика (которую легко показать $\Theta(n \log n)$ для любой константы $p$ ). Меня интересует, насколько медленной становится быстрая сортировка при уменьшении $p$ , например меня интересует соотношение $T(n, 0.25) \over T(n, 0.5)$ .

PPS: Будучи студентом бакалавриата, я прошу прощения, если я сделал очевидные вещи слишком длинными или недооцененными нетривиальности. И хотя я не знаю, смотрят ли они здесь так же, как другие сайты SE, отмечу, что это личный интерес, а не домашняя работа.

Как вы упоминаете, теорема Акра – Бацци показывает, что решением рекуррентности является для всех . Однако это не раскрывает характера зависимости от . Чтобы определить последнее, мы можем использовать подход дерева рекурсии.T ( n , p ) O ( n log n ) p ∈ ( 0 , 1 ) $T(n,p)$$O(n\log n)$$p \in (0,1)$$p$

В корне дерева рекурсии находится интервал . Его двое детей являются интервалы и , общая длина которых снова . У каждого из этих узлов есть два дочерних элемента (при условии, что достаточно велико) и т. Д. Для простоты мы игнорируем ошибки округления, то есть предполагаем, что является целым числом; это всего лишь техническая составляющая, и я бы об этом не беспокоился. Мы останавливаем процесс всякий раз, когда длина узла не превышает . Сложность алгоритма пропорциональна общей длине интервалов в дереве. Когда , листья{ 1 , ... п } { 1 , ... , р п } { р п + 1 , ... , п } п п р п 1 р ≠ 1 /$\{1,\ldots n\}$$\{1,\ldots,pn\}$$\{pn+1,\ldots,n\}$$n$$n$$pn$$1$$p \neq 1/2$ (узлы, на которых мы останавливаем процесс) имеют разную глубину, и это затрудняет определение общей сложности.

Мы можем получить простую верхнюю границу, отметив, что дерево имеет не более уровней: каждый узел по крайней мере в меньше своего родителя. Как и в анализе для , общая длина интервалов на любом уровне не превышает , и мы получаем верхнюю границу на Продолжительность. Так как и для малых , мы можем записать это как .войти 1 - р ( 1 / п ) 1 - р р = 1 / 2 п О ( п войти 1 - р ( 1 / п ) ) войти 1 - р ( 1 / п ) = войти п / журнал ( 1 - р ) - 1 журнал ( 1 - р ) - $\log_{1-p} (1/n)$$1-p$$p = 1/2$$n$$O(n\log_{1-p} (1/n))$$\log_{1-p} (1/n) = \log n/\log (1-p)^{-1}$$\log (1-p)^{-1} = -\log (1-p) = p \pm O(p^2)$$p$$O(n\log n/p)$

Вот более точный расчет. Рассмотрим уровень . Предположим, мы не останавливаем процесс при достижении небольшого интервала. Мы можем создать случайную вершину, сделав шагов, в каждом из которых мы идем налево (скажем) с вероятностью и направо (скажем) с вероятностью . Каждый раз, когда мы делаем левый шаг, лог длины интервала уменьшается на , а каждый раз, когда мы делаем правый шаг, уменьшается на . Вершина находится в самом дереве журнала длина снизилась не более чем на . Общий вес интервалов на уровне$t$$t$$p$$1-p$$-\log p$$-\log (1-p)$$\log n$$t$дерева как раз и есть вероятность того, что вершина, сгенерированная в соответствии с этим процессом, соответствует уменьшению не более . То есть, если является распределение , которое равно с вероятностью и с вероятностью и являются независимыми, то общий вес уровня равен . Для суперконстантного случайная величина примерно нормально распределена со средним и дисперсией, линейной поlog n D - log p p - log ( 1 - p ) 1 - p X 1 , … , X t ∼ D t Pr [ X 1 + ⋯ + X t ≤ log n ] t X 1 + ⋯ + X t [ - p log p - ( 1 - p ) $\log n$$D$$-\log p$$p$$-\log(1-p)$$1-p$$X_1,\ldots,X_t \sim D$$t$$\Pr[X_1+\cdots+X_t \leq \log n]$$t$$X_1+\cdots+X_t$$[-p\log p-(1-p)\log(1-p)]t$$t$, поэтому для удовлетворяющего , скажем, вероятность будет очень близка к , тогда как для удовлетворяя , скажем, оно будет очень близко к нулю. Определив (известный как двоичная энтропийная функция), мы заключаем, что время выполнения равно (равномерный по , так как ). В качестве мы имеем , поэтому наша более ранняя оценка не была точной.$t$$[-p\log p-(1-p)\log(1-p)]t \leq (\log n)/2$$1$$t$$[-p\log p-(1-p)\log(1-p)]t \geq 2\log n$$h(p) = -p\log p-(1-p)\log(1-p)$$\Theta(n\log n/h(p))$$p$$n\to\infty$$p\to 0$$h(p) \approx -p\log p$

Другой способ взглянуть на тот же анализ состоит в том, чтобы иметь бесконечную последовательность независимых случайных величин как и раньше, и определить время остановки как первый момент времени такой что . Время работы пропорционально . Элементарная теорема об обновлении тогда утверждает, что , подразумевая, что общий размер интервалов равен . Точнее, для каждой константы общий размер интервалов равен , где$X_1,X_2,\ldots$$T$$t$$X_1 + \cdots + X_t \geq \log n$$n\mathbb{E}[T]$$\lim_{n\to\infty} \mathbb{E}[T]/\log n = 1/\mathbb{E}[D] = 1/h(p)$$(1+o(1))n\log n/h(p)$$p$$(1+\alpha_p(n))n\log n/h(p)$$\alpha_p(n) = o(n)$ . Сходимость в элементарной теореме восстановления является экспоненциальной по параметру времени - в нашем случае - поэтому она должна быть полиномиальной от , то есть . Сходимость также, вероятно, равномерна для для любого .$\log n$$n$$\alpha_p(n) = O(n^{-C_p})$$p \in (\delta,1-\delta)$$\delta > 0$

Подводя итог, общая длина интервалов в дереве рекурсии, которая пропорциональна времени выполнения, имеет следующую форму для каждого : где и берутся в одну базу, а является функцией, зависящей от и стремящейся к с помощью .$p$

Более того, вероятно, верно, что для любого и любого верно, что общая длина интервалов имеет вид где и скрытая большая константа O зависят только от . В частности, должно быть так, что для всех констант , и сходимость полиномиально быстра.$\delta > 0$$p \in (\delta,1-\delta)$