Сложность неэффективного разделяй и властвуй алгоритм

Question

Экземпляр размера n делится на p≥2 экземпляров каждого размера n-a, где a является небольшой integer и p является constant. Расчетная стоимость этой операции (т. Е. Деление на экземпляры) представляет собой единицу, с C(0)=1.

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

C(n) = (n-a)*C(n/p) + 1 

это правильно?

Answer 1

Я думаю, что это будет что-то вроде этого:

C(n) = (p)*C(n-a) + 1 

Мое объяснение в том, что вы сказали «p≥2 экземпляры каждого размера п-а» в вашем вопросе. Таким образом, размер уменьшается до C(n-a) и есть p подзадач. Поэтому я думаю, что это будет что-то вроде p*C(n-a). У вас есть другой термин. Стоимость деления на каждом шаге составляет C(0) = 1, как вы сказали.

Answer 2

Ну, так как это выглядит как школьное задание, особенно из-за формулировки «неэффективный алгоритм разделения и покорения», я не буду отвечать на него напрямую.

В качестве примера я бы посоветовал использовать a=1 и p=2. В этом случае вам нужно решить две подзадачи размером n-1, а затем потратьте 1 единицу времени на объединение решений. Если это займет у вас 1 единицу времени, чтобы решить для n=1, т.е. C(1)=1, то вы получите

C(1)=1 
C(2) = 2*C(1) + 1 = 3 
C(3) = 2*C(2) + 1 = 7 
C(4) = 2*C(3) + 1 = 15 

и т.д. Таким образом, вы получите C(n) =2^n - 1. Если a не 1, это в основном то же самое: вы просто поднимете до уровня n/a вместо n.

Кстати, не странно ли вы называть a «маленьким целым», тогда как p является «константой»? Конечно, оба выражения означают одно и то же. Все константы «малы», что касается асимптотического поведения.

Answer 3

Как писал Шашанк, C (n) = p⋅C (n-a) + 1 является правильным.

Я просто хочу сказать, что это приводит к

С (п) = S _{я = 0, ..., п/а}^{р я} = р ^{п/а + 1} - 1

Так с (п) в O (р ^н/), который является экспоненциальной в п.