сложност на мултимножество, карта и хеш карта

Бих искал да знам сложността в нотацията Big O на класовете STL multiset, map и hash map, когато:

  • вмъкване на записи
  • достъп до записи
  • извличане на записи
  • сравняване на записи

c++ big-o complexity-theory
person Community    schedule 21.10.2008    source източник
comment
това всъщност е моя публикация и не мога да разбера защо изглеждам неактивен и следователно не мога да го променя...   -  person Harry    schedule 25.07.2009

Отговори (1)


arrow_upward
111
arrow_downward

map, set, multimap и multiset

Те се изпълняват с помощта на червено-черно дърво, тип балансирано двоично дърво за търсене. Те имат следните асимптотични времена на изпълнение:

Вмъкване: O(log n)
Търсене: O(log n)
Изтриване: O(log n)

hash_map, hash_set, hash_multimap и hash_multiset

Те се реализират с помощта на хеш таблици. Те имат следните времена на изпълнение:

Вмъкване: O(1) очаквано, O(n) най-лош случай
Търсене: O(1) очаквано, O(n) най-лош случай
Изтриване: O(1) очаквано, O(n) най-лош случай

Ако използвате правилна хеш функция, почти никога няма да видите най-лошия случай на поведение, но е нещо, което трябва да имате предвид — вижте Отказ на услуга чрез атаки за алгоритмична сложност от Кросби и Уолах за пример за това.

person Adam Rosenfield    schedule 21.10.2008
comment
Всичко, което казвате на hash_*, отнася ли се за C++11 unordered и Boost.Unordered контейнери? - person myWallJSON; 11.12.2011
comment
Шаблоните за клас hash_* са част от Silicon Graphics STL. Те бяха включени в ревизията на C++11 под unordered_* имена (unordered_map, unordered_set и т.н.) Освен това те бяха включени в библиотеките libstdc++, Visual C++ и Boost C++. - person milpita; 20.09.2016
comment
@CEOatApartico: Поправи мъртвата връзка - person Adam Rosenfield; 29.11.2018
comment
Не разбирам очакваното O и най-лошия случай O. Big-O по дефиниция е най-лошият случай. - person Paulius Liekis; 02.01.2021
comment
@PauliusLiekis Не знаеш за какво говориш. Big-O по дефиниция е горна граница, която няма нищо общо с най-лошия случай, ср. случай, най-добрият случай. - person ypnos; 03.01.2021
comment
За да го обясня: нотацията на Ландау описва растеж на функция. Ако правите разлика между случаите, както в hashmap, вие се занимавате с различни по сложност функции и всяка от тях има свой собствен растеж и ограничение. - person ypnos; 03.01.2021
comment
@ypnos да, признавам - не разбирам. Това всъщност ме притеснява :) Но и аз не разбирам обяснението ти :/ позволете ми да преформулирам въпроса: да кажем, че имаме std::hash_map‹std::string, T› - мога да конструирам такъв обект, където всички ключове ще живеят в една и съща кофа, като по този начин намирането на записи ще отнеме O(N) или O(log N) в зависимост от изпълнението. И така, как може да се твърди, че намирането на записи е O(1)? Искрено искам да разбера. - person Paulius Liekis; 03.01.2021
comment
Виждам обосновката следната. При дадена хеш карта с подходяща хеш функция и размер, вие очаквате размерът на кофата да не расте с n и да получите средния случай на O(1). Изборът на подходяща хеш функция е отговорност на разработчика. За да се гарантира подходящ размер (коефициент на натоварване), повторно хеширане може да се задейства при вмъкване и получаваме най-лошия случай O(n)+O(1) = O(n). Символите на Ландау не покриват такова разграничение между два различни алгоритъма! Така че всичко, което ви остава, е да посочите две различни мерки за среден и най-лош случай, като и двете могат да използват O(), o(), Ө() и т.н. - person ypnos; 05.01.2021