Пример для алгоритма с разделением больше чем n

Question

Я делал вывод для теоремы мастеров, используя метод дерева, и я кое-что заметил.

Итак, мы имеем:

$ T (n) = a * T (n / b) + n ^ c $

Отсюда: мы замечаем, что последний уровень дерева будет иметь $a^(log_b_n)$ split, что равно $n^(log_b_a)$

Теперь, если $a=b$, я получаю n разбиений на последнем уровне, который, как я видел, используется в быстрой сортировке и сортировке слиянием, и если

Есть ли практический пример для разделений больше чем n? Где мы на самом деле повторяем операции для элементов?

* Кроме того, математическое форматирование с переполнением не работает. Был бы признателен, если кто-нибудь поможет.

Answer 1

Классическим матричным умножением на разделяй и властвуй был бы такой пример. Отношение рекуррентности: T(n)=8T(n/2)+ Theta(n^2). Другим был бы алгоритм Штрауссена.

Математическая запись (к сожалению) ограничена только несколькими сайтами обмена стека.