Любая идея, как преобразовать этот O (n^2) алгоритм в O (n)

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

Думаю, я понимаю ваши требования .... Я собираюсь повторить проблему:

Учитывая : размер скользящего буфера K и массив данных размером N> K, индексы от 0 до N-1.

Вычислить : подсчитать количество точек j, таких как K <= j

Это может быть выполнено следующим образом:

1. Сортировка точек {данные [0], данные [1], ... данные [K-1]}, используя структуру данных, которая имеет не более O (log N) стоимость за вставку / удаление.

2. Инициализировать счетчик R равным 0, инициализировать j равным K.

3. Проверить отсортированный массив, чтобы увидеть, является ли самая низкая точка <= data [j] * 0.95; если да, увеличьте R.

4. Удалите данные [j-K] из отсортированного массива и вставьте данные [j] в отсортированный массив.

5. Приращение j

6. Если j

Ключевым моментом здесь является выбор правильной структуры данных. Я почти уверен, что двоичное дерево подойдет. Если инкрементная стоимость вставки равна O (log N), тогда ваше общее время выполнения будет O (N log N).

Я не думаю, что это возможно сделать за O (n), потому что, решив его с помощью O (n), вы можете отсортировать его с помощью O (n), а это невозможно. (минимум, для сортировки O (nlogn)).

РЕДАКТИРОВАТЬ - свести сортировку к этой проблеме

Предположим, для каждой точки можно определить, сколько точек в прошлом имело значение меньше x% (здесь x равно 5, но x также может быть 0, тогда счет будет любым меньшие точки в прошлом).

Теперь - предположим, вы хотите отсортировать массив из n элементов.
Если вы можете получить количество меньших точек в прошлом для всех элементов в O (n), если точка a имеет большее значение, чем точка b , количество точек a также будет больше, чем счетчик для точки b (поскольку массив круглый). Таким образом, эта проблема фактически дает функцию от значений до счетчика, которая сохраняет порядок.
Теперь - новые значения связаны между o и n, и их можно отсортировать по времени n.

Поправьте меня, если я ошибаюсь (возможно, я вообще не понял проблему).

Вы можете поддерживать массив buffArray для элементов numberOfDataPointsInPast , который будет содержать текущие элементы «окна», отсортированные в порядке возрастания.

Для каждой итерации:

• Проверить, меньше ли текущий элемент, чем 0.95 * buffArray [0] , и выполнить необходимые действия, если это так.
• Удалить элемент, который выходит из «окна» (т. Е. i + numberOfDataPointsInPast ’th) из buffArray .
• Добавить новый элемент (то есть i ’th) в buffArray , сохраняя порядок сортировки.

Это не O (N), как я понимаю, но определенно более эффективно, чем O (N ^ 2), поскольку добавление и удаление элементов в / из отсортированного массива составляет O (log N). Я подозреваю, что конечная эффективность равна O (N log (W)), где W - numberOfDataPointsInPast .

РЕДАКТИРОВАТЬ:

Поразмыслив над этим, можно увидеть простой алгоритм времени O (n) без необходимости в RMQ или дереве (см. Предыдущую часть моего ответа ниже).

Учитывая массив A [1 ... n] и ширину окна W, вам нужно найти минимум A [i, ... i + W] для данного i.

Для этого вы делаете следующее.

Разделить A [1 ... n] на смежные блоки размера W-1. B1, B2, ... B (W-1).

Для каждого блока B сохраните еще два блока с именами BStart и BEnd.

BStart [i] = минимум B 1 , B [2], ..., B [i].

BEnd [i] = минимум B [W-1], B [W-2], ..., B [W-i].

Это можно сделать за O (W) времени для каждого блока, то есть всего за O (n) времени.

Теперь, когда задано i, подмассив A [i ... i + W] будет охватывать два последовательных блока, скажем, B1 и B2.

Найдите минимум от i до конца блока B1 и от начала блока B2 до i + w, используя B1End и B2Start соответственно.

Это время O (1), итого O (n).

Для кольцевого массива C [1 .... n] все, что вам нужно сделать, это выполнить описанное выше на

A [1 .... 2n], который в основном представляет собой две копии C, соединенные вместе, т. Е. A [1 ... n] = C [1 ... n] и A [n + 1 ... 2n] = C [1 ... n]

Предыдущая запись.

Хорошо. Предполагая, что на этот раз я правильно понял ваш вопрос ...

Это возможно за O (n) время и O (n) пространство.

Фактически, можно изменить размер окна на любое число, которое вам нравится, сделать его другим для разных элементов, и при этом оно будет работать!

Учитывая массив A [1 ... n], он может быть предварительно обработан за время O (n) и пространство O (n), чтобы ответить на запросы вида: Какова позиция минимального элемента в подмассив A [i ...j]? в константе времени!

Это называется проблемой Минимальный запрос диапазона .

Итак, теоретически это можно сделать за O (n) раз.

Простое использование дерева даст вам время O (nlogW), где W - размер окна и, вероятно, на практике будет работать намного лучше, чем RMQ, поскольку я ожидаю, что скрытые константы могут ухудшить RMQ.

Вы можете использовать дерево следующим образом.

Начните в обратном направлении и вставьте элементы W. Найдите минимум и положите в стопку. Теперь удалите первый элемент и вставьте (W + 1) -й элемент. Найдите минимум, протолкните стек.

Продолжайте так. Общее время обработки составит O (nlogW).

В конце у вас есть стопка минимумов, которую вы можете просто выскакивать, пока вы проходите по массиву во второй раз, на этот раз в правильном порядке, ища цель 0,95 *.

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

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

По мере добавления новых точек диапазон точек данных может увеличиваться только за верхнюю или нижнюю границу. По мере того, как нижняя граница уменьшается, все, что необходимо, - это удерживать нижнюю границу. Любые новые точки, превышающие нижнюю границу / 0,95, будут приемлемы (поскольку нижняя граница всегда в прошлом):

const int numberOfDataPointsInPast = 1000; 
int numberOfDataPoints = 0; 
double lb = NAN;
for (int i = 0; i < numberOfDataPointsInPast; i++) 
{ 
    if ( lb == NAN || data[i] < lb ) {
        lb = data[i];
    }
    if ( data[i] >= lb / 0.95 ) {
        numberOfDataPoints++
    }
} 

У вас есть два варианта:

1. Сортировать - O (n log n)

2. Алгоритм медианы медианы

Вы могли бы отсортировать их по первому numberOfDataPointsInPast в прошлом, который равен n log (n). Затем выполните двоичный поиск, log (n), найдите самую низкую точку данных, которая проходит проверку 5%. Это скажет вам, сколько точек из numberOfDataPointsInPast пройдет тест за n log (n) раз, как я полагаю.

Попробуйте следующее:

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

На каждом этапе прохождения через буфер определяйте, меньше ли текущее значение или равно значению, на которое указывает min1 или min2, если да, обновите min1 или min2, чтобы указать на текущее местоположение. В противном случае, если с помощью арифметики указателя значение min1 или min2 составляет 1500 мест в буфере, вам необходимо определить, какое это из них, и перенастроить min1 или min2 соответственно, то есть min1 указывает на min2, а min2 устанавливается на точку текущее местоположение, или min2 просто устанавливается так, чтобы указывать на текущее местоположение.

Будет ли значение, на которое указывает min1 или min2, меньше 15% от текущего значения, может быть определено простым сравнением ...