algorithm - 计算 split 为 1 的树的时间复杂度 :3 ratio unlike binary tree

Question

我们如何计算以 1:3 的比例不均匀 split 的树的时间复杂度，这与典型的二叉树 split 成两半的情况不同？

Answer 1

这有点家庭作业的味道，但我还是会试一试。

树本身并不具有时间复杂性，但我想我明白你的意思。

大多数具有良好平衡树的算法的复杂度都具有 log2(n) 分量。如果改为将它分成三份，则对数的底数将为 3/2。

因此，在常规二叉搜索树中的二分搜索的 O(log2(n)) 中，在您的场景中，它将是 O(log3/2(n))。

也就是说，可以通过乘以一个常数来改变对数的底数，而我们在复杂性理论中不考虑常数。所以从技术上讲，虽然在这种情况下最坏的情况会更慢，但它具有相同的时间复杂度。