найти 4-й самый маленький элемент в линейном времени - PullRequest
Новая
       5

найти 4-й самый маленький элемент в линейном времени

0 голосов
/ 17 января 2020

Итак, мне было дано упражнение, длившееся мне около 2 месяцев go, которое говорит следующее:

Учитывая n (n> = 4) различных элементов, разработайте алгоритм «разделяй и властвуй» вычислить 4-й самый маленький элемент. Ваш алгоритм должен работать за линейное время в худшем случае.

Мне было очень тяжело с этой проблемой, и я мог найти только соответствующие алгоритмы, которые работают в худшем случае O (n * k). После нескольких недель попыток нам удалось с помощью нашего учителя «решить» эту проблему. Последний алгоритм выглядит следующим образом: 

Rules: The input size can only be of size 2^k

(1): Divide input into n/2. One left array, one right array.

(2): If input size == 4, sort the arrays using merge sort.
     (2.1) Merge left array with right array into a new result array with length 4. 
     (2.2) Return element at index [4-1]

(3): Repeat step 1


This is solved recursively and our base case is at step 2. Step 2.2 means that for all
of our recursive calls that we did, we will get a final result array of length 4, and at that
point, we can justr return the element at index [4-1].

С этим алгоритмом мой учитель утверждает, что он работает за линейное время. Моя проблема с этим утверждением заключается в том, что мы погружаемся во входные данные, пока не достигнем подмассивов с входным размером 4, а затем они сортируются. Таким образом, для размера ввода 8 мы бы отсортировали 2 подмассива длиной 4, так как 8/4 = 2. Как это в любом случае линейное время? Мы все еще сортируем весь входной размер, но не по блокам? Это действительно не имеет смысла для меня. Неважно, будем ли мы сортировать весь входной размер или разделить его на подмассивы размером 4, и отсортировать их вот так? Это все еще будет худшее время O (n * log (n))?

Буду признателен за некоторые объяснения этого!

1 Ответ

0 голосов
/ 17 января 2020

Чтобы доказать, что алгоритм работает за линейное время, давайте немного его изменим (мы изменим только порядок деления и объединения блоков, не более того): 

(1): Divide input into n/4 blocks, each has size 4.

(2): Until there is more than one block, repeat:
        Merge each pair of adjacent blocks into one block of size 4.
        (For example, if we have 4 blocks, we will split them in 2 pairs -
        first pair contains first and second blocks,
        second pair contains third and fourth blocks.
        After merging we will have 2 blocks -
        the first one contains 4 least elements from blocks 1 and 2,
        the second one contains 4 least elements from blocks 3 and 4).

(3): The answer is the last element of that one block left.

Доказательство: факт, что Массив постоянной длины (в вашем случае 4) можно отсортировать за постоянное время. Пусть k = log (n). L oop (2) выполняет k-2 итерации (на каждой итерации количество оставшихся элементов делится на 2, пока не останется 4 элемента).

До i-й итерации (0 <= i < k-2) осталось (2 ^ (ki)) элементов, поэтому осталось 2 ^ (ki-2) блоков, и мы объединяем 2 ^ (ki-3) пары блоков. Давайте найдем, сколько пар мы будем объединять во всех итерациях. Количество слияний равно </p> 

mergeOperationsCount = 2^(k-3) + 2^(k-4) + .... + 2^(k-(k-3)) =
    = 2^(k-3) * (1 + 1/2 + 1/4 + 1/8 + .....) < 2^(k-2) = O(2^k) = O(n)

Поскольку мы можем объединить каждую пару в постоянное время (поскольку они имеют постоянный размер), и единственная операция, которую мы выполняем, - это объединение пар, алгоритм выполняется за O (n).

И после этого доказательства я хочу заметить, что существует еще один линейный алгоритм, который тривиален, но он не разделяй и властвуй.

...