производительность — набор C ++: количество элементов меньше значения
Предполагая, у меня есть STL set <int> s и int xКак я могу посчитать количество элементов в s которые меньше чем x?
Я ищу O(log n) (или что-то похожее; O(n)) решение;
Я уже знаю о std::distance(s.begin(), s.lower_bound(x)), но это O(n)Я верю, потому что setс не случайным доступом.
Решение
Что вам нужно, так это «дерево статистики заказов». По сути, это расширенное (бинарный поиск) дерево, которое поддерживает дополнительную операцию rank(x) который дает вам количество элементов с меньшим или равным ключом в качестве элемента x, Глава 14 в Cormen, Leiserson, Rivest, Stein; «Введение в алгоритмы» должно дать вам алгоритмический фон.
Существует также некоторая реализация на Web.
Другие решения
Я не думаю, что это возможно. Ваш набор STL является древовидной структурой, поэтому даже проверка наличия элемента — это O (log n). Узлы вашего дерева не хранят размеры своих подветвлений в каком-либо поле (насколько я знаю), поэтому количество операций, необходимых для подсчета узлов, обладающих некоторым свойством, которое не следует непосредственно из правил, используемых для построения дерева, не может быть меньше чем количество этих узлов. Поскольку вы заранее не знаете, сколько узлов имеют значения, меньшие x, производительность в худшем случае — когда все узлы меньше x, что означает O (n) сложность в худшем случае. Даже если значение x было в дереве, вам нужно O (log n) операций, чтобы найти этот узел, но затем нужно посетить все его левые потомки, чтобы подсчитать их, поэтому сложность зависит от количества совпадающих узлов, которое равно O ( о) в худшем случае. Возможно, с дополнительными данными в узлах дерева, можно было бы добиться большего, чем это.
Как продолжение моего комментария: используя красно-черные двоичные деревья поиска (вместо наборов), если каждый узел хранит количество узлов, укорененных в этом узле (обновляется каждый раз, когда вы вставляете / удаляете узел), тогда вы можете получить по адресу » Количество узлов больше / меньше X «Статистика довольно быстрая.
detector