这是我要解决的问题:
提出了以下分而治之算法来寻找同时的最大值和最小值:
如果有一项,就是最大值和最小值
如果有两项,则比较它们,一次比较就可以找到最大值和最小值。
否则,将输入分成两半,尽可能均匀地分开(如果 N 是奇数,则两半中的一个将比另一半多一个元素)。
- 递归地找出每一半的最大值和最小值,然后在另外两次比较中得出整个问题的最大值和最小值。
(b) 假设 N 的形式为 3 + 2k。该算法使用的确切比较次数是多少?
对于这一点(b),我试图找到一个递归方程来求解,但没有成功。 我试过了
T(n)= T(n/2+1) + T(n/2) + 3
当我尝试 3 个输入时,其中 3 是最低成本。 有帮助吗?
最佳答案
您的递归方程不应该包含 n = 3 的特殊情况的项。该算法为您提供了以下事实:
- T(1) = 0
- T(2) = 1
- T(n) (n > 2) = T(floor(n/2)) + T(ceil(n/2)) + 2
这应该是您计算出答案所需的全部内容。
关于algorithm - 同时最大和最小元素的比较次数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8627292/