21 July 2010

Сравнение характеристик структур для операций поиска

Lumber room
При рассмотрении реализаций поиска нашёл интересную таблицу с характеристиками структур, применяемых для реализации символьных таблиц. Причём рассматриваются худшие и средние случаи.

худший случай средний случай
вставка поиск выбор вставка попадание при поиске промах при поиске
массив, индексированный по ключам 1 1 M 1 1 1
упорядоченный массив N N 1 N/2 N/2 N/2
упорядоченный связный cписок N N N N/2 N/2 N/2
неупорядоченный массив 1 N NlnN 1 N/2 N
неупорядоченный связный список 1 N NlnN 1 N/2 N
бинарный поиск N lnN 1 N/2 lnN lnN
дерево бинарного поиска N N N lnN lnN lnN
дерево типа "красное-черное" lnN lnN lnN lnN lnN lnN
рандомизованное дерево N N N lnN lnN lnN
хеширование 1 N NlnN 1 1 1
Tags:searchalgorithms
Hubs: Lumber room
-1
183 0
Comments 4
Popular right now
SEO-специалист
December 7, 202064,900 ₽Нетология
iOS-разработчик с нуля
December 7, 202070,740 ₽Нетология
Python для работы с данными
December 7, 202031,500 ₽Нетология
UX-дизайнер
December 7, 202047,940 ₽Нетология
Top of the last 24 hours