Однопроходный алгоритм - One-pass algorithm - Wikipedia

В вычислениях однопроходный алгоритм это алгоритм потоковой передачи который считывает входные данные ровно один раз по порядку без неограниченных буферизация. Однопроходный алгоритм обычно требует О(п) (видеть Обозначение 'большой O' ) время и меньше О(п) хранилище (обычно О(1)), где п размер ввода.

В основном однопроходный алгоритм работает следующим образом:

  1. Описания объектов обрабатываются последовательно.
  2. Первый объект становится представителем кластера первого кластера.
  3. Каждый последующий объект сопоставляется со всеми представителями кластера, существующими во время его обработки.
  4. Данный объект назначается одному кластеру (или нескольким, если допускается перекрытие) в соответствии с некоторым условием функции сопоставления.
  5. Когда объект назначается кластеру, представитель этого кластера пересчитывается.
  6. Если объект не проходит определенный тест, он становится представителем нового кластера, ничего не произошло

Примеры задач, решаемых с помощью однопроходных алгоритмов

Учитывая любой список в качестве входных данных:

  • Подсчитайте количество элементов.

Учитывая список чисел:

Учитывая список символов из алфавита k символы, указанные заранее.

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

Примеры задач, не решаемых с помощью однопроходных алгоритмов

Учитывая любой список в качестве входных данных:

  • Найди пth элемент с конца (или сообщить, что в списке меньше, чем п элементы).
  • Найдите средний элемент списка.

Учитывая список чисел:

  • Найди медиана.
  • Найди режимы (Это не то же самое, что найти наиболее часто встречающийся символ из ограниченного алфавита).
  • Отсортируйте список.