algorithm - 选择，使用三元比较器查找集合中的最大值

Question

让 S 是一组 n>0 不同整数。假设 n 是 3 的幂。三元比较可以比较集合 S 中的三个数字，并将它们从最大到最小排序。

描述一个有效的算法，它使用尽可能少的三元比较来找到集合 S 中的最大数。解释为什么你的算法是正确的，并说明它在最坏情况下使用的三元比较的确切数量。

这是一个中期问题。

我的回答如下：

T(n) = 3T(n/3) + 1

解析为 (n/2) -1

有没有更有效的方法来做到这一点？

谢谢。

Answer 1

我不认为你能做得比这更好。请注意，每次比较都可以让您完全放弃考虑的两个数字。你应该得到 (n-1)/2，而不是 (n/2)-1。