Случай q > 2 подзадач
Как вы увидите, результат сильно отличается.
♦ Анализ нескольких начальных уровней: пример приведен для случая q = 3 на рис.
5.2. На первом уровне рекурсии имеется одна задача с размером n, кото- рая выполняется за время cn плюс время, потраченное на все последующие рекурсивные вызовы. На следующем уровне имеются q задач с размером n/2. Каждая задача выполняется за время максимум cn/2, что дает в сумме (q/2) cn плюс время последующих рекурсивных вызовов. На следующем уровне ис- пользуются q2 задач с размером n/4 с общим временем (q2/4)cn. Мы видим, что при q > 2 общий объем работы на уровень возрастает с увеличением уровня.♦ Выявление закономерности: на произвольном уровне j рекурсии задействованы q разных экземпляров, каждый из которых имеет размер n/2j.
Следовательно, общий объем работы, выполняемой на уровне j, составляет q j(cn/2 j) = (q/2) jcn.♦ Суммирование по всем уровням рекурсии: как и в предыдущем случае, существуют log2 n уровней рекурсии, а общий объем выполняемой работы определяется следующей суммой:
Это геометрическая сумма, состоящая из степеней r = q/2. Воспользовавшись формулой геометрической суммы при r > 1, получаем
Так как нас интересует асимптотическая верхняя граница, будет полезно выде- лить то, что является константой: последнее выражение может быть записано в виде
Наконец, нужно разобраться в том, что же собой представляет .
Восполь- зуемся очень удобной формулой: для всех a > 1 и b > 1 справедливо alog b = blog a. Следовательно,
В итоге получаем
Результат можно обобщить в следующей форме:
(5.4) Любая функция 7`(·), удовлетворяющая условию (5.3) сq>2, имеет гра- ницу О( ).
Получается, что время выполнения больше линейного, так как log2 q > 1, но все равно полиномиальное по п. При подстановке конкретных значений q время выпол- нения составит О( м⅛ s) = О(;?1·59) для q= 3; а для q = 4 оно равно О( J) = О(п2). Увеличение времени выполнения с ростом q выглядит логично, поскольку рекур- сивные вызовы порождают больший объем работы с увеличением q.
Еще по теме Случай q > 2 подзадач:
- СЛУЧАЙ
- Несчастные случаи
- Случай 1
- Случай 2
- ПОХОЖИЙ СЛУЧАЙ
- НЕСЧАСТНЫЙ СЛУЧАЙ
- 4.11. СЛУЧАЙ С ГРУЗОВИКОМ
- СЛУЧАИ ИЗ ПРАКТИКИ
- 7.1.1. Случай с бабочками
- КРАЙHИЕ СЛУЧАИ
- Несчастный случай
- 3.2.1. Случай первый
- 3.2.2. Случай второй
- СЛУЧАЙ С ЖЕНЬКОЙ
- Случай с Ириной
- § 1. Случаи прекращения обязательств
- 1. Непреодолимая сила и случай