Случай q > 2 подзадач

Начнем с раскрутки (5.3) для случая q > 2 по схеме, использованной ранее для (5.1).

Как вы увидите, результат сильно отличается.


♦ Анализ нескольких начальных уровней: пример приведен для случая 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.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Случай q > 2 подзадач:

  1. СЛУЧАЙ
  2. Несчастные случаи
  3. Случай 1
  4. Случай 2
  5. ПОХОЖИЙ СЛУЧАЙ
  6. НЕСЧАСТНЫЙ СЛУЧАЙ
  7. 4.11. СЛУЧАЙ С ГРУЗОВИКОМ
  8. СЛУЧАИ ИЗ ПРАКТИКИ
  9. 7.1.1. Случай с бабочками
  10. КРАЙHИЕ СЛУЧАИ
  11. Несчастный случай
  12. 3.2.1. Случай первый
  13. 3.2.2. Случай второй
  14. СЛУЧАЙ С ЖЕНЬКОЙ
  15. Случай с Ириной
  16. § 1. Случаи прекращения обязательств
  17. 1. Непреодолимая сила и случай