Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   Почему hash table имеет сложность O(1)? (https://javascript.ru/forum/misc/83541-pochemu-hash-table-imeet-slozhnost-o-1-a.html)

jaroslav.tavgen 06.01.2022 18:39

Почему hash table имеет сложность O(1)?
 
Лично я представляю Hash Table примерно так:

let array = Array.from({length:5}, _=>Math.floor(Math.random()*100));
let keys = [];
for(let i = 0; i < 100; i++){
  keys[i] = array.includes(i)?i:0;
}
// Дальше уже делаем с массивом то, что хотели: сортируем или находим сумму элементов или ещё что-нибудь

В данном конкретном примере это куда как ближе к O(n^2) (O(n^2 + 75) = O(n^2)), чем к O(1).

Почему же считается O(1)? Только потому что 100 - константа? Или я вообще всё неправильно понимаю?:)

Aetae 06.01.2022 19:59

O(1) - в подавляющем большинстве случаев. O(n) - в очень редком, когда надо рехэшить всю таблицу. Там ничто не ищется в цикле, хэш указывает куда надо смотреть сразу, без каких-либо переборов.
Как это достигается? По-разному, открой википедию и почитай.


Часовой пояс GMT +3, время: 07:19.