Хочу узнать какого время работы при использовании массива map(С++). P.S не могу сдать задачу, у меня по ней TL :( использую в ней map. В Google'e искал не нашел или
плохо ищу.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.05.2024 08:49:27 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
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.com/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;а где я могу узнать конкретную цифру константы? Много раз слышал, но ни разу своими глазами не видел ее(константу)
Нигде по факту. Просто проверь сам.