每個節點上有三個孩子的樹搜索的時間複雜度

Question

在二叉搜索樹的情況下，查找元素的時間複雜度爲O(logn)，每次迭代一次，要搜索的元素減半。但是如果在每個節點下面有一棵樹最多有三個孩子，並且考慮到我們在三個分支中有下一個搜索分支的條件，那麼時間複雜度是多少。在這種情況下，要搜索的元素每次減少1/3。

Answer 1

閱讀答案here和明白爲什麼二叉樹的遞推關係是

T(n) = T(n/2) + O(1)

在樹中有3個或更多節點一般k個節點的情況下，同樣的關係將是

T(n) = T(n/k) + O(1)

沿着這個答案，你會知道，任何k-ary樹，二進制搜索將採取O（日誌_ķ N）

Answer 2

我要說什麼了複雜性是O（鑑於你有一些條件的三個分支之間未來要搜索的分支登錄 N）。

在最壞的情況下，每次迭代都會減少3倍的剩餘迭代次數。