403
правки
Изменения
→Доказательство корректности
== Доказательство корректности ==
Покажем, что алгоритм строит корректное расписание. Если мы успеваем выполнить очередную работу, то, очевидно, от ее добавления, расписание не может стать некорректным. В противном случае мы пытаемся заменить одну работу из множества <tex> S </tex> на текущую. Но это так же не может сделать наше расписание некорректным. Это следует из того, что мы рассматриваем работы в порядке неуменьшениях их дедлайнов. Пусть мы заменяем работу <tex> k </tex> на работу <tex> i </tex>. Но <tex> d_{k} \leqslant d_{i} </tex>, и следовательно, если мы успевали выполнить работу <tex> k </tex>, то успеем выполнить и работу <tex> i </tex>.
== Время работы ==
Время работы алгоритма зависит от того, насколько быстро мы будем добавлять и удалять работы из множества <tex> S </tex>, а также как быстро мы будем искать работу с минимальным весом. Если в качестве множества <tex> S </tex> использовать структуру данных, умеющую выполнять данные операции за <tex> O(\log n) </tex>, то время работы всего алгоритма будет составлять <tex> O(n\log n) </tex>. Например, такими структурами данных являются [[Двоичная куча | двоичная куча]] и [[Красно-черное дерево | красно-черное дерево]].
