48
правок
Изменения
Нет описания правки
=== Асимптотика ===
Сначала мы сортируем работы и станки, что занимает <tex> \mathcal{O}(n\log{n})</tex> и <tex> \mathcal{O}(m\log{m})</tex>. Так как мы можем предположитьпри <tex>m \geqslant n</tex>, что количество станков меньше или равно колиеству работ <tex>m \leqslant - n</tex>самых медленных станков можно не использовать, то в итоге сортировка займет <tex> \mathcal{O}(n\log{n})</tex>.
Количество прерываний ограничено числом <tex>(m-1) \cdot n - (1 + 2 + \ldots + (m - 1)) = (m - 1) \cdot (n - \cfrac{m}{2})</tex>.
В итоге всё вместе составляет асимптотику алгоритма <tex> \mathcal{O}(n\log{n} + mn)</tex>.
