САОД Методы анализа (1016810), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Таким образом, будем различать временную T(n) и пространственную (её также называют ёмкостной) V(n) сложности алгоритма. При рассмотрении оценок сложности, будем использовать только временную сложность. Пространственная сложность оценивается аналогично.

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

1. временная сложность алгоритма программы;

2. качество скомпилированного кода исполняемой программы в силу различий в реализации отдельных операторов языка высокого уровня с учетом «оптимизации» компилятора под конкретный процессор;

3. внешние задержки, вызванные работой операционной системы, например, при реализации механизма многозадачности или других программ, работающих в «фоновом» режиме (например, антивирусы);

4. машинные инструкции, используемые для выполнения программы, которые ориентированы на аппаратные особенности архитектуры ЭВМ, например, параллельную обработку линейной последовательности данных.

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

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

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

Часто, временная сложность алгоритма зависит от количества входных данных. Обычно говорят, что временная сложность алгоритма имеет порядок T(n) от входных данных размера n. Точно определить величину T(n) на практике представляется довольно трудно. Поэтому прибегают к асимптотическим отношениям с использованием O-символики, которая дает приемлемую оценку времени выполнения алгоритма для не бесконечно больших и не бесконечно малых значений n. Она также позволяет ответить на вопросы наподобие: «во сколько раз быстрее будет работать реализация данного алгоритма на компьютере, быстродействие которого больше нашего, например, в 10 раз»? Казалось бы, ответ очевиден — в 10 раз. Однако, если O(n) = n(n + 1)/2, то это далеко не так. Или: «насколько дольше будет выполняться программа, если удвоить размер входных данных»? Ответ будет такой: приблизительно в четыре раза медленнее.

Когда используют обозначение «O()», имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n²), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов.

Например, если число тактов (действий), необходимое для работы алгоритма, выражается как 25n² – 10n*log n + 5n + 15, то это алгоритм, для которого T(n) имеет порядок O(n²). Фактически, из всех слагаемых оставляется только то, которое вносит наибольший вклад при больших n (в этом случае остальными слагаемыми можно пренебречь), и игнорируется коэффициент перед ним.

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

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

1. максимальную сложность T_max(n), или сложность наиболее неблагоприятного случая, когда алгоритм работает дольше всего;

2. среднюю сложность T_mid(n) – сложность алгоритма в среднем;

3. минимальную сложность T_min(n) – сложность в наиболее благоприятном случае, когда алгоритм справляется быстрее всего.

1.3Асимптотические обозначения

1.3.1Асимптотически точная оценка функции роста

Если для функции T(n) найдутся константы c₁ > 0 и c₂ > 0 и такое число n₀ > 0, что выполнится условие , то говорят что время выполнения алгоритма (программы) асимптотически точно соответствует функции n². Этот факт обозначается как , где n – длина входа алгоритма.

Определение 1. Вообще, если и положительно определенные функции, то запись означает, что найдутся константы c₁ > 0 и c₂ > 0 и такое n₀ > 0, что для всех .

(Запись « » читается как «эф от эн есть тэта от же от эн»).

Если , то говорят, что является асимптотически точной оценкой (asymptotically tight bound) для . На самом деле это отношение симметрично, если: , то .

Рис. 2. Иллюстрация к определению

Заметим, что есть обозначение факта некоторого соотношения между двумя функциями, поэтому, если установлено , а следовательно и , то это вовсе не означает, что .

Проиллюстрируем свойство симметрии функции . Можно показать, что . Согласно определению надо указать положительные константы с₁, с₂ и число n₀ так, чтобы неравенства

выполнялись для всех . Разделим все части неравенства на n²:

.

Видно, что для выполнения второго неравенства достаточно положить c₂ = 1/2. Первое будет выполнено, если (например) n₀ = 7 и c₁=1/14.

Покажем, что В самом деле, пусть найдутся такие c₂ и n₀, что для всех . Но тогда для всех , из чего следует что c₂ не может является константой, так как растет с увеличением n, что противоречит определению.

Упомянем важный частный случай использования -обозначений: , который обозначает ограниченную функцию, отделённую от нуля некоторый положительной константой при достаточно больших значениях аргумента.

Асимптотические обозначения часто употребляются внутри формул. Например, рекуррентное соотношение вида

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

Часто асимптотические обозначения употребляются не вполне формально, хотя их подразумеваемый смысл обычно ясен из контекста.

Типичный пример неформального использования асимптотических обозначений – цепочка равенств вида . Второе из этих равенств понимается при этом так: какова бы ни была функция в левой части, сумма есть .

Отыскивая асимптотически точную оценку для суммы, мы можем отбрасывать члены меньшего порядка, которые при больших n становятся малыми по сравнению с основным слагаемым. Заметим также, что коэффициент при старшем члене роли не играет (он может повлиять только на выбор констант с₁ и с₂). Например, рассмотрим квадратичную функцию , где a, b, c – некоторые константы и a > 0. Отбрасывая члены младших порядков и коэффициент при старшем члене, находим что Чтобы убедиться в этом формально, можно положить с₁ = a/4, c₂ = 7a/4 и . Вообще, для любого полинома p(n) степени d с положительным старшим коэффициентом имеем .

1.3.2 - и - обозначения

Вообще, запись включает в себя две оценки: верхнюю и нижнюю. Их можно разделить:

Определение 2. Пусть имеются функции и , которые принимают неотрицательные значения для достаточно больших значений аргумента. Говорят, что , если найдётся такая константа c > 0 и такое число n₀, что для всех (рис. 3а).

Определение 3. Говорят, что , если найдётся такая константа c > 0 и такое число n₀, что для всех (рис. 3б). Эти записи читаются так: «эф от эн есть о большое от же от эн», «эф от эн есть омега большая от же от эн».

Теорема 1. Для любых двух функций и свойство выполнено тогда и только тогда, когда и .

Замечание: Для любых двух функций и свойство и равносильны.

Характеристики

Список файлов книги