Определение O-большого

Вычислительная сложность алгоритмов

Для оценки эффективности алгоритма наиболее важными показателями являются:

- время выполнения алгоритма,
- требуемый объем оперативной памяти.

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

Упрощения для оценки времени выполнения алгоритмов

В работах Д.Кнута был предложен следующий подход для анализа времени выполнения алгоритмов: общее время складывается из величин стоимость * частота для каждой базовой операции. В число базовых операций могут входить сложение, умножение, деление, получение элемента по индексу из массива, сравнение целых чисел и т.д. Нетрудно заметить, что в этом случае вычисление оценки времени выполнения алгоритма довольно-таки утомительно. Поэтому А.Тьюринг сказал, что удобно пользоваться даже грубыми приближениями оценок времени выполнения алгоритмов: можно присвоить веса различным операциям в зависимости от их частоты появления во время работы алгоритма и учитывать только те операции, которым соответствуют наибольшие веса. Например, при перемножении матриц следует учитывать только такие операции, как умножение и запись чисел, т.к. это самые частые операции. Рассмотрение только наиболее часто встречающихся операций - первое упрощение, предложенное для приблизительного расчета времени выполнения алгоритмов.

Второе упрощение заключается в отбрасывании термов (т.е. слагаемых) более низкого порядка, которые привносят небольшой вклад в итоговую оценку времени выполнения алгоритма. Например (далее число N характеризует размер входных данных),

1/6 N 3 +20 N +16∼1/6 N 3,

3 N 4− N 2 +12 N ∼3 N 4.

Далее используют О-нотацию:

вместо 1/6 N 3 пишут "этот алгоритм имеет сложность O (N 3), вместо 3 N 4 пишут "этот алгоритм имеет сложность O (N 4)".

Определение O-большого

Говорят, что f является "O большим" от g при x → x 0, если существует такая константа C >0, что для всех x из окрестности точки x 0 имеет место неравенство | f (x)|≤ C | g (x)|. Ниже приведена иллюстрация определения (ось x - размер входных данных, ось y - время выполнения алгоритма). Мы видим, что начиная с некоторой точки при стремлении размера входных данных к ∝ f (n) растет медленнее, чем g (n) и вообще g (n) как бы ограничивает ее сверху.

Примеры. 1= O (N), N = O (N 2).

Наряду с оценками вида O (N) используется оценка Ω(N) (омега большое). Она обозначает нижнюю оценку роста функции. Например, пусть количество операций алгоритма описывает функция f (N)=Ω(N 2). Это значит, что даже в самом удачном случае будет произведено не менее N 2 действий. В то время как оценка O (N 3) гарантирует, что в худшем случае будет не более чем порядка N 3 действий. Также используется оценка Θ(N) (тэта), которая является верхней и нижней асимптотической оценкой, когда O (N) и Ω(N) совпадают. Итак, O (N) - приближенная оценка алгоритма на худших входных данных, Ω(N) - на лучших входных данных, Θ(N) - сокращенная запись одинаковых O (N) и Ω(N).

Дата добавления: 2015-07-11