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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 22: Строка 22:
 
Так как [[Сортировка|сортировка]] весов занимает <tex>O(n \log n)</tex> время, то асимптотика времени работы алгорита равна <tex>O(n + n \log n)</tex>.
 
Так как [[Сортировка|сортировка]] весов занимает <tex>O(n \log n)</tex> время, то асимптотика времени работы алгорита равна <tex>O(n + n \log n)</tex>.
  
 +
===Вариант 3===
 +
<tex> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
 +
 +
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \ldots , n</tex>.
 +
 +
 +
Нам нужно распределить <tex>n</tex> работ в разное время. Если мы назначим время <tex>t</tex> для работы <tex>i</tex> то цена будет <tex>f_i(t + 1)</tex>. Функция <tex>f_i</tex> монотонно неубывающая, тогда работы в расписании надо располагать как можно раньше для получения верного решения. <tex>n</tex> временных интервалов <tex>t_i</tex> для <tex>n</tex> работ могут быть получены с помощью следующего алгоритма, где предполагается что работы отсортированы так:
 +
 +
<tex> r_1 \leqslant r_2 \leqslant \ldots \leqslant r_n</tex>
 +
 +
'''Псевдокод'''
 +
 +
  <tex>t_1 \leftarrow r_1 </tex>
 +
  '''for'''  <tex> i \leftarrow 2</tex> '''to''' <tex>n</tex> '''do'''
 +
      <tex> t_i \leftarrow </tex> max<tex>(r_i, \ t_{i-1} - 1)</tex>
 +
 +
Этот алгоритм работает за <tex>O(n \log n +n)</tex>
 
==Основная задача==  
 
==Основная задача==  
 
===Описание алгоритма===
 
===Описание алгоритма===

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

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

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

Шаблоны, используемые на этой странице: