Сложность контейнера
Следовательно, у меня есть std::set<int> а также std::list<int>,
Я хочу отсортировать мой контейнер.
Для набора у меня будет сложность, как O(nlogn) за n вставленные элементы.
Для списка у меня будет сложность, как O(n) для вставки n элементы + O(nlogn) для вызова list::sort,
В обоих случаях сложность O(nlogn), но есть дополнительные O(n) операции в случае std::list, И у меня есть некоторое постоянное время для set восстановление равновесия.
Вот вопрос, какой контейнер будет работать быстрее?
Решение
Как хочешьConstотсортированный контейнер, предлагаю std::vector который кеш дружественен.
Во время инициализации:
push_backвсе элементыO(n),std::sortвекторO(n log n),std::uniqueесли вы хотите удалить дубликаты (какstd::setделает).O(n),
Итак, инициализация O(n log n),
Чтобы проверить, существует ли элемент, используйте std::binary_search иметь O(log n) вместо O(n),
Другие решения
Других решений пока нет …