Сложность поиска в B-Tree

Question

Как я могу вычислить сложность поиска в B-дереве, где коэффициент ветвления равен 100 ? Мне вообще нужен фактор ветвления? Я думаю, что этот вопрос может ввести меня в заблуждение.

В Google говорится, что время большого поиска для B-дерева O(log(n)). Вот почему я действительно смущен тем, почему это может зависеть от фактора ветвления? Означает ли это, что ответ O(log_100(n))?

Спасибо

Answer 1

Поиск в такой структуре данных потребует: -

O(log(100) * log(number of elements)/log(2))

Глубина дерева будет log(number of elements)/log(100), где log - base2.

Поиск, к какому дочернему элементу спускатьсяпотребует log(100) операций с использованием бинарного поиска.