Хочу узнать какого время работы при использовании массива map(С++). P.S не могу сдать задачу, у меня по ней TL :( использую в ней map. В Google'e искал не нашел или
плохо ищу.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3857 |
| 2 | jiangly | 3747 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3591 |
| 6 | gamegame | 3477 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3463 |
| 9 | ecnerwala | 3451 |
| 10 | heuristica | 3431 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | -is-this-fft- | 161 |
| 3 | Qingyu | 160 |
| 4 | Dominater069 | 159 |
| 5 | atcoder_official | 157 |
| 6 | adamant | 153 |
| 7 | Um_nik | 152 |
| 8 | djm03178 | 151 |
| 9 | luogu_official | 150 |
| 10 | awoo | 147 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2025 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 28.02.2025 15:33:58 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
map использует красно-черное двоичное дерево, поэтому операции добавления, поиска, удаления должны выполняться за O(log(N))
Спасибо
3105513 берет ТL. Использую map <string, bool>. Общее время должно работать за N*N(log(N)), но почему TL?
Потому что сравнение строк работает за их длину. Так что поиск элемента в map будет близко к log(N)*N
Ок, ясно
программа съела 200 мб оперативки, похоже на то что в мапе у тебя порядка N^2 строк длины O(N) т.е. время работы никак не ниже N^3, а это многовато.
Стоит ещё заметить, что, хоть в
std::mapоперации и выполняются за логарифм, но в GNU C++ константа у них довольно большая, т.е.,std::mapмедленный.std::unordered_map(хешмап) в большинстве случаев работает заметно быстрее.По-поводу константы в
std::map. Eсли задача не онлайн, то лучше писать на масиве с бинпоиском. upper/lower _bound работают заметно быстрее.У upper/lower _bound не лучшая константа. Можно написать оптимизированный бинпоиск, приведенный ilyaraz (http://codeforces.me/blog/entry/1878)
У меня компилятор не находит библиотеку
#include <unordered_map>дляstd::unordered_map. Как тут быть? И где можно найти мануал по ней?std::unordered_setиstd::unordered_mapпоявились только в новом стандарте C++11. Не все компиляторы его поддерживают. GNU C++ (версии где-то с 4.4 или 4.5) частично поддерживает, но компилировать надо с параметром-std=c++0xили-std=c++11.Мануал здесь: http://cplusplus.com/reference/unordered_map/unordered_map/
еще можно поискать в tr1
#include <tr1/unordered_map>using namespace tr1;а где я могу узнать конкретную цифру константы? Много раз слышал, но ни разу своими глазами не видел ее(константу)
Нигде по факту. Просто проверь сам.