Реализация алгоритма устойчивых паросочетаний со списками и массивами
Мы рассмотрели общий подход к выражению границ времени выполнения алго- ритмов. Чтобы проанализировать асимптотическое время выполнения алгоритмов, выраженных на высоком уровне (например, алгоритма поиска устойчивых паросочетаний Гейла–Шепли в главе 1), следует не писать код, компилировать и выполнять его, а думать над представлением и способом обработки данных в алгоритме, чтобы получить оценку количества выполняемых вычислительных действий.
Для начала мы рассмотрим реализацию алгоритма устойчивых паросочетаний Гейла–Шепли; ранее было показано, что алгоритм завершается максимум за n2 итераций, а наша реализация обеспечивает соответствующее худшее время выполнения O(n2) с подсчетом фактических вычислительных шагов вместо простого количества итераций.
Чтобы получить такую границу для алгоритма устойчивых паросочетаний, достаточно использовать две простейшие структуры данных: списки и массивы. Таким образом, наша реализация также предоставит хорошую возможность познакомиться с использованием этих базовых структур данных.
В задаче устойчивых паросочетаний у каждого мужчины и каждой женщины должны существовать оценки всех членов противоположного пола. Самый первый вопрос, который необходимо обсудить, — как будут представляться эти оценки? Кроме того, алгоритм ведет учет паросочетаний, поэтому на каждом шаге он дол- жен знать, какие мужчины и женщины свободны и кто с кем находится в паре.
Для реализации алгоритма необходимо решить, какие структуры данных будут использоваться для всех этих задач.
Следует учесть, что структура данных выбирается проектировщиком алго- ритма; для каждого алгоритма мы будем выбирать структуры данных, обеспечивающие эффективную и простую реализацию. В некоторых случаях это может потребовать предварительной обработки входных данных и их преобразования из заданного входного представления в структуру, лучше подходящую для решаемой задачи.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу