在对数时间内找到未排序数组中的最小值

Question

是否有一种算法方法可以在对数时间（ O(logn) ）内找到未排序数组的最小值？或者只能在线性时间内实现？我不想并行。

谢谢

迈克尔

Answer 1

如果列表未排序，则您的搜索必须至少是线性的。您必须至少查看每个项目一次，因为您没有查看过的任何内容可能都会少于您已经看过的内容。

Answer 2

一般来说，并行并没有什么帮助。如果您的处理器数量多于n，并且您不计算加载数据所需的时间，即 O(n) ，那么是的，你可以在对数时间内完成。但假设每个处理器有 10 个数字。这需要一定的时间。现在每个处理器有 20 个数字。在并行比较彼此的结果之前，每个处理器将花费两倍的时间来处理其数字。 O(n) + O(log n) = O(n)。

Answer 3

它不可能在线性时间内，因为在 lg n 步骤中，您只能检查 lg n 元素，并且因为它们是未排序的，所以这些值不包含有关其他值的信息数组。

Answer 4

你是说最小值？

这是线性的 - 您迭代数组，保存最不为人知的元素的位置（或值本身）并将每个元素与其进行比较。元素是否较低，请保存它。最后你得到了最小元素的位置（或值）。

我用 C++0x 做了一个简短的示例：

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
   std::vector<int> array({5, 3, 2, 7, 5, 1, 9});

   int min = array[0];

   std::for_each(array.cbegin(), array.cend(), [&min] (const int cur) {
      min = std::min(cur, min);
   });

   std::cout << min;
}

您可以在 Ideone 执行它

Answer 5

线性排序不是，但是如果使用某种改进的快速排序，对于少于 10 个元素，它可以比线性排序更快。我怀疑您正在寻找数组中少于 10 个的项目:)

实现它的另一种方法是深入研究 SSE 指令的世界。

CMPLEPS 是一种可以提供帮助的操作码，它一次并行比较 4 个标量。

如果您不愿意在并行代码中执行此操作，但我严重怀疑您是否愿意使用 SSE 汇编指令。

Answer 6

您还可以为此采用分而治之的递归算法，代码：

private static Integer array[];

private static Integer findMinimum(int startIndex, int endIndex){

   //base case
   if(startIndex + 1 == endIndex || startIndex == endIndex){
     return array[startIndex] < array[endIndex] ? array[startIndex] : array[endIndex];
   }

   //recursive case
   int a = findMinimum(startIndex, (startIndex + endIndex) / 2 );   
   int b = findMinimum( (startIndex + endIndex) / 2 + 1, endIndex); 

   return Math.min(a, b);
}

此算法的运行时间为：O(n)

但是，如果您有 N 个处理器（我知道这不是一个“有效的”现实世界场景，这仅对理论讨论有意义）。您可以进行并行计算，并且运行时间为：O(log n)

因此，如果您想做一些并行计算，您可能需要尝试这种方法。