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

Question

У меня есть следующий алгоритм, который сканирует большой круговой массив (данные). В определенной точке массива мне нужно взглянуть на прошлые значения (0 = самая новая точка данных, n = самая старая точка данных) и определить, было ли значение на 5% ниже текущего значения. В итоге я написал алгоритм O (n ^ 2), который работает нормально, но это не масштабируется.

        const int numberOfDataPointsInPast = 1000;
        int numberOfDataPoints = 0;
        for (int i = numberOfDataPointsInPast; i >= 0; i--)
        {
            double targetPoint = data[i] * 0.95;
            for (int j = i + numberOfDataPointsInPast; j > i; j--)
            {
                if (data[j] <= targetPoint)
                {
                    numberOfDataPoints++;
                    break;
                }
            }
        }

Есть идеи, как я мог бы преобразовать это в O (n) -алго? Спасибо!

Answer 1

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

Answer 2

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

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

Вычислить : Подсчитать количество точек j таких K <= j <N-1, и что множество {data [j-1], данные [j-2], данные [j-3], ... данные [jK]} содержат хотя бы одну точку со значением <= 0,95 * data [j]. </p>

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

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

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

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

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

5. Увеличение j

6. Если j

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

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

Answer 5

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

Подумав об этом, возможен простой алгоритм 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 [Wi].

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

Теперь с учетом i, подмассива[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) пробел для ответа на запросы вида: What is the position of a minimum element in the sub-array A[i...j]? в константа время!

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

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

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

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

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

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

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

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

Answer 6

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

Answer 7

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

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

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

Answer 8

Попробуйте это:

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

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

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

Answer 9

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

По мере добавления новых точек диапазон точек данных может только увеличивать верхнюю или нижнюю границу.Когда нижняя граница уменьшается, поддержание нижней границы - это все, что нужно.Любые новые точки, превышающие нижнюю границу / 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++
    }
}