C++: найти максимальное целое число в массиве подматриц

Question

У меня возникла проблема, когда я хочу написать алгоритм, который может возвращать максимальный элемент каждого последовательного подматрица из k элементов в более крупном массиве и эти максимальные элементы чтения в их собственный массив, например, так:

Given int array = {3, 7, 20, 6, 12, 2, 0, 99, 5, 16}, and int k = 4, 
--> creates the array {20, 20, 20, 12, 99, 99, 99} 
[because there are 7 consecutive sub-arrays of size 4 within the given array: 
{3, 7, 20, 6}, {7, 20, 6, 12}, {20, 6, 12, 2}, ... , {0, 99, 5, 16} 
and the max element of these, respectively, is 20, 20, 20, ..., 99 which 
are read into the resulting array. 

Теперь здесь мой вопрос: Я знаю, как реализовать это в O (N^2) сложность, но хочу сделать это быстрее, например что это может быть O (n), или если это невозможно, O (nlog (n)). Кто-нибудь знает, есть ли более быстрый способ сделать это, и если да, то как?

Answer 1

Во-первых, сложность наивным алгоритма О (к (п-к + 1)) (как правило, это приближается к O (k.n)), а не О (п^2). Вот где, для каждого последовательного подмассива (n-k + 1 возможно), вы должны выполнить k сравнения.

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

Для каждой итерации через свой набор данных вы исследуете первый элемент maximums. Вы удаляете любые «истекшие» индексы, и теперь первый элемент - ваш ответ для текущей итерации.

Как вы слайд окна (размер к) по вашим данным, вы толкаете текущий индекс на maximums, а затем подрезать его следующим образом: значение по индексу maximums[i]должен быть меньше, чем значение по индексу maximums[i-1] , Если это не так, вы продолжаете пузырить индекс в начале maximums, по одному пятну за раз, пока это не станет истинным.

В действительности, лучше всего обработать массив maximums в качестве кольцевого буфера. Процесс обрезки сократит хвост назад к голове, в то время как при появлении каких-либо «просроченных» максимумов (когда окно скользит мимо них) будет продвигать голову на один шаг.

Это немного неуклюжим, но вот некоторые рабочий код для иллюстрации:

#include <vector> 
#include <iostream> 

int main() 
{ 
    const int window_size = 4; 
    std::vector<int> vals = { 3, 7, 20, 6, 12, 2, 0, 99, 5, 16 }; 
    std::vector<int> maximums(window_size); 
    int mhead = 0, mtail = 0; 

    for(int i = 1; i < vals.size(); i ++) 
    { 
     // Clean out expired maximum. 
     if(maximums[mhead] + window_size <= i) 
     { 
      int next_mhead = (mhead + 1) % window_size; 
      if(mtail == mhead) mtail = next_mhead; 
      mhead = next_mhead; 
     } 

     if(vals[i] >= vals[ maximums[mtail] ]) 
     { 
      // Replace and bubble up a new maximum value. 
      maximums[mtail] = i; 
      while(mhead != mtail && vals[ maximums[mtail] ] >= vals[ maximums[(mtail+window_size-1)%window_size] ]) 
      { 
       int prev_mtail = (mtail + window_size - 1) % window_size; 
       maximums[prev_mtail] = maximums[mtail]; 
       mtail = prev_mtail; 
      } 
     } 
     else 
     { 
      // Add a new non-maximum. 
      mtail = (mtail + 1) % window_size; 
      maximums[mtail] = i; 
     } 

     // Output current maximum. 
     if(i >= window_size - 1) 
     { 
      std::cout << vals[ maximums[mhead] ] << " "; 
     } 
    } 

    std::cout << std::endl; 
    return 0; 
} 

Теперь сложность времени ...

Лучший случай О (п), что произойдет, если все ваши данные сортируются (либо по возрастанию, либо по убыванию).

Худший случай, я считаю, является O (2n). Единственный способ потребовать дополнительных операций на одной итерации, если у вас уже есть k шагов линейной сложности (так что кольцевой буфер заполнен). И в таком случае кольцевой буфер будет пустым для следующего шага. Так как мы можем заполнить и опорожнить кольцевой буфер только п/к раз, эти случайные к операции выходят на k.n/к или просто н.

Вы должны быть в состоянии показать, что даже постоянное частичное опорожнение кольцевого буфера приведет к такой же сложности.

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