Решите T (n) = T (nn / k) + n, используя суммирование

Question

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

k> = 0. T (n <= 2) = 1. </p>

Это рекуррентное соотношение было получено из алгоритма, который я написал, чтобы получить один отсортированный массив измассив, который отсортирован по k (это означает, что каждый k-й элемент находится в отсортированном порядке). Этот алгоритм работает не более k раз. Каждый раз, когда k уменьшается на один, каждый k-й элемент добавляется в другой массив. Наконец, каждый массив объединяется с использованием сортировки слиянием (n раз). Этот алгоритм вызывается рекурсивно до k = 0, что означает, что мы нашли каждый отсортированный подмассив.

У меня есть ощущение, что это O (k * n), но я не уверен.

Answer 1

Может быть полезно отметить, что

n - n / k = ((k - 1) / k) n,

, поэтому ваше рекуррентное отношение представляет nзатухание геометрически с коэффициентом (k-1) / k на каждом шаге. Чтобы увидеть, сколько работы сделано, пусть a = (k-1) / k. Тогда выполненная работа ограничивается сверху:

n + an + a ² n + a ³ n + ...

= n / (1 - a)

= n / (1 / k)

= nk.

Таким образом, ваша общая работа O (nk).

Как примечание, я не проверял, соответствует ли ваше рекуррентное отношение вашему коду - я просто показываю здесь математику. : -)