Хочу узнать какого время работы при использовании массива map(С++). P.S не могу сдать задачу, у меня по ней TL :( использую в ней map. В Google'e искал не нашел или
плохо ищу.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 141 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 136 |
| 8 | BledDest | 132 |
| 9 | maroonrk | 131 |
| 10 | qwexd | 129 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.09.2026 04:22:21 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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;а где я могу узнать конкретную цифру константы? Много раз слышал, но ни разу своими глазами не видел ее(константу)
Нигде по факту. Просто проверь сам.