Правила анализа алгоритма
Рассмотрим следующее утверждение:
При использовании описанного выше жадного алгоритма каждому интервалу будет назначена метка, и никаким двум перекрывающимся интервалам не будет присвоена одна и та же метка.
Доказательство. Начнем с доказательства того, что ни один интервал не останется не помеченным. Рассмотрим один из интервалов Ij и предположим, что в порядке сортировки существует t интервалов, которые начинаются ранее и перекрывают его.
Далее утверждается, что никаким двум перекрывающимся интервалам не будут назначены одинаковые метки. В самом деле, возьмем два перекрывающихся интервала I и I’ и предположим, что I предшествует I’ в порядке сортировки.
Затем, при рассмотрении алгоритмом I’, интервал I принадлежит множеству интервалов, метки которых исключаются из рассмотрения; соответственно, алгоритм не назначит I’ метку, которая использовалась для I.
Алгоритм и его анализ очень просты. По сути, в вашем распоряжении имеется d меток, затем при переборе интервалов слева направо с назначением доступной метки каждому обнаруженному интервалу никогда не возникнет ситуация, в которой все метки уже задействованы.
Так как наш алгоритм использует d меток, из (4.4) можно сделать вывод, что он использует минимально возможное количество меток. Данный результат обобщается следующим образом.
Описанный выше жадный алгоритм связывает каждый интервал с ресурсом, используя количество ресурсов, равное глубине множества интервалов. Это количество ресурсов является минимально необходимым, то есть оптимальным.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу