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

Я столкнулся с проблемой, когда я хочу написать алгоритм, который может возвращать максимальный элемент каждого последовательного подмассива из 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), или, если это невозможно, О(nlog(n)). Кто-нибудь знает, есть ли более быстрый способ сделать это, и если да, то как?


c++ arrays max algorithm sub-array
person Rich    schedule 15.02.2016    source источник
comment
* последовательные подмассивы. Извините, я забыл упомянуть об этом   -  person Rich    schedule 15.02.2016
comment
Я не думаю, что вы можете сделать это более эффективным с точки зрения сложности выполнения, если у вас нет какой-либо формы эвристики. Если бы эти структуры данных были деревьями, вы могли бы использовать расширенные алгоритмы усечения, такие как сокращение альфа-бета. Так что, к сожалению, я думаю, что вы можете сделать его более элегантным только с помощью рекурсии, и вы застряли с O(n^2)   -  person Aiden Strydom    schedule 15.02.2016
comment
Разве вы не имеете в виду сложность O (nk) вместо O (n ^ 2)? Кажется, что наивный подход заключается в сканировании k элементов в каждом подмассиве и выборе наибольшего из них.   -  person josliber♦    schedule 15.02.2016
comment
Возможный дубликат Может ли мин/макс движущегося окна достичь в O( Н)?   -  person MBo    schedule 15.02.2016

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

Когда вы перемещаете окно (размер k) по своим данным, вы помещаете текущий индекс в 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(n), что происходит, если все ваши данные отсортированы (по возрастанию или по убыванию).

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

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

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

person paddy    schedule 15.02.2016
comment
Вероятно, мне следовало упомянуть, что, как и во многих других алгоритмах, наивный подход может быть более подходящим для малых значений k, но по мере увеличения k преимущества линейного время алгоритм начинает показывать. - person paddy; 15.02.2016