在同时进行的最大和最小元件比较的数 [英] number of comparisons in simultaneous maximum and minimum element

问题描述

这是个问题，我试图解决：

This is the question I'm trying to solve:

下面的分而治之算法寻找同时最大值和最小值：

The following divide-and-conquer algorithm is proposed for finding the simultaneous maximum and minimum:

• 如果有一个项目时，它是最大和最小

• If there is one item, it is the maximum and minimum

如果有两个项目，然后对它们进行比较，在一个比较可以找到最大和最小。

if there are two items, then compare them and in one comparison you can find the maximum and minimum.

否则，分割输入成两半，分为均匀为可能（如果N为奇​​数，两个半部中的一个将有一个比另一个更元件）。

Otherwise, split the input in two halves, divided as evenly as possibly (if N is odd, one of the two halves will have one more element than the other).

（b）假设N是形成3 + 2K的。什么是比较使用该算法的确切数字？

(b) Suppose N is of the form 3 + 2k. What is the exact number of comparisons used by this algorithm?

这点（B），我试图找到一个递推公式来解决，但没有奏效。 我试过

for this point (b), I tried to find a recurrence equation to solve but it didn't work. I've tried

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

其中，三是成本最低，当我尝试3输入。 任何帮助吗？

where three is the minimum cost when I try 3 inputs. any help?

推荐答案

您递推公式不应该有一个期限为n的特例= 3的算法为您提供了以下事实：

Your recurrence equation should not have a term for the special case of n = 3. The algorithm gives you these facts:

• T（1）= 0
• T（2）= 1
• T（N）（N> 2）= T（地面（N / 2））+ T（CEIL（N / 2））+ 2

这应该是所有你需要计算出答案。

That should be all you need to work out the answer.

这篇关于在同时进行的最大和最小元件比较的数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！