Sliding window statistics calculation complexity

The following C++ code takes a sequence of n elements, a₁, a₂, …, a_n, and outputs a sequence of n – k + 1 elements. The i-th output element is a maximal element in the subsequence a_i, a_{i + 1}, …, a_{i + k – 1}. The runtime complexity of the code is O(n).

template <typename T>
void insert(std::list< std::pair<T,unsigned int> > &l, T v)
{
    unsigned int sp = 0;
    while (!l.empty() && l.back().first < v)
    {
        sp++;
        l.pop_back();
    }
    l.push_back(std::pair<T,unsigned int>(v,sp));
}

template <typename T>
void advance(std::list< std::pair<T,unsigned int> > &l)
{
    if (l.front().second > 0)
        l.front().second--;
    else
        l.pop_front();
}

template <typename T>
void max_in_window(T const *in, T *out, size_t n, size_t k)
{
    std::list< std::pair<T,unsigned int> > l;
    unsigned int i;
    for (i = 0; i < k - 1 && i < n; i++)
        insert(l,in[i]);

    for (; i < n; i++)
    {
        insert(l,in[i]);
        out[0] = l.front().first;
        out++;
        advance(l);
    }
}

Interestingly, an algorithm for the median in a sliding window will have runtime of at least O(n log k), since such an algorithm can be used to sort O(n / k) sequences of length O(k) each:

Let a₁, a₂, …, a_n be a sequence of numbers in a known interval, say (0, 1). Create a sequence of length 3n – 2 by padding the sequence with a prefix of (n – 1) 0‘s and a suffix of (n – 1) 1‘s. Now execute the sliding window median algorithm with the padded sequence as input, and with k = 2n – 1.

The i-th output element will be the median of a sequence that is made of the entire sequence a₁, a₂, …, a_n, n – i zeros, and i – 1 ones. That median is a_(i), the i-th smallest elements of the sequence a₁, a₂, …, a_n. Thus, the output of the algorithm will be the sorted sequence a₍₁₎, a₍₂₎, …, a_(n).

Advertisement