Изменения
→Асимптотика
<tex>h(t_j) = h(t_j) + 1</tex>
=== Асимптотика ===
Алгоритм может работать за <tex>O(nm)</tex>. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага i, сохранялся инвариант: <tex>l_1 \geqslant l_2 \geqslant \ldots \geqslant l_m </tex> при <tex>l_1 \geqslant T_i</tex>, что на станке <tex>M_j</tex> все промежутки <tex>1 \ldots l_j</tex> заняты.
На первом шаге алгоритма <tex> l_1 = l_2 = \ldots = l_m = 0 </tex>. Предположим, что инвариант сохранился после шага <tex> i - 1 </tex>. Тогда <tex> T_{i-1} \leqslant T_i </tex> и, для сохранения инварианта, распределим работу в следующем порядке:<br>
<tex>l_1 + 1 \ldots T_i</tex> на станке <tex> M_1 </tex>,<br>
<tex>l_2 + 1 \ldots l_1</tex> на станке <tex> M_2 </tex>,<br>
<tex> \vdots </tex><br>
<tex>l_m + 1 \ldots l_{m-1}</tex> на станке <tex> M_1 </tex>.
== Доказательство корректности ==
