Т2. Оценка сложности. Лекция 4 Оценка сложности алгоритма классификация
 Скачать 21.72 Kb.
|
|
Лекция 4 Оценка сложности алгоритма: классификация. Оценка сложности алгоритма: классы алгоритмов, неразрешимые задачи Цель занятия: Изучить понятие сложности алгоритмов, научиться классифицировать алгоритмы по сложности и определять их сложность Вопросы: 1. Оценки сложности 2. Временная оценка 3. Оценка пространственной (емкостной) сложности Оценки сложности Важнейшей характеристикой алгоритма и соответствующей ему программы является их сложность, которая может оцениваться: a) временем решения задачи (трудоемкостью алгоритма); b) требуемой емкостью памяти. Наиболее часто сложность алгоритма оценивают по порядку величины (порядка n, n2 и т.д.). Этот метод применим как к временной, так и к емкостной сложности. 1. Временная оценка (оценка порядка) Эта оценка считается сомой важной. Наиболее точно она определяется числом машинных команд, выполняемых при реализации алгоритма. Для программ на языках высокого уровня обычно используют следующий набор «элементарных» операций, характерных для этих языков. 1. Простое присваивание: а b, будем считать ее сложность, равной 1; 2. Одномерная индексация a[i] : (адрес (a)+i*длина элемента), будем считать ее сложность, равной 2; 3. Арифметические операции: (*, /, -, +), будем считать их сложность, равной 1; 4. Операции сравнения: a < b, будем считать их сложность, равной 1; 5. Логические операции {or - |, and - &&, not - !}, будем считать их сложность, равной 1; С их помощью трудоемкость основных алгоритмических конструкций можно представить так. 1. Линейная конструкция из k последовательных блоков Трудоемкость конструкции есть сумма трудоемкостей блоков, следующих друг за другом. Θ =f1+f2+…+fk, где fk – трудоемкость k-го блока. 2. Конструкция «Ветвление» If (Условие) then Операторы else Операторы. Общая трудоемкость конструкции «Ветвление» требует анализа вероятности выполнения операторов, стоящих после «Then» (р) и «Else» (1-р) и определяется как: Θ = fthenp + felse(1-p),  где fthen и felse – трудоемкости соответствующих ветвей.3. Конструкция «Цикл» for (i=1; i<= n; i++) { Тело цикла } После сведения этой конструкции к элементарным операциям ее трудоемкость определяется как: Θ =1+3*n+n* fцикла, где fцикла – сложность тела цикла, n – число его повторений, 3* n – трудоемкость изменения параметра и проверки условия выполнения цикла. Сложность линейного участка и ветвления, как правило, не зависит от объема данных и считается равной некоторой константе. При этом алгоритмы, содержащие циклы и рекурсии, являются более сложными. Величина Θ возрастает с увеличением вложенности циклов, а также при многократном вызове методов обработки данных (процедур). Рассмотрим примеры анализа простых алгоритмов. Пример 1. Задача суммирования элементов квадратной матрицы размерностью n* n. SumM (A, n; Sum) Sum <-- 0 For i <-- 1 to n For j <-- 1 to n Sum <-- Sum + A[i,j] end for Return (Sum) End Алгоритм выполняет одинаковое количество операций при фиксированном значении n и, следовательно, является количественно-зависимым. Применение методики анализа конструкции «Цикл » дает: Θ (n)=1+ fцикла по i = 1 + 1+ 3*n + n * fцикла по j =1 + 1+ 3*n + n *(1+ 3*n + n *(2 + 2 + 1 + 1)) = 2 + 3n + n *(1 + 3n + 6 n) = 9n2+4 n +2. (1.1) 1.1. Общий случай определения временной сложности Оценку сложности алгоритмов выполняют с использованием аппарата математического асимптотического анализа и выведения асимптотической оценки сложности. Выражение (1.1) представляет собой точную оценку сложности алгоритмов. В теории алгоритмов они являются семейством функций, дающих множество значений, в том числе верхнее и нижнее. Основным свойством Θ(n) является то, что при увеличении размерности входных данных n время выполнения алгоритма возрастает с той же скоростью, что и функция f(n). Ее еще называют асимптотической. Асимптотическая оценка сложности обозначается греческой буквой Θ (тета). f(n) = Θ(g(n)), если существуют c1, c2>0 и n0 такие, что c1*g(n)<=f(n)<=c2*g(n) , при n>n0. Функция g(n) является асимптотически точной оценкой сложности алгоритма - функции f(n). Приведенное неравенство называется асимптотическим, а само обозначение Θ символизирует множество функций, которые растут «так же быстро», как и функция g(n) – т.е. с точностью до некоторой константы c1 или c2. Как следует из приведенного неравенства, Θ представляет собой одновременно и верхнюю, и нижнюю оценки сложности. Не всегда имеется возможность получить выражение в общем виде, поэтому верхнюю и нижнюю оценки могут определять отдельно. Верхняя оценка сложности обозначается греческой буквой Ο (омикрон), и является множеством функций, которые растут не быстрее, чем g(n). f(n)= Ο(g(n)), если существует c>0 и n0 такие, что 0<=f(n)<=cg(n), при n>n0. Нижняя оценка сложности обозначается греческой буквой Ω (омега), и является множеством функций, которые растут не медленнее, чем g(n). f(n)= Ω(g(n)), если существует c>0 и n0 такие, что 0<=cg(n)<=f(n), при n>n0. Вообще, асимптотическая оценка существует только в том случае, если совпадают нижняя и верхняя оценки сложности алгоритма. В практике анализа алгоритмов чаще всего используют верхнюю оценку. Это вполне логично, поскольку наиболее важна оценка времени, за которое алгоритм гарантировано закончит работу, а не время, в пределах которого он точно не завершится. Таким образом, верхняя оценка сложности является оценкой порядка и пропорциональна максимальному элементу в формуле Θ(n) (см. (1.1)). Она легче вычисляется и дает предельное значение. Именно она получила наибольшее распространение. Обычно определение сложности алгоритма сводится к анализу a) Циклов; b) Вызовов методов и c) Вызовов рекурсий. Так, в примере 1 (нахождение суммы элементов квадратной матрицы) она определяется величиной O(n2), а в примере 2 (нахождение максимума в одномерном массиве) для всех случаев – O(n). Вообще для циклов вида: for (i=1; i<= n; i++) for (j=1; j<= n; j++) for (k=1; k<= n; k++) {Тело цикла} сложность равна O(n3), т.е. пропорциональна числу повторений самого внутреннего цикла. 1.2. Виды функций оценки сложности алгоритмов В общем случае, О-функции выражают относительное быстродействие алгоритма в зависимости от некоторой переменной или переменных. При этом используются три правила оценки сложности. 1. O(k*f) = O(f), 2. O(f*g) = O(f)*O(g), 3. O(f+g) = Max (O(f), O(g)). Здесь k обозначает константу, а f и g - функции. Первое правило означает, что постоянные множители не имеют значения для определения порядка сложности, например, O(2*n) = O(n). В соответствии со вторым порядок сложности произведения двух функций равен произведению их сложностей. Например, O((10*n)* n) = O(n)* O(n) = O(n2). На основании третьего правила порядок сложности суммы двух функций равен максимальному (доминирующему) значению из их сложностей. Например, O(n4 + n2) = O(n4). На практике применяются следующие виды О-функций: a) О(1) – константная сложность, для алгоритмов, сложность которых не зависит от размера данных. b) О(n) – линейная сложность, для одномерных массивов и циклов, которые выполняются n раз, c) О(n2), О(n3), … – полиномиальная сложность, для многомерных массивов и вложенных циклов, каждый из которых выполняется n раз, d) О(log(n)) – логарифмическая сложность, для программ, в которых большая задача делится на мелкие, которые решаются по-отдельности, e) О(2n) – экспоненциальная сложность, для очень сложных алгоритмов, использующих полный перебор или так называемый «метод грубой силы». Функции перечислены в порядке возрастания сложности. Чем выше в этом списке находится функция, тем быстрее будет выполняться алгоритм с такой оценкой. 1.3. Экспериментальный метод оценки трудоемкости (сложности) алгоритма Метод основан на измерении времени выполнения алгоритма на некотором наборе данных (тесте). При этом используются стандартные средства языка программирования, позволяющие определить системное время компьютера. Например, для среды java это могут быть методы System.CurrentTimeMillis (), позволяющий фиксировать время с точность до миллисекунд и System.nanoTime() – до наносекунд. Последний имеет ограничения и работает не на всех платформах. Для оценки трудоемкости некоторого алгоритма достаточно запомнить время перед его выполнением и зафиксировать в конце, например, с помощью следующего фрагмента: long start = System.nanoTime(); // Фрагмент программы, реализующий исследуемый алгоритм long end = System.nanoTime(); long traceTime = end-start; traceTime даст искомое время. Быстродействие современных процессоров с тактовой частотой в несколько Гигагерц имеет порядок нескольких десятков миллиардов операций в секунду. При этом время выполнения простых алгоритмов может быть очень малым, а измерение его предлагаемым методом будет иметь большую погрешность. Для ее уменьшения можно зациклить выполнение исследуемого фрагмента (например, повторить его 1000 или 10 000 раз), а величину traceTime поделить на число повторений цикла. 2. Оценка пространственной (емкостной) сложности Такая оценка выполняется аналогично временной. При этом если для реализации алгоритма требуется дополнительная память для одной, двух или трех переменных, то емкостная сложность алгоритма будет константной, т.е. О(1). Такую сложность имеет, например, рассмотренный выше алгоритм поиска максимума. Если дополнительная память пропорциональна n, то пространственная сложность равна О(n) и т.д. Для всех рекурсивных алгоритмов, помимо временной, важно понятие емкостной сложности. При каждом вызове метод запрашивает небольшой объём памяти, но этот объем может значительно увеличиваться в процессе рекурсивных вызовов. Так, при вычислении факториала на первом этапе (разворачивания рекурсии) значения сомножителей помещаются в стек. Их количество равно n. При этом пространственная сложность алгоритма будет равна О(n). В других случаях эта характеристика может быть еще больше. Таким образом, всегда требуется анализ емкостной сложности рекурсивных процедур. Временная и емкостная сложность взаимосвязаны. Это обусловлено тем, что память современных ЭВМ имеет иерархическую структуру. При выполнении программы процессор, прежде всего, работает с данными, находящимися в быстрой кэш-памяти. Если массив имеет большую размерность, то он может не поместиться в кэше. При его обработке будут происходить кэш-промахи, которые сильно замедляют выполнение программы. Оценка временной сложности в таком случае должна осуществляться экспериментально. Контрольные вопросы: 1. Дайте определение оценке сложности алгоритмов 2. Как осуществляется временная оценка сложности алгоритмов? 3. Как осуществляется оценка пространственной (емкостной) сложности алгоритмов? |