Изменения

ИтакДля того, чтобы найти расписание, соответствующее списку всех операций <tex>L</tex>, выполним следующие шаги:*На на первом шаге каждую операцию кладём в соответствующий [[список]] <tex>L(k)</tex>, где <tex>k = l(O_{ij}) = d_i - n_i + j</tex> <tex>(-r + 1 \leqslant k \leqslant r - 1)</tex>. ; *На на втором шаге планируем операции соответственно возрастающему по номеру списка <tex>k</tex> порядку, где операции из одного списка могут выполнятся в произвольном порядке.

Суммарное количество операций равно <tex>r</tex>. Первый шаг алгоритма занимает <tex>O(r)</tex>, так как каждая операция добавляется либо в <tex>L</tex>, либо в <tex>Z</tex>. На втором шаге каждая операция назначается единожды, то есть на втором шаге также выполняется <tex>O(r)</tex> действий. И, наконец, суммарное время всех вызовов функции <tex>\mathrm{schedule}</tex> также равно <tex>O(r)</tex>, так как суммарное количество итераций циклов внутри этой функции не превышает <tex>O(r)</tex>. Итого, время работы алгоритма <tex>O(r)</tex>.