algorithm - 同时最大和最小元素的比较次数

Question

这是我要解决的问题:

---

提出了以下分而治之算法来寻找同时的最大值和最小值:

• 如果有一项，就是最大值和最小值

• 如果有两项，则比较它们，一次比较就可以找到最大值和最小值。

• 否则，将输入分成两半，尽可能均匀地分开(如果 N 是奇数，则两半中的一个将比另一半多一个元素)。

• 递归地找出每一半的最大值和最小值，然后在另外两次比较中得出整个问题的最大值和最小值。

(b) 假设 N 的形式为 3 + 2k。该算法使用的确切比较次数是多少？

---

对于这一点(b)，我试图找到一个递归方程来求解，但没有成功。我试过了

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

当我尝试 3 个输入时，其中 3 是最低成本。有帮助吗？

Answer 1

您的递归方程不应该包​​含 n = 3 的特殊情况的项。该算法为您提供了以下事实:

• T(1) = 0
• T(2) = 1
• T(n) (n > 2) = T(floor(n/2)) + T(ceil(n/2)) + 2

这应该是您计算出答案所需的全部内容。