Изменения

Перейти к: навигация, поиск

Opij1SumTi

1 байт убрано, 00:20, 8 июня 2016
Асимптотика
=== Асимптотика ===
Алгоритм может работать за <tex>O(nm)</tex>. Чтобы получить алгоритм с такой сложностью, мы распределяем работы так, чтобы после каждого шага <tex>i</tex>, сохранялся инвариант: <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>
<center><tex>l_1 + 1 \ldots T_i</tex> на станке <tex> M_1 </tex>,<br>
<tex>l_m + 1 \ldots l_{m-1}</tex> на станке <tex> M_1 </tex>.
</center>
Таким образом, мы получаем распределение одной работы по <tex>Mm</tex> станкам для <tex>Nn</tex> работ. Итоговая асимптотика <tex>O(nm)</tex>.
== Доказательство корректности ==
Анонимный участник

Навигация