Вычисление максимума

Вычисление максимума из n чисел может быть выполнено классическим «одно- проходным» методом. Допустим, числа поступают на вход в виде списка или массива. Числа av a2,... обрабатываются последовательно, с сохранением текущего максимума во время выполнения.
Каждое очередное число а. сравнивается с теку- щим максимумом, и если оно больше, текущий максимум заменяется значением ai.

При таком решении для каждого элемента выполняется постоянный объем работы, а общее время выполнения составляет O(n).

Иногда необходимость применения однопроходных алгоритмов объясняется ограничениями приложения: например, алгоритм, работающий на высокоско- ростном коммутаторе в Интернете, «видит» проходящий мимо него поток пакетов и может выполнять любые необходимые вычисления с проходящими пакетами. При этом для каждого пакета выполняется ограниченный объем вычислительной

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Вычисление максимума:

  1. 6. Желать надо по-максимуму.
  2. Зарубка на носу Для максимума здоровья
  3. 9 рекомендаций, как взять максимум из этой книги.
  4. 4. Извлеките максимум из новых возможностей - не печальтесь по поводу того, что осталось позади.
  5. Вычисление символических дирекций
  6. ВЫЧИСЛЕНИЕ СРОКА СТАБИЛЬНОСТИ БРАКА
  7. Вычисление ошибки выборки.
  8. Вычисление ошибки выборки.
  9. Вычисление ошибки выборки.
  10. Вычисление местного звездного времени
  11. Статья 676. Вычисление гарантийного срока
  12. Статья 860. Порядок вычисления гарантийного срока
  13. Вычисление ошибки репрезентативности для собственно случайной выборки.
  14. ЭФФЕКТ ПУРКИНЬЕ
  15. СТАНДАРТИЗОВАННОСТЬ
  16. Страшилка перед глазами
  17. ДЕЯТЕЛЬНОСТЬ РАССУДОЧНАЯ
  18. Расч?т положений планет