37
правок
Изменения
Нет описания правки
<tex> \mathtt{time++}</tex>
===Сложность алгоритмов===
====Алгоритм 1====
Множество <tex>S</tex> станет пустым не позже, чем через <tex>n + \max\limits_{i = 1 \ldots n} r_{i}</tex> шагов цикла. Определить максимум в множестве можно за время <tex>O(\log n)</tex>, используя , например, [[:Категория:Приоритетные_очереди|очередь с приоритетами]]. Значит общее время работы алгоритма <tex>O((n + \max\limits_{i = 1 \ldots n} r_{i})\log n)</tex>
====Алгоритм 2====
В начале алгоритма мы добавляем все элементы <tex>w_i</tex> в двоичную кучу тратя на это <tex>O(n \log n)</tex> времени. Затем мы тратим <tex>O(n \log n)</tex> на получение ответа. Тогда суммарное время работы алгоритма составит <tex>O(n \log n + n \log n)</tex> что есть <tex>O(n \log n)</tex> времени.
==См. также==
