Изменения
Нет описания правки
===Задача 3===
<tex dpi = "200"> 1 \mid r_i,p_i = 1 \mid \sum f_i</tex>
<tex>f_{i}</tex> {{---}} монотонная функция времени окончания работы <tex>C_{i}</tex> для работ <tex>i = 1, 2, \dots , n</tex>.
===Сложность алгоритма===
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max_{i = 1}^n r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max_{i = 1}^n r_{i})\log n)</tex>
==См. также==
