Редактирование: Opij1SumTi

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 54: Строка 54:
  
 
=== Асимптотика ===
 
=== Асимптотика ===
Алгоритм может работать за <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>l_j</tex> такое, что на станке <tex>M_j</tex> все временные промежутки <tex>1 \ldots l_j</tex> заняты.
+
Алгоритм может работать за <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>l_j</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 = 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>
 
<center><tex>l_1 + 1 \ldots T_i</tex> на станке <tex> M_1 </tex>,<br>

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)