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

Сначала мы докажем, что алгоритм выдает правильный ответ, используя факты, установленные в ходе его разработки.

(5.11) Алгоритм правильно находит ближайшую пару точек в P. Доказательство. Как упоминалось ранее, все компоненты доказательства уже

были представлены ранее, так что осталось лишь собрать их все воедино.

Для доказательства правильности будет использована индукция по размеру P; случай |P| < 3 очевиден. Для заданного P ближайшая пара рекурсивных вызовов правильно вычисляется индукцией. Из (5.10) и (5.9) оставшаяся часть алгоритма правильно определяет, находится ли любая пара точек S на расстоянии менее δ, и если находится — возвращает такую пару с минимальным расстоянием. Теперь у ближайшей пары P либо обе точки принадлежат одному из множеств Q или R, либо они принадлежат разным множествам. В первом случае ближайшая пара на- ходится рекурсивным вызовом; во втором она находится на расстоянии менее δ и ищется оставшейся частью алгоритма. ■

Также определим границу времени выполнения, используя (5.2).

(5.12) Время выполнения алгоритма равно O(n log n).

Доказательство. Исходная сортировка P по x и у выполняется за время O(n log n). Время выполнения оставшейся части алгоритма удовлетворяет ре- куррентному отношению (5.1), а следовательно, равно O(n log n) согласно (5.2). ■

5.5.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. АНАЛИЗ
  14. АНАЛИЗ КОРОТКИЙ
  15. КОНТЕНТ - АНАЛИЗ
  16. Анализ документов