1632
правки
Изменения
м
Количество шагов Суммарное количество операций равно <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>.
rollbackEdits.php mass rollback
<tex>-r + 1 \leqslant l(O_{ij}) = d_i - n_i + j \leqslant r - 1</tex>
Для того, чтобы найти расписание, соответствующее списку всех операций <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> порядку, где операции из одного списка могут выполнятся в произвольном порядке.
==Алгоритм==
'''function''' solve():
<font color=darkgreen>// Шаг 1</font>
<font color=darkgreen>// Инициализируем L и Z</font>
'''for''' k = -r + 1 '''to''' r - 1
T1 = 0
T2 = 0
<font color=darkgreen>// Шаг 2</font>
<font color=darkgreen>// Планируем операции соответственно возрастающему по номеру списка порядку</font>
'''for''' k = -r + 1 '''to''' r - 1
==Асимптотика==
==Доказательство==
