algorithm - B 树中查找的复杂性

Question

如何计算分支因子为 100 的 B 树中查找的复杂度？我什至需要分支因子吗？我认为这个问题可能只是在误导我。

在 Google 上，它表示 B 树的大 O 查找时间是 O(log(n))。这就是为什么我真的很困惑为什么这可能取决于分支因素？这是否意味着答案是 O(log_100(n))？

谢谢

Answer 1

在这样的数据结构中查找需要:-

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

树的深度为 log(元素数量)/log(100)，其中 log 是 base2。

搜索要下降到哪个 child 将需要使用二进制搜索进行 log(100) 操作。