Порядок роста.
Классика алгоритмизации
Для всех значений n, лежащих справа от n0, функция больше или равна функции, но не превосходит функцию. Другими словами, для всех функция равна функции с точностью до постоянного множителя. Говорят, что функция является асимптотически точной оценкой функции. Обозначение и (можно строго определить, сделав таким образом понятие порядка роста более формализованным. Мы говорим, что, имеет порядок… Читать ещё >
Порядок роста. Классика алгоритмизации (реферат, курсовая, диплом, контрольная)
Теперь введем ещё одно абстрактное понятие, упрощающее анализ алгоритма. Это порядок роста интересующего нас времени работы.
Допустим, что время работы описывается формулой где a, b и c — некоторые константы. Во внимание будет приниматься только главный член формулы (), поскольку при больших значениях n членами меньшего порядка можно пренебречь. Кроме того, постоянный множитель при главном члене будет также будет игнорироваться, так как для оценки вычислительной эффективности со входными данными большого объема они менее важны, чем порядок роста. Таким образом, время работы алгоритма равно и ((произносится «тета от n в квадрате»).
Обычно один алгоритм рассматривается как более эффективный по сравнению с другим, если время его работы в наихудшем случае имеет более низкий порядок роста.
Асимптотические обозначения
Обозначение и (можно строго определить, сделав таким образом понятие порядка роста более формализованным. Мы говорим, что, имеет порядок роста и (), если существуют положительные постоянные и независимые от n, такие, что.
для всякого достаточно большого n.
На рисунке показано интуитивное изображение функций, таких, что.
).
Для всех значений n, лежащих справа от n0, функция больше или равна функции, но не превосходит функцию. Другими словами, для всех функция равна функции с точностью до постоянного множителя. Говорят, что функция является асимптотически точной оценкой функции.
Интуитивно понятно, что при асимптотически точной оценке положительных функций, слагаемыми низших порядков в них можно пренебречь, поскольку при больших n они становятся несущественными. При больших n даже небольшой доли старшего слагаемого достаточно для того, чтобы превзойти слагаемые низших порядков.
Вобозначениях функция асимптотически ограничивается сверху и снизу. Если же достаточно определить только асимптотическую верхнюю границу, используются O-обозначения. Для данной функции обозначение О (означает, что существуют положительные постоянные c и, такие, что.
для всех .
O-обозначения применяются, когда нужно указать верхнюю границу функции с точностью до постоянного множителя.