Я считаю, что ответ один не существует, и я постараюсь изложить доказательство того, почему это так.
Рассмотрим «бесполезный» онлайн-алгоритм, который определяется двумя критериями:
- Он должен иметь фиксированные требования к памяти во время обработки.
- Каждое обновление должно занимать фиксированное количество времени.
Это строже, чем буквальное определение последовательного / инкрементного / оперативного алгоритма, который на самом деле просто требует, чтобы данные передавались по одной порции за раз. Однако учтите, что если бы 1) или 2) были неверными, то после обработки достаточно большого количества элементов требуемая память или время, необходимое для запуска алгоритма, в конечном итоге стали бы невозможными. Обычно одна из причин использования онлайн-алгоритмов состоит в том, что они могут использоваться непрерывно, не опасаясь, что производительность будет постепенно ухудшаться. Также обратите внимание, что существуют онлайн-алгоритмы для вычисления среднего значения и дисперсии, которые удовлетворяют как 1, так и 2, и я думаю, что мы стремимся к этому.
Теперь проблема поставлена. Во время обработки среднее значение будет меняться с каждым битом новых данных. Это, в свою очередь, означает, что набор наблюдений, которые падают ниже среднего, изменится. Когда это происходит, нам нужно отрегулировать нашу текущую полуверсию в соответствии с набором «дельта», определенным как элементы, которые не находятся в объединении между набором элементов ниже старого среднего и набором элементов ниже нового среднего. Нам придется вычислять эту дельту в процессе корректировки старой вариабельности на новую вариабельность при наличии новых данных.
Теперь давайте рассмотрим сложность вычисления этой дельты множества. Нам нужно будет найти все элементы, которые попадают между старым и новым средним. Мы всегда будем отслеживать старое среднее значение, в то время как новое среднее значение может быть вычислено постепенно в фиксированное время, поэтому они не представляют проблемы. Однако, чтобы вычислить саму дельту, нет другого способа сделать это, кроме как требовать, чтобы мы отслеживали все предыдущие элементы в нашем наборе. Это немедленно нарушает состояние памяти онлайн-алгоритма. Во-вторых, даже если мы сохраним предыдущие элементы в нашем наборе, лучшая скорость, которую мы можем достичь, чтобы найти те, которые находятся между старым средним и новым средним, - это O (log (количество элементов)), что хуже, чем фиксированное. Таким образом, в конечном итоге, при наличии достаточного количества элементов, онлайновый алгоритм не только потребует больше памяти, чем у нас, но также потребует больше времени.