4

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

谢谢

迈克尔

4

6 回答 6

16

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

于 2011-03-24T15:25:57.117 回答
2

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

于 2011-03-26T01:11:23.500 回答
1

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

于 2011-03-24T15:25:55.293 回答
0

你的意思是最小值？

那是线性的 - 你遍历你的数组，保存最不为人知的元素的位置（或值本身）并将每个元素与之进行比较。是不是元素较低保存它。最后你有最小元素的位置（或值）。

我在 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执行它

于 2011-03-24T15:26:30.413 回答
0

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

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

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

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

于 2011-03-24T16:12:30.010 回答
0

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

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)

所以，如果你想做一些并行计算，你可能想尝试这种方法。

于 2013-09-16T22:58:13.383 回答