1

Как посчитать большое О для вставки в коллекцию?

Коллекция имеет вид:

typedef std::map<std::string, tokens> Consumers;  
typedef std::unordered_set<std::string> Tokens;

Каким образом оно расчитывается? Произведение сложности вставки в unordered_set и сложности вставки в map, или иным образом?

4
  • Формально - вставка одного элемента в map - O(lg N), в unordered_set - O(1) в среднем.
    – Harry
    5 мар 2019 в 20:45
  • А можно ли посчитать суммарную сложность в этом случае?
    – st.limp
    5 мар 2019 в 20:57
  • 1
    tokens и Tokens? Язык С++ является чувствительным к регистру. 6 мар 2019 в 3:02
  • 1
    @HolyBlackCat Нет, вы неправы. Зависит от того, чего и сколько вставлять, и еще и от того, в каком порядке.
    – Harry
    6 мар 2019 в 20:59

4 ответа 4

1

Зависит от порядка.

Если вставляем по m строк в n unordered_set, имеем O(mn)+O(log n), т.е. вообще говоря O(mn).

Если вставляем n пустых unordered_set в map, а потом случайным образом (с поиском в map!) заполняем их m строками каждый, то O(log n)+O(m*n*log n), т.е. O(mn*log n).

И не забываем, что unordered_set имеет O(1) в среднем, но может иметь при невезении и O(n)...

"По-моему, так" (с) Пух

3
  • Если вставляем по m строк в n unordered_set, имеем O(mn)+O(log n), т.е. вообще говоря O(mn) Этот момент не очень понятен. Почему вставка в hashtable O(log n)? И почему O(mn) это не O(n)?
    – calm27
    6 мар 2019 в 19:31
  • 1
    @raviga Вставка в конкретную таблицу - O(1), но ее еще нужно найти - а это - O(log n). O(mn) не O(n), потому что никто не гарантирует, что m - константа. Вдруг у вас n^2 строк в каждую из n таблиц? и получите вы O(n^3) :) А вообще, это очень недопонимаемая многими тема, но, увы, она куда больше, чем можно рассказать в одном вопросе/ответе. Простейший пример с порядком вычислений - тот же поиск в массиве m раз - если он несортирован, имеем O(mn), если отсортировать - O((m+n)*log n). Да, вот так вот и записывается :) - читайте Кнута или Кормена...
    – Harry
    6 мар 2019 в 20:58
  • не уверен, что все хорошо понял, но понял, что надо это точно перечитать
    – calm27
    6 мар 2019 в 21:08
0

Исходя из определения

фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n);

вы можете сами посчитать "большое О" проведя эксперимент (например вставка 100_000 элементов), и подобрав аппроксимационную функцию.

0

Смотря что собираешься вставлять, если пару std::string и Tokens то будет сложность map( O(logn)), тк он по sting`е просто положит unordered_set. Если же достать по std::string unordered_set и вставить уже в него, тогда будет сумма сложностей. Так как сначала ищем нужный unordered_set O(logN) а потом вставляем в него O(1).

-1

Для того, чтобы правильно посчитать сложность вставки, выборки или поиска рандомного элемента в контейнере в первую очередь нужно понимать как этот контейнер сохраняется в памяти. Или это участок память без разрывов, или это связной список или дерево или хештейбл и т.п. Понимая это ,понять эффективность контейнеров станет намного проще, а с таким подходом "просто заучить" это не даст никакого понимая. Для std::map и std::unordered_map ну нужно самостоятельно ничего считать, можно посмотреть их эффективность по всем операциям здесь.

1
  • Остальные ответы или дали конкретную формулу, или посоветовали провести эксперимент. У вас ничего кроме общеговорильни. Это я поясняю, почему ставлю минус.
    – Mikhajlo
    11 мар 2019 в 5:40

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.