Почему сложность B-дерева равна O (log n), это не двоичное дерево

Согласно Wiki и GFG временная сложность поиска/вставки/удаления B-дерева составляет O(log n). Дерево B может иметь > 2 дочерних элементов, т. е. это не бинарное дерево. Так что я не понимаю, почему это log n - разве это не должно быть быстрее, чем log n? Например, поиск должен быть в наихудшем случае O(h), где h — высота дерева.


time-complexity b-tree
person aol    schedule 14.08.2019    source источник
comment
Почему тройка с тремя детьми не может быть log(n)?   -  person Willem Van Onsem    schedule 14.08.2019
comment
насколько я понимаю из ответов, это будет журнал n другой базы (база 3 в вашем примере)   -  person aol    schedule 16.08.2019
comment
правильно, но loga(b) — это всего лишь log(b)/log(a), следовательно, это постоянный коэффициент.   -  person Willem Van Onsem    schedule 16.08.2019

Ответы (3)


arrow_upward
2
arrow_downward

B-дерево — это обобщение двоичного дерева, в котором каждый узел может иметь более двух дочерних элементов. Но это не точно. Если, например, количество дочерних элементов для каждого узла было определено как x, тогда сложность будет log_x n. Однако, когда минимальное количество дочерних элементов равно 2 (как в B-Tree), максимальная высота дерева будет logn, и, как упоминалось в предыдущем ответе, Big-O рассматривает наихудший сценарий, который представляет собой дерево с наибольшей высотой (логарифмическая база 2). Следовательно, сложность B-дерева составляет O(logn).

person Hadi GhahremanNezhad    schedule 14.08.2019
comment
Понятно! Спасибо. - person aol; 16.08.2019

arrow_upward
0
arrow_downward

да, это не бинарное дерево. Но если мы выполняем алгоритм бинарного поиска внутри узла (для ключа внутри узла), сложность времени можно рассматривать как O (logn).

Давайте рассмотрим,

степень B-дерева (максимальное количество детей на узел) ≤ m. общее количество узлов в узле: n

если дело обстоит так, как указано выше,

высота дерева равна 

O(logmn)   ----------(1)
, так как количество дочерних элементов может быть изменено на узел, придется выполнять логарифмический поиск по порядку узлов 
(lgm)   ----------(2)

поэтому общая сложность поиска в двоичном дереве равна

O(logmn) . O(lgm)   ----------(3)

согласно логарифмической операции ,

{logba = logca / logcb}

применяя вышеуказанную операцию к (3)

O(logmn) . O(lgm) = O(lgn/lgm) . O(lgm)
                  = O(lgn)

поэтому временная сложность дерева B для операции поиска составляет O(lgn)

person Pubudu Mahesh Meththananda    schedule 12.06.2021

arrow_upward
-1
arrow_downward

Big-O — это мера наихудшей сложности; поскольку узлы B-дерева не обязаны иметь более 2 дочерних элементов, в худшем случае ни один узел не имеет более 2 дочерних элементов.

person Scott Hunter    schedule 14.08.2019