Презентация на тему: Анализ производительности алгоритмов

Реклама. Продолжение ниже
Анализ производительности алгоритмов
Литература
Литература
Понятие сложности алгоритмов
Как оценить эффективность алгоритма?
Пример
Пример
Обозначения сложности
Анализ производительности алгоритмов
Примеры
Сравнение среднего, худшего и лучшего случаев
Анализ производительности алгоритмов
1/12
Средняя оценка: 4.6/5 (всего оценок: 87)
Код скопирован в буфер обмена
Скачать (59 Кб)
Реклама. Продолжение ниже
1

Первый слайд презентации: Анализ производительности алгоритмов

Изображение слайда
1/1
2

Слайд 2: Литература

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: Изд. Дом Вильямс, 2000. — 960 с. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. – М.: Изд. Дом Вильямс, 2000. – 384с. Кнут Д. Искусство программирования, т.1 Основные алгоритмы, Изд. Дом Вильямс, 2000. – 384с.

Изображение слайда
1/1
3

Слайд 3: Литература

Левитин, А. Алгоритмы : введение в разработку и анализ. : Пер. с англ. — М. : Издательский дом "Вильяме", 2006. — 576 с. Дж. Макконнелл Основы современных алгоритмов. 2-е издание. М.: Техносфера, 2004. - 368с.

Изображение слайда
1/1
4

Слайд 4: Понятие сложности алгоритмов

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

Изображение слайда
1/1
5

Слайд 5: Как оценить эффективность алгоритма?

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

Изображение слайда
1/1
6

Слайд 6: Пример

А лгоритм вычисления значения многочлена степени n в заданной точке x. Алгоритм 1 Для каждого слагаемого, кроме a 0 возвести x в заданную степень последовательным умножением и затем домножить на коэффициент. Затем слагаемые сложить. Вычисление i- го слагаемого (i=1..n) требует i умножений. всего 1 + 2 + 3 +... + n = n(n+1)/2 умножений. кроме того, требуется n+1 сложение. Всего n(n+1)/2 + n + 1= n 2 /2 + 3n/2 + 1 операций. P n (x) = a n x n + a n-1 x n-1 +... + a i x i +... + a 1 x 1 + a 0

Изображение слайда
1/1
7

Слайд 7: Пример

Алгоритм 2 Вынесем x за скобки и перепишем многочлен в виде Самая внутренняя скобка требует одно умножение и одно сложение. Ее значение используется для следующей скобки. И так, одно умножение и одно сложение на каждую скобку, которых n-1 штука. И еще после вычисления самой внешней скобки умножить на x и прибавить a 0. Таким образом, всего n умножений и n сложений, всего 2n операций. P n (x) = a 0 + x(a 1 + x(a 2 +... ( a i +.. x(a n-1 + a n x )))

Изображение слайда
1/1
Реклама. Продолжение ниже
8

Слайд 8: Обозначения сложности

широкое распространение для оценивания алгоритмов в отношении размера входных данных получили обозначения с использованием символа О(*). Типичный результат: сложность алгоритма сортировки – О( nlogn ). Читается как «сложность алгоритма порядка nlogn » это следует понимать так: существует константа C  >   0, такая, что время работы алгоритма в худшем случае не превышает C · n · log 2 n. Существует и другой подход, который заключается в рассмотрении сложности в среднем.

Изображение слайда
1/1
9

Слайд 9

Выражение О(*) показывает, насколько быстро увеличивается время работы алгоритма с увеличением размерности, т.е.алгоритм, работающий за время О( nlogn ) лучше алгоритма с временем работы О( n 2 ). Таким образом, сложность алгоритма определяется как порядок функции, выражающее время его работы или затрачиваемую память.

Изображение слайда
1/1
10

Слайд 10: Примеры

Алгоритм Сложность a[1]:=10 O(1) i:=1…n a[i]:=i O(n) i:=1…n j:=1…m a[i]:=a[i]+a[j] O(n 2 ) Умножение матриц O(n 3 )

Изображение слайда
1/1
11

Слайд 11: Сравнение среднего, худшего и лучшего случаев

Количество элементов ( п ) Средний случай: nlogn Худший случай: п 2 8 64 2048 24 384 22528 64 4096 4194304

Изображение слайда
1/1
12

Последний слайд презентации: Анализ производительности алгоритмов

Изображение слайда
1/1
Реклама. Продолжение ниже