История изменений
Исправление iVS, (текущая версия) :
Дерево Ван Боаса — это только теория, показывающая, что поиск из N целочисленных элементов, значения которых не превосходят U, можно делать за O(log log U), занимая память O(N). Но эти «O» слишком велики, чтобы говорить про какое-то практическое применение. Есть очень близкие к дереву Ван Боаса решения — X-fast и Y-fast деревья. У них используется perfect hashing, так что получается слишком непрактично.
Исправление iVS, :
Дерево Ван Боаса — это только теория, показывающая, что поиск из N челочисленных элементов, значения которых не превосходят U, можно делать за O(log log U), занимая память O(N). Но эти «O» слишком велики, чтобы говорить про какое-то практическое применение. Есть очень близкие к дереву Ван Боаса решения — X-fast и Y-fast деревья. У них используется perfect hashing, так что получается слишком непрактично.
Исходная версия iVS, :
Дерево Ван Боаса — это только теория, показывающая, что поиск из N элементов, значения которых не превосходят U, можно делать за O(log log U), занимая память O(N). Но эти «O» слишком велики, чтобы говорить про какое-то практическое применение. Есть очень близкие к дереву Ван Боаса решения — X-fast и Y-fast деревья. У них используется perfect hashing, так что получается слишком непрактично.