Литература / AiSD-Tema-Analiz-algoritmov
.pdfАНАЛИЗ АЛГОРИТМОВ
Сравнительные оценки алгоритмов
При использовании алгоритмов для решения практических задач
проблема рационального выбора алгоритма.
Решение проблемы выбора связано с построением системы сравнительных оценок, которая в свою очередь существенно зависит от формальной модели алгоритма.
Для оперирования с формальной моделью алгоритма рассматривают абстрактную машину, включающую:
процессор, поддерживающий адресную память набор элементарных операций соотнесенных с языком высокого уровня.
Допущения:
каждая команда выполняется не более чем за фиксированное время; исходные данные алгоритма представляются N машинными словами по α битов каждое.
На входе алгоритма
Nα = N*α бит информации
Программа, реализующая алгоритм состоит из М машинных инструкций по β битов
Мβ = М*β бит информации.
Дополнительные ресурсы абстрактной машины на реализацию алгоритма:
Sd – память для хранения промежуточных результатов;
Sγ – память для организации вычислительного процесса (память, необходимая для реализации рекурсивных вызовов и возвратов).
При решении конкретной задачи, заданной N+М+Sd+Sy словами памяти алгоритм выполняет конечное количество «элементарных» операций абстрактной машины.
В связи с этим вводится определение:
Под трудоѐмкостью алгоритма Fa(n)
для данного конкретного входа для решения конкретной проблемы (задачи) в данной формальной системе
понимается количество «элементарных» операций (n) совершаемых алгоритмом.
Комплексный анализ алгоритма может быть выполнен на основе комплексной оценки ресурсов формальной машины, требуемых алгоритмом для решения конкретных задач.
A c1Fa (n) c2 N c3M c4Sd c5Sy
Для различных областей применения веса ресурсов ci будут различны.
Классификация алгоритмов по виду функции трудоёмкости
1.Количественно-зависимые по трудоемкости алгоритмы
Это алгоритмы, функция трудоемкости которых зависит только от размерности конкретного входа, и не зависит от конкретных значений:
Fa(n), n=f(N)
Пример:
• алгоритмы для стандартных операций с массивами и матрицами – умножение матриц, умножение матрицы на вектор и т.д.
2. Параметрически-зависимые по трудоемкости алгоритмы
Это алгоритмы, трудоемкость которых определяется конкретными значениями обрабатываемых слов памяти:
Fa(n), n=f(р1…,рi)
У таких алгоритмов на входе два числовых значения – аргумент функции и точность.
Пример:
• алгоритмы вычисления стандартных функций с заданной точностью путем вычисления соответствующих степенных рядов.
3. Количественно-параметрические по трудоемкости алгоритмы
В большинстве практических случаев функция трудоемкости зависит от количества данных на входе, значений входных данных
Fa(n), n=f(N, р1…, рi)
Пример:
• алгоритмы |
численных |
методов, |
в |
которых |
существует |
параметрически зависимый цикл по точности и цикл количественнозависимый по размерности.
Среди параметрически-зависимых алгоритмов выделяют группу алгоритмов для которой количество операций зависит от порядка расположения исходных объектов.
Пример:
•алгоритмы сортировки,
•алгоритмы поиска минимума/максимума в массиве.
Асимптотический анализ функций
Цель анализа трудоёмкости алгоритмов – нахождение оптимального алгоритма для решения данной задачи.
Критерий оптимальности – количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма.
Tзадачи
n
Sтех |
Sинт |
|
|
|
|
SИ |
|
|
|
t |
||
Э |
|
|
|
|
|
1, |
SИ min |
|||
|
SИ |
SТ |
||||||||
|
|
|
|
|
|
|
||||
Эm |
|
|
|
SИ |
|
|
mSИ |
1 |
||
|
SИ |
SТ |
|
|
||||||
|
|
|
|
/ m mSИ SТ |
|
|||||
Цель асимптотического анализа - сравнение затрат ресурсов системы различными алгоритмами, предназначенными для решения одной и той же задачи при больших объемах входных данных.
Используемая в асимптотическом анализе оценка функции трудоёмкости, называется сложностью алгоритма и позволяет определить, как быстро растет трудоёмкость алгоритма с увеличением объема данных.
В |
асимптотическом |
анализе |
используются |
обозначения |
позволяющие показать скорость роста функции :
1.Оценка (тетта)
2.Оценка О (О большое)
3.Оценка (Омега)
1. Оценка (тетта)
Пусть f(n) и g(n) – положительные функции положительного аргумента, n >= 1 , тогда:
Обычно говорят, что при этом функция g(n) является асимптотически точной оценкой функции f(n), т.к. по определению функция f(n) не отличается от функции g(n) с точностью до постоянного множителя.
Примеры:
1) f(n)=4 n2+nln(n)+174 f(n)= (n2); 2) f(n)= (1) – запись означает, что f(n)
или равна константе, не равной нулю, или f(n) ограничена константой на :
f(n) = 7+1/n = (1).
Пример
Пример
Неравенства выполняются если выбрать:
n>=7 с1<=1/14 n→∞ с2>=1/2
Таким образом
(2/7)n2<=n2/2-3n<= (1/2)n2
с1 n2<=a n2 +bn+c<= c2 n2 , a,b,c>0
a n2 <= a n2 +bn+c<= (a+b+c) n2
Для произвольных a,b,c
C1=min{a, a+b+c}, C2=max{a, a+b+c}
2. Оценка О (О большое)
Запись O(g(n)) обозначает класс таких функций которые растут не быстрее, чем функция g(n) с точностью до постоянного множителя, поэтому иногда говорят, что g(n) мажорирует функцию f(n).
Например, для всех функций:
f(n)=1/n, f(n)= 12, f(n)=3n+17, f(n)=nLn(n), f(n)=6n2 +24n+77
будет справедлива оценка О(n2)