Нахождение минимума в несортированном массиве за логарифмическое время

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

Для этого также можно использовать рекурсивный алгоритм «разделяй и властвуй», код:

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)

Итак, если вы хотите выполнить несколько параллельных вычислений, вы можете попробовать этот подход.

Answer 5

Линейно нет, однако он может быть быстрее линейного для менее чем 10 элементов, если используется какой-либо вид быстрой сортировки.Я сомневаюсь, что вы ищете менее 10 элементов в массиве:)

Другой способ достижения этого - погрузиться в мир инструкций SSE.

Один OPCODE, который может помочь, - это CMPLEPSкоторый сравнивает параллельно 4 скаляра за раз.

Если вы не хотите делать это в параллельном коде, я серьезно сомневаюсь, что вы хотели бы использовать инструкции по сборке SSE.

Answer 6

Вы имеете в виду минимальное значение?

Это линейно - вы перебираете свой массив, сохраняете позицию (или само значение) наименее известного элемента и сравниваете каждый элемент с этим.Элемент ниже, сохраните это вместо этого.В конце у вас есть позиция (или значение) наименьшего элемента.

Я сделал короткий пример на 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