Почему 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 - константа? Или я вообще всё неправильно понимаю?:) |
O(1) - в подавляющем большинстве случаев. O(n) - в очень редком, когда надо рехэшить всю таблицу. Там ничто не ищется в цикле, хэш указывает куда надо смотреть сразу, без каких-либо переборов.
Как это достигается? По-разному, открой википедию и почитай. |
Часовой пояс GMT +3, время: 07:19. |