列表中的最大和最小元素

Question

寻找未排序的n个不同元素中最大值和最小值所需的最少比较次数是多少？

上述算法的最佳时间复杂度可能是什么？

从最少比较次数的角度，我指的是针对最坏情况最有效的算法。

- Atishay

Answer 1

最优算法需要进行3/2*n次比较。

它的工作原理如下：

5 2 6 7 3 1 10 35 4 6

1. [5] [6]
   
2. [5, 2], [6, 4]
   
3. [5, 2, 6], [6, 4, 35]
   
4. [5, 2, 6, 7], [6, 4, 35, 10]
   
5. [5, 2, 6, 7, 1], [6, 4, 35, 10, 3]
   

每一步（n/2步），您将比较第i个和第n-i个元素，并移动到“bigger”和“lower”表格。

n/2步后，您知道最小值在“lower”表格中，最大值在“bigger”表格中。在这两个表格中查找最小值和最大值是(n/2) * 2，因此总共进行了(3/2) * n次比较。

- Marcin Krupowicz

---

这是否有证据表明这是最优的？此外，所有答案都忽略了 OP 提出的这个问题是关于具有不同元素的数组的。这可能会改变事情。 - IVlad

您可以通过消除中间表来减少内存使用。在A部分期间，不要将每个比较的较小值添加到“lower”表中，而是将其与当前最小数字进行比较/替换，并对每个比较的较大值执行相同操作。 - oosterwal

如果元素数量为奇数，会发生什么？ - user

抱歉，您能再详细解释一下吗？当您在每个步骤（n/2）中比较第i个元素和第n-i个元素并将其移动到“更大”和“更小”的表格时，您的意思是什么？ - Jwan622

抱歉，我很难理解这个。 - Jwan622

Answer 2

这是 N * (3/2).

- n. m.

---

你有参考资料证明这是最优的吗？ - IVlad

这不是平均比较次数而是最小比较次数吗？ - Chris

我想我曾经有一个证明，但是我忘了。@Chris：不，这不是平均情况，而是最坏情况。 - n. m.

@n.m.：啊，是这样。虽然我不确定为什么，但问题仍然在询问最小值（尽管最坏情况可能更有用）。 - Chris

“最小要求是什么”通常是指“最小值是多少，以便存在一种算法，该算法在最多X次操作内找到答案。” - n. m.

Answer 3

下限（从记忆中重建；不确定引用应该是什么）

当n为偶数时，此处有一个对手会强制进行(3/2) n - 2次比较，而当n为奇数时，则需要(3/2) n - 3/2次比较。Marcin所描述的算法，在经过仔细分析后，可以达到这些下限。

每个元素都处于四种状态之一：{min, max}（从未被比较过，因此可以是最小值或最大值），{min}（从未大于另一个元素，因此可以是最小值但不是最大值），{max}（从未小于另一个元素，因此可以是最大值但不是最小值），{}（大于另一个元素，小于另一个元素，既不是最小值也不是最大值），其中“可以是…”意味着存在与算法执行的比较兼容的总序，以便…成立。

设T为元素e的状态基数之和。在开始时，T = 2n。在结束时，T = 2，否则最小值或最大值将不唯一确定。以下对手确保T每次比较时至多减少2，并且除非两个元素首次进行比较，否则至多减少1。由此得到了上述下限。

对手必须保持T不会过快减少，同时至少保留一个一致的总序。对手如何确定比较结果？如果两个元素都不处于状态{min, max}中，则很容易解决。状态不同，我们根据{min} < {} < {max}进行解决，并且T保持不变；或者它们相同，我们给出任意一致的答案，并且T减少1。我们通过反证法证明了一致性得以维护。假设最近的比较创建了一个循环。现在循环中的所有元素都必须处于状态{}中，这仅在两者先前都处于状态{}时才可能发生。这与我们为处于相同状态的元素一致地回答的策略相矛盾。

否则，至少要比较的其中一个元素处于状态{min, max}中。如果另一个元素处于状态{min}中，则{min} < {min, max}。如果另一个元素处于状态{max}中，则{min, max} < {max}。否则，任意解决即可。显然，当且仅当比较是在两个{min, max}元素之间进行时，T减少2。这种比较不会创建循环，因为处于状态{min, max}的元素在比较图中的度数为1。

- cutting plane

Answer 4

这可以通过以下方式实现

3*n/2-2 list element comparisons if n is even
3*(n-1)/2 list element comparisons if n is odd.

这里是代码

minVal = maxVal = a[0];
int i;
for(i = 1; i < n-1; i += 2) {
    if(a[i] < a[i+1]) {
        if(a[i] < minVal)
            minVal = a[i];
        if(a[i+1] > maxVal)
            maxVal = a[i+1];
    }
    else {
        if(a[i+1] < minVal)
            minVal = a[i+1];
        if(a[i] > maxVal)
            maxVal = a[i];
    }
}
// here i == n-1 or i == n
if(i < n) {
    if(a[i] < minVal)
        minVal = a[i];
    else if(a[i] > maxVal)
        maxVal = a[i];
}  

- Johan Råde

---

所以如果 n 是2，可能需要2次比较？听起来不太理想。 - Steve Jessop

为什么需要检查 if(i < n)，你能解释一下吗？ - user

例如，n = 6。然后循环的第一次迭代处理a [1]和a [2]。第二次迭代处理a [3]和a [4]。然后我们以i = 5退出循环。然后条件为真，if块处理a [5]。 - Johan Råde

@Steve Jessop：我已经修复了答案。 - Johan Råde

Answer 5

如果您想比较数字值，实际上可以完全不需要进行任何比较！诀窍是扩展两个值之间差异的符号位，并将其用作二进制掩码。

也许这更像是一个聪明的技巧，而不是您正在寻找的“计算机科学”的答案，但是，根据编译器和 CPU 的不同，以下方法可能比使用 if 语句的其他方法更快：

void minmax(int values[], size_t count) {
  int min = values[0];
  int max = min;
  for(int i = 1; i < count; ++i) {
    int v = values[i];
    int maxMask = (v - max) >> 31;  // assuming 32-bit int
    max = (max & maxMask) | (v & ~maxMask);
    int minMask = (min - v) >> 31;
    min = (min & minMask) | (v & ~minMask);
  }
  printf("max=%d min=%d\n", max, min);
}

示例调用：

int main() {
  int values[] = {
    20, -5, 13, -100, 55
  };
  minmax(values, 5); // prints max=55 min=-10
}

总计：0次比较，除了循环使用的一次之外，如果展开循环，则可以将其删除 :-)

这个算法的好处是它在机器代码层面上不使用条件跳转，因此没有管道停顿的风险。该算法也可以轻松地扩展到同时比较多个值（例如使用64位寄存器同时比较八个字节）。

- Martin Vilcans

---

哇！这真的很酷！你有没有进行过分析，将这种方法与更标准的方法进行比较？ - Johan Råde

@user763305：不，我还没有对此进行基准测试。无论如何，您可以将此技巧与其他人提到的更高级算法一起使用。 - Martin Vilcans

Answer 6

实际上它在n-1和2(n-1)之间，因为您必须将每个元素与当前的最大值和最小值进行比较，但如果第一个比较返回true，则不必执行第二个比较

从其他答案中借鉴代码，我的解决方案如下：

var largest = list[0];
var smallest = list[0];
for(var i=1;i<list.length;i++)
{
    if(list[i] > largest) {
        largest = list[i];
    } else if(list[i] < smallest) {
        smallest = list[i];
    }
}

如果您的原始列表按升序排序，此代码将进行n-1次比较。如果按降序排序，它将进行2n-2次比较。对于所有其他情况，它将介于两者之间。

- biziclop

---

不是，这还不是最小的。 - n. m.

在最好的情况下，它是这样的。平均而言，它与其他算法持平。 - biziclop

@n.m.：他提供的n-1的最小值比你提供的3n/2的最小值要小，所以你需要更详细地解释你的评论。 - Chris

@Chris：最好的情况并不有趣。一个已排序的数组需要n-1次比较和0次交换来进行排序。这并不是比较排序算法的基础。 - n. m.

@n.m.：是的，但问题说的是最小数量，而且没有人实际上在这个问题上纠正原帖作者，所以在评论中或者你的回答中提到这个问题可能是值得的。 - Chris

Answer 7

这里有一个带有工作代码的好的解释。 复杂度为O((3n/2)-2)。

它还解释了奇数大小数组的情况，你只需要进行填充即可。

- user2228512

Answer 8

使用maxmin算法[https://en.wikipedia.org/wiki/Minimax][minmax]

在n个不同元素中查找最大值和最小值所需的比较次数为(3/2)n - 2。

nums是一组数字，n(nums)是nums中元素的数量：

minMax (nums) {
   if (n(nums) == 2) {
      nums = {x, y};
      return (max (x, y), min (x, y));   
   }
   else {
      divide nums equally into two sets, set1, set2;
      minMax (set1);
      minMax (set2);
   }
}

- jaxkewl

Answer 9

我猜应该是 (n-1) * 2。

var largest = list[0];
var smallest = list[0];
foreach(var i in list.Skip(1))
{
  if(i > largest)
      largest = i;
  else if(i < smallest)
      smallest = i;
}

- Ankur

---

错误，那不是最小值。 - biziclop

如果第一个 if 为真，你真的需要运行第二个吗？ - IVlad

这只是挑剔，但你发布的代码由于i<list.length条件使用了比你声称的多n次比较。 - blubb