Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. I ОФИЦИАЛЬНОЕ ОПРЕДЕЛЕНИЕ УГРОЗ НАЦИОНАЛЬНОЙ БЕЗОПАСНОСТИ РОССИИ
  2. I. ОБЛАСТЬ ПРИМЕНЕНИЯ, ОПРЕДЕЛЕНИЕ И ЦЕЛИ
  3. II. Определение для каждого процесса изменения внутренней энергии, температуры, энтальпии, энтропии, а также работы процесса и количества теплоты, участвующей в процессе.
  4. III. ОПРЕДЕЛЕНИЕ ОБЛАДАТЕЛЕЙ ПРИЗОВ
  5. IV. Определение массы груза, опломбирование транспортных средств и контейнеров
  6. p.2.1.2.1(c) Определение коэффициента объемного расширения жидкостей
  7. VI I Определение победителей и награждение.

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

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

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

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

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

 

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

 

Второе упрощение заключается в отбрасывании термов (т.е. слагаемых) более низкого порядка, которые привносят небольшой вклад в итоговую оценку времени выполнения алгоритма. Например (далее число 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 при xx 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; просмотров: 78 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Основные характеристики люминесцентных ламп| Оценки времени выполнения для разных алгоритмов

mybiblioteka.su - 2015-2024 год. (0.006 сек.)