Изменения
Нет описания правки
В силу того, что для любого сдвига будет построено оптимальное расписание, алгоритм находит оптимальное расписание.
}}
==Сложность алгоритма==
В алгоритме требуется знать для двух произвольных работ, зависит ли, возможно, не непосредственно, одна от другой. Для этого нужно транзитивно замкнуть граф по отношению зависимости. Это можно сделать несколькими способами. Первый и самый простой {{---}} за <tex>O(n^3)</tex> алгоритмом Флойда-Уоршалла. Второй {{---}} при помощи метода четырех русских за <tex>O(\frac{n^3}{\log n})</tex>. Третий {{---}} применить алгоритм Фишера-Мейера для построения замыкания графа за <tex>O(n^{\log_2 7})</tex>.
При подсчете вынужденных дедлайнов, за <tex>O(n)</tex> считается вынужденный дедлайн одной работы. Так как всего работ <tex>n</tex>, суммарное время подсчета вынужденных дедлайнов {{---}} <tex>O(n^2)</tex>.
При, непосредственно, составлении расписания, на каждом шаге за <tex>O(n)</tex> обрабатываются одна или две работы. Значит, все работы будут обработаны также за <tex>O(n^2)</tex>.
Итоговая сложность {{---}} <tex>O(TrCl + n^2)</tex>.
==Ссылки==
[http://rjlipton.files.wordpress.com/2009/10/matrix1971.pdf| Алгоритм Фишера-Мейера]
