47
правок
Изменения
м
Пояснил, почему 2logn
* Для четырех уровней: <tex> 4 \sqrt[4]{n}</tex>
* Для пяти уровней: <tex> 5 \sqrt[5]{n}</tex>
* Для <tex>\log{n}</tex> уровней: <tex> \log{n} \times \sqrt[\log{n}]{n} = n ^ {\frac{1}{log{n}}} \log{n} = n ^ {\log_n{2}} \log{n} = 2 \log{n}</tex>
В списках с пропусками, в которых содержится <tex>\log{n}</tex> уровней будет себя вести очень похоже на сбалансированные бинарные деревья поиска. В идеальной данной структуре соотношение между соседними уровнями будет равняться двум. Поиск в <tex>\log{n}</tex> списке с пропусками будет осуществляться за асимптотическое время <tex>O(\log{n})</tex>.
