algorithm - average case complexity of ternary search

Question

I need to solve for the average case complexity of ternary search. In the worst case you would do two comparisons so I assume worst case complexity looks like this:

C(n) = C(n/3) + 2

which can then be shown to be O(logn), however what would the average case look like? I'm thinking possibly this:

C(n) = C(n/3) + 1.5

since on average you might do 1 or 2 comparisons so (1+2)/3 = 1.5

Answer 1

如果我们都在谈论搜索一个元素是一个排序数组，我认为平均而言你将不得不进行 5/3 的比较。假设您首先检查要找到的元素 x 是高于还是低于放置在 A(n/3) 中的元素，其中 A 是您的排序数组，n 是它的长度。从统计上看，由于 1/3 的元素低于 A(n/3)，而 2/3 的元素更高，因此 x 有 1/3 的机会低于和 2/3 的机会高于。如果 x 较低，则不需要第二次比较，因此只需要 1。如果 x 较高，则需要与 A(2n/3) 进行比较，因此需要 2。所以平均，您将需要 (1/3)*1+(2/3)*2 = 5/3。

但这并没有改变全局复杂性，它总是 O(log n)。唯一的区别是常数因子。