Анализ алгоритма

Приведенные выше рассуждения уже доказывают, что алгоритм возвращает пра- вильный ответ и использует память O(m + n). Остается проверить только следу- ющий факт.

Рис.

6.19. Первый уровень рекуррентности для процедуры Divide-and-Conquer-Alignment, эффективной по затратам памяти. Две области, выделенные рамкой, обозначают входные данные для двух рекурсивных вызовов

(6.21) Время выполнения для процедуры Divide-and-Conquer-Alignment для строк длины m и n равно O(mn).

Доказательство. Обозначим T(m, n) максимальное время выполнения алгорит- ма для строк m и n. Алгоритм выполняет работу O(mn) для построения массивов B и B'; затем он рекурсивно выполняется для строк c размерами q и n/2 и строк с размерами m - q и n/2. Следовательно, для некоторой константы c и некоторого выбора индекса q:

Эта рекуррентность сложнее тех, которые встречались нам ранее в примерах «разделяй и властвуй» из главы 5. Прежде всего, время выполнения является функцией двух переменных (m и n), а не одной; кроме того, разбиение на подзада- чи не обязательно является «равным», а зависит от значения q, найденного в ходе предшествующей работы, выполненной алгоритмом.

Как же подойти к разрешению этой рекуррентности? Можно попытаться угадать форму решения, рассмотрев частный случай рекуррентности, и затем воспользоваться частичной подстановкой для заполнения параметров. А имен- но предположим, что m = n, а точка разбиения q находится точно в середине.

В этом (надо признаться, весьма ограниченном) частном случае мы можем за- писать функцию T() для одной переменной n, присвоить q = n/2 (предполагается идеальное деление пополам) и прийти к условию

T(n) < 2T(n/2) + cn2.

Это выражение полезно, потому что оно уже было разрешено при обсужде- нии рекуррентности в начале главы 5, а именно: из этой рекуррентности следует T(n) = O(n2).

Итак, при m = n и равном разбиении время выполнения возрастает в квадра- тичной зависимости от n. Вооружившись этой информацией, мы возвращаемся к общему рекуррентному отношению текущей задачи и предполагаем, что T(m, n) растет со скоростью произведения m и n. А именно предположим, что T(m, n) < kmn для некоторой константы k, и посмотрим, удастся ли доказать это утверждение по индукции. Начиная с базовых случаев m < 2 и n < 2, мы видим, что они выполняют- ся при k> c/2. Теперь предполагая, что T(m', n') < km'n' выполняется для пар (m', n') с меньшим произведением, имеем

Следовательно, шаг индукции выполняется, если выбрать k = 2c, а доказатель- ство на этом завершается. ■

6.8.

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

Еще по теме Анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Принципы анализа происшествия.
  13. АНАЛИЗ