Page 121 - Bkhargava_-_Grokaem_algoritmy

120 Глава 5. Хеш-таблицы

не встречались. Оно не означает, что операции выполняются мгновенно;
просто время остается постоянным независимо от размера хеш-таблицы.
Например, вы знаете, что простой поиск выполняется за линейное время.

()(.>\)
f\ИНЕКНОЕ &РЕМ.Я
(П Рос.ток ПОИС.К)

Бинарный поиск работает быстрее - за логарифмическое время:

Q(lo~n)
мrАРИФМИЧЕС.КОЕ &РЕМ.Я
(БМНАРНЫК ПОМС.К)

Поиск данных в хеш-таблице выполняется за постоянное время.

L

Q(})
nос.тоянноЕ &РЕМ.Я
(XEOl-TA БЛИЦЫ)

Видите горизонтальную линию? Она означает, что при любом размере
хеш-таблицы - 1 элемент или 1 миллиард элементов - выборка данных
займет одинаковое время. На самом деле вы уже сталкивались с постоян­
ным временем: получение элемента из массива выполняется за постоянное

www.trk.kg