Асимптотический порядок роста

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

Алгоритмы будут в основном выражаться на псевдокоде наподобие того, ко- торый использовался в алгоритме Гейла-Шепли. Время от времени появляется необходимость в более формальных средствах, но для большинства целей такого стиля определения алгоритмов вполне достаточно. Вычисляя граничную оценку для времени выполнения алгоритма, мы будем подсчитывать количество выпол- няемых шагов псевдокода; в этом контексте один шаг будет состоять из присва- ивания значения переменной, поиска элемента в массиве, перехода по указателю или выполнения арифметической операции с целым числом фиксированного размера.

Если нам потребуется что-то сказать о времени выполнения алгоритма с вход- ными данными размера n, можно попытаться сделать предельно конкретное за- явление, например: «Для любых входных данных размера n этот алгоритм будет выполнен не более чем за 1,62n2 + 3,5n + 8 шагов». В некоторых контекстах такое утверждение будет представлять интерес, но в общем случае ему присущ ряд недостатков. Во-первых, получение такой точной оценки может потребовать зна- чительных усилий, а настолько подробная оценка все равно не нужна. Во-вторых, так как нашей конечной целью является идентификация широких классов алго- ритмов, обладающих сходным поведением, нам хотелось бы различать время

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

И наконец, излишне точные утверждения о количестве шагов алгоритма часто оказываются (в некоторой степени) бессмысленными. Как говорилось ранее, мы обычно под- считываем шаги в описании алгоритма на псевдокоде, напоминающем язык про- граммирования высокого уровня. Каждый из этих шагов обычно преобразуется в некоторое фиксированное число примитивных шагов при компиляции програм- мы в промежуточное представление, которые затем преобразуются в еще большее количество шагов в зависимости от конкретной архитектуры, используемой для проведения вычислений. Итак, максимум, что можно сказать с уверенностью, — что при рассмотрении задачи на разных уровнях вычислительной абстракции понятие «шаг» может увеличиваться или уменьшаться с постоянным коэффици- ентом. Например, если для выполнения одной операции языка высокого уровня требуется 25 низкоуровневых машинных команд, то наш алгоритм, выполняемый за максимум 1,62n2 + 3,5n + 8 шагов, может рассматриваться как выполняемый за 40,5п2 + 87,5п + 200 шагов при анализе на уровне, приближенном к уровню физического оборудования.

O, Ω и Θ

По всем указанным причинам мы хотим выразить скорость роста времени выпол- нения и других функций способом, из которого исключены постоянные факторы и составляющие низших порядков. Иначе говоря, нам хотелось бы взять время выполнения типа приведенного выше, 1,62n2 + 3,5n + 8, и сказать, что оно растет со скоростью n2. А теперь посмотрим, как же решается эта задача.

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

Еще по теме Асимптотический порядок роста:

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