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

Рассмотрим следующее утверждение:

(4.5) При использовании описанного выше жадного алгоритма каждому ин- тервалу будет назначена метка, и никаким двум перекрывающимся интервалам не будет присвоена одна и та же метка.

Доказательство. Начнем с доказательства того, что ни один интервал не оста- нется не помеченным. Рассмотрим один из интервалов I и предположим, что в порядке сортировки существует t интервалов, которые начинаются ранее и пере- крывают его. Эти t интервалов в сочетании с I. образуют множество из i интервалов, которые все проходят через общую точку временной шкалы (а именно начальное время I), поэтому t + 1 < d. Следовательно, t < d - 1. Из этого следует, что по край- ней мере одна из меток d не будет исключена из этого множества интервалов t, поэтому существует метка, которая может быть назначена I..

Далее утверждается, что никаким двум перекрывающимся интервалам не бу- дут назначены одинаковые метки. В самом деле, возьмем два перекрывающихся интервала I и I' и предположим, что I предшествует I' в порядке сортировки. Затем, при рассмотрении алгоритмом I', интервал I принадлежит множеству интервалов, метки которых исключаются из рассмотрения; соответственно, алгоритм не на- значит I' метку, которая использовалась для I. ■

Алгоритм и его анализ очень просты. По сути, в вашем распоряжении имеется d меток, затем при переборе интервалов слева направо с назначением доступной метки каждому обнаруженному интервалу никогда не возникнет ситуация, в ко- торой все метки уже задействованы.

Так как наш алгоритм использует d меток, из (4.4) можно сделать вывод, что он использует минимально возможное количество меток. Данный результат обобща- ется следующим образом.

(4.6) Описанный выше жадный алгоритм связывает каждый интервал с ре- сурсом, используя количество ресурсов, равное глубине множества интервалов. Это количество ресурсов является минимально необходимым, то есть оптималь- ным.

4.2.

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