Анализ алгоритмов и их сложности

Июль 26, 2022

Главная
Информатика
Анализ алгоритмов и их сложности

Содержание

2. Сложность алгоритма Для практики недостаточно знать, что задача алгоритмически разрешима Т. к. ресурсы ЭВМ (оперативная память
3. Сложность алгоритма Оценка сложности зависит от: ♦ времени, затраченного на выполнение алгоритма ♦ объема памяти, требуемой
4. Оценка качества алгоритма
5. Оценка качества алгоритма
6. Оценка качества алгоритма
7. Оценка качества алгоритма
8. Сложность алгоритма
9. Выбор алгоритма Какой из множества алгоритмов выбрать для решения конкретной задачи? Как оценить эффективность программы? Лучший
10. Задачи и многообразие алгоритмов их решения
11. Задачи и многообразие алгоритмов их решения Задача возведения в степень Дано число x и натуральное (целое
12. Задачи и многообразие алгоритмов их решения Задача возведения в степень Дано число x и натуральное (целое
13. Задачи и многообразие алгоритмов их решения Задача возведения в степень Дано число x и натуральное (целое
14. Задачи и многообразие алгоритмов их решения Задача возведения в степень Дано число x и натуральное (целое
15. Задачи и многообразие алгоритмов их решения Задача возведения в степень – быстрые алгоритмы Для такой относительно
16. Проблема выбора алгоритма. Понятие временной сложности Программисты должны быть осведомлены не только о методах построения быстрых
17. Проблема выбора алгоритма. Понятие временной сложности Время выполнения является функцией размера данных самих исходных данных Функцию
18. Проблема выбора алгоритма. Понятие временной сложности - это время T, необходимое для его выполнения в зависимости
19. Проблема выбора алгоритма. Понятие временной сложности n – это размерность задачи (для линейного массива – размер
20. Асимптотические соотношения оценки временной сложности Оценка временной сложности алгоритма – математически оценить время исполнения подсчетом операций
21. Асимптотические соотношения оценки временной сложности Оценка временной сложности – математически оценить время исполнения подсчетом операций Основные
22. Асимптотические соотношения оценки временной сложности Оценка временной сложности – математически оценить время исполнения подсчетом операций Пример.
23. Асимптотические соотношения оценки временной сложности Пример. Задача вычисления значения многочлена Алгоритм 1: для каждого слагаемого, кроме
24. Асимптотические соотношения оценки временной сложности Пример. Задача вычисления значения многочлена Алгоритм 1, оценка временной сложности Вычисление
25. Асимптотические соотношения оценки временной сложности Пример. Задача вычисления значения многочлена Алгоритм 2: S0 = an, S1
26. Асимптотические соотношения оценки временной сложности Пример. Задача вычисления значения многочлена Алгоритм 2, оценка временной сложности для
27. Асимптотические соотношения оценки временной сложности Обычно подробная оценка временной сложности не требуется Достаточно указать асимптотическую скорость
28. Асимптотические соотношения оценки временной сложности Если числа в таблице - микросекунды, то для задачи с n=1048576
29. Время выполнения алгоритмов
30. Асимптотические соотношения оценки временной сложности Для описания скорости роста функций используется О-символика (Paul Bachman 1894г.) "урезанная"
31. Асимптотические соотношения оценки временной сложности Когда мы говорим, что Т(n) имеет степень роста O(f(n)), то подразумевается,
32. Асимптотические соотношения оценки временной сложности Временная сложность алгоритма в худшем случае — функция размера входных данных,
33. Асимптотические соотношения оценки временной сложности
34. Асимптотические соотношения оценки временной сложности Также используется оценка Θ(n), которая является комбинаций O(n) и Ω(n) Θ(n)
35. Асимптотические соотношения оценки временной сложности O( ) – асимптотическая оценка алгоритма на худших входных данных, Ω(
36. Сравнительная оценка сложности алгоритмов
37. Асимптотические соотношения оценки временной сложности
38. Вычисление временной сложности Базовые принципы определения времени выполнения программ: При оценке за функцию берется количество операций,
39. Некоторые операции с символом О
40. Сравнительная оценка сложности алгоритмов Задача Дано: два алгоритма А1 и А2 , решающих одну и ту
41. Сравнительная оценка сложности алгоритмов Решение t1 = 10 12 / 10 8 = 10 4 с
42. Временная сложность алгоритмов
44. Скачать презентацию

Слайд 2

Сложность алгоритма
Для практики недостаточно знать, что задача алгоритмически разрешима
Т. к. ресурсы

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

Для оценки качества введено понятие сложности или обратное понятие — эффективность алгоритма

Слайд 3

Сложность алгоритма
Оценка сложности зависит от:
♦ времени, затраченного на выполнение алгоритма
♦ объема

памяти, требуемой для хранения исходных данных задачи

Слайд 4

Оценка качества алгоритма

Слайд 5

Оценка качества алгоритма

Слайд 6

Оценка качества алгоритма

Слайд 7

Оценка качества алгоритма

Слайд 8

Сложность алгоритма

Слайд 9

Выбор алгоритма
Какой из множества алгоритмов выбрать для решения конкретной задачи?
Как оценить

эффективность программы?

Лучший способ сравнения эффективностей алгоритмов - сопоставление их порядков сложности; применим к временной и пространственной сложности

Слайд 10

Задачи и многообразие алгоритмов их решения

Слайд 11

Задачи и многообразие алгоритмов их решения
Задача возведения в степень
Дано число x

и натуральное (целое неотрицательное) число n ≥ 0.
Вычислить значение функции f(x) = хn

Очевидный способ решения:

f(x) = хn

Слайд 12

Задачи и многообразие алгоритмов их решения
Задача возведения в степень
Дано число x

и натуральное (целое неотрицательное) число n ≥ 0.
Вычислить значение функции f(x) = хn

div - операция целочисленного деления

Слайд 13

Задачи и многообразие алгоритмов их решения
Задача возведения в степень
Дано число x

и натуральное (целое неотрицательное) число n ≥ 0.
Вычислить значение функции f(x) = хn

Рекурсивный алгоритм возведения в степень

Слайд 14

Задачи и многообразие алгоритмов их решения
Задача возведения в степень
Дано число x

и натуральное (целое неотрицательное) число n ≥ 0.
Вычислить значение функции f(x) = хn

Слайд 15

Задачи и многообразие алгоритмов их решения
Задача возведения в степень – быстрые

алгоритмы

Для такой относительно простой задачи, как возведение в степень существуют,
по крайней мере,
4 алгоритма

Слайд 16

Проблема выбора алгоритма. Понятие временной сложности
Программисты должны быть осведомлены не только

о методах построения быстрых программ, но и знать, когда их следует применить, желательно с минимальными программистскими усилиями

Противоречащие друг другу требования

Слайд 17

Проблема выбора алгоритма. Понятие временной сложности
Время выполнения является
функцией
размера данных
самих исходных

данных

Функцию Т(n) можно
найти экспериментально,
но это сложно…

Слайд 18

Проблема выбора алгоритма. Понятие временной сложности
- это время T, необходимое для

его выполнения в зависимости от исходных данных

Временнáя сложность алгоритма

T = k·t,
где k – количество вычислительных действий
t – время выполнения одного действия
В практике оценки времени выполнения программ,
Т(n) понимают как количество элементарных шагов – инструкций, выполняемых на идеализированном компьютере

Слайд 19

Проблема выбора алгоритма. Понятие временной сложности
n – это размерность задачи
(для

линейного массива – размер массива)

T(n) – зависимость времени от объема входных данных

Поведение T при увеличении n называется теоретической сложностью – O(f(n))

Слайд 20

Асимптотические соотношения оценки временной сложности
Оценка временной сложности алгоритма –
математически оценить

время исполнения подсчетом операций

1. Записать алгоритм в виде кода одного из развитых языков программирования (например, Java или С++).
2. Перевести программу в последовательность машинных команд (например, байт-коды, используемые в виртуальной машине Java).
3. Определить для каждой машинной команды i время ti, необходимое для ее выполнения.
4. Определить для каждой машинной команды i количество повторений ni команды i за время выполнения алгоритма.
5. Определить произведение ti *ni всех машинных команд, что и будет составлять время выполнения алгоритма.

Слайд 21

Асимптотические соотношения оценки временной сложности
Оценка временной сложности –
математически оценить время

исполнения подсчетом операций

Основные (простейшие) операции, аналоги машинных команд:
присваивание переменной значения
вызов функции
выполнение арифметической операции
сравнение двух чисел
индексация массива
переход по ссылке на объект
возвращение из функции

Слайд 22

Асимптотические соотношения оценки временной сложности
Оценка временной сложности –
математически оценить время

исполнения подсчетом операций

Пример. Задача вычисления значения многочлена

Задано:
массив коэффициентов A={A[0], A[1],…, A[n]}
значение переменной x
Вычислить значение многочлена S = Pn(x)

Слайд 23

Асимптотические соотношения оценки временной сложности
Пример. Задача вычисления значения многочлена
Алгоритм 1:
для

каждого слагаемого, кроме a0 возвести x в заданную степень последовательным умножением и затем помножить на коэффициент

Слайд 24

Асимптотические соотношения оценки временной сложности
Пример. Задача вычисления значения многочлена
Алгоритм 1, оценка

временной сложности

Вычисление i-го слагаемого(i=1...n) требует i умножений
всего 1 + 2 + 3 + ... + n = n(n+1)/2 умножений
Требуется n сложений и одна операция начального присваивания значения a0
Временная сложность алгоритма:
Т(n) = n(n+1)/2 + n + 1 = n2/2 + 3n/2 + 1 операций

Слайд 25

Асимптотические соотношения оценки временной сложности
Пример. Задача вычисления значения многочлена
Алгоритм 2:

S0

= an,
S1 = S0 x + an-1,
S2 = S1 x + an-2,
…,
Si = Si-1 x + an-i,
…,
Sn = Sn-1 x + a0, Pn(x) = Sn

Схема Горнера

Слайд 26

Асимптотические соотношения оценки временной сложности
Пример. Задача вычисления значения многочлена
Алгоритм 2, оценка

временной сложности

для вычисления Si требуется 1 умножение и 1 сложение
всего такая итерация осуществляется n раз
Временная сложность алгоритма:
Т(n) = n умножений + n сложений = 2n операций

Слайд 27

Асимптотические соотношения оценки временной сложности
Обычно подробная оценка временной сложности не требуется
Достаточно

указать асимптотическую скорость возрастания количества операций при увеличении n
Например, функция Т(n) = n2/2 + 3n/2 + 1 возрастает приблизительно как n2/2
Это – верхняя оценка, т.е. количество операций (а значит, и время работы) растет не быстрее, чем квадрат количества элементов
Говорят, что Т(n) есть O(n2), или Т(n) имеет порядок O(n2)

Слайд 28

Асимптотические соотношения оценки временной сложности
Если числа в таблице - микросекунды, то

для задачи с n=1048576 элементами алгоритму с временем работы порядка O(log n) потребуется 20 микросекунд
алгоритму с временем работы порядка O(n2) – более 12 дней

Слайд 29

Время выполнения алгоритмов

Слайд 30

Асимптотические соотношения оценки временной сложности
Для описания скорости роста функций используется О-символика

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

Слайд 31

Асимптотические соотношения оценки временной сложности
Когда мы говорим, что Т(n) имеет степень

роста O(f(n)),
то подразумевается, что f(n) является верхней границей скорости роста Т(n)
Когда мы говорим, что время выполнения Т(n) некоторой программы имеет порядок О(n2), то подразумевается, что существуют положительные константы с и n0 такие, что для
всех n ≥ n0, выполняется неравенство Т(n) < c n2.
Чтобы указать нижнюю границу скорости роста Т(n), используется обозначение: Ω(g(n)) это подразумевает существование такой константы с, что для бесконечного числа значений n выполняется неравенство Т(n) > cg(n).

Слайд 32

Асимптотические соотношения оценки временной сложности
Временная сложность алгоритма в худшем случае — функция

размера входных данных, которая показывает максимальное количество элементарных операций, которые могут быть затрачены алгоритмом для решения экземпляра задачи указанного размера - O(f(n))
Аналогично определяется понятие временная сложность алгоритма в наилучшем случае - Ω(g(n))

Слайд 33

Асимптотические соотношения оценки временной сложности

Слайд 34

Асимптотические соотношения оценки временной сложности
Также используется оценка Θ(n), которая является комбинаций

O(n) и Ω(n)
Θ(n) - точная оценка асимптотики

Θ(g(n)) – множество функций Т(п), для которых существуют такие константы c1, c2 и n0, что c1 g(n) ≤ Т(п) ≤ c2 g(n) для всех n ≥ n0. Оценка Θ(g(n)) существует только тогда, когда O(g(n)) и Ω(g(n)) совпадают и равна им

Слайд 35

Асимптотические соотношения оценки временной сложности
O( ) – асимптотическая оценка алгоритма на

худших входных данных,
Ω( ) – на лучших входных данных,
Θ( ) – сокращенная запись одинаковых O( ) и Ω( ).
Интуитивный смысл этих оценок:

Слайд 36

Сравнительная оценка сложности алгоритмов

Слайд 37

Асимптотические соотношения оценки временной сложности

Слайд 38

Вычисление временной сложности
Базовые принципы определения времени выполнения программ:
При оценке за функцию

берется количество операций, возрастающее быстрее всего
½ n2 + n = O(n2)
При оценке O( ) константы не учитываются
Основание логарифма внутри символа O( ) не пишется

Слайд 39

Некоторые операции с символом О

Слайд 40

Сравнительная оценка сложности алгоритмов
Задача
Дано: два алгоритма А1 и А2 ,

решающих одну и
ту же задачу размерности n=10 6
А1 имеет сложность O1(n2) и выполняется на суперкомпьютере с быстродействием 10 8оп/с;
А2 имеет сложность O2(n·log2n) и выполняется на обычном компьютере с быстродействием 10 6оп/с

Требуется:
найти время решения задачи t1 , t2 - ?

Слайд 41

Сравнительная оценка сложности алгоритмов
Решение
t1 = 10 12 / 10 8

= 10 4 с ≈ 2,8 ч
t2 = 10 6 ·log2 10 6 / 10 6 = 6 ·log2 10 ≈ 20 с

Вывод: Разработка эффективных алгоритмов не менее важна, чем разработка быстрой электроники!

Слайд 42

Анализ алгоритмов и их сложности

Содержание

Сложность алгоритма Для практики недостаточно знать, что задача алгоритмически разрешимаТ. к. ресурсы

Сложность алгоритма Оценка сложности зависит от:♦ времени, затраченного на выполнение алгоритма♦ объема

Оценка качества алгоритма

Оценка качества алгоритма

Оценка качества алгоритма

Оценка качества алгоритма

Сложность алгоритма

Выбор алгоритма Какой из множества алгоритмов выбрать для решения конкретной задачи?Как оценить

Задачи и многообразие алгоритмов их решения

Задачи и многообразие алгоритмов их решенияЗадача возведения в степеньДано число x

Задачи и многообразие алгоритмов их решенияЗадача возведения в степеньДано число x

Задачи и многообразие алгоритмов их решенияЗадача возведения в степеньДано число x

Задачи и многообразие алгоритмов их решенияЗадача возведения в степеньДано число x

Задачи и многообразие алгоритмов их решенияЗадача возведения в степень – быстрые

Проблема выбора алгоритма. Понятие временной сложностиПрограммисты должны быть осведомлены не только

Проблема выбора алгоритма. Понятие временной сложностиВремя выполнения является функциейразмера данныхсамих исходных

Проблема выбора алгоритма. Понятие временной сложности - это время T, необходимое для

Проблема выбора алгоритма. Понятие временной сложностиn – это размерность задачи (для

Асимптотические соотношения оценки временной сложностиОценка временной сложности алгоритма – математически оценить

Асимптотические соотношения оценки временной сложностиОценка временной сложности – математически оценить время

Асимптотические соотношения оценки временной сложностиОценка временной сложности – математически оценить время

Асимптотические соотношения оценки временной сложностиПример. Задача вычисления значения многочленаАлгоритм 1: для

Асимптотические соотношения оценки временной сложностиПример. Задача вычисления значения многочленаАлгоритм 1, оценка

Асимптотические соотношения оценки временной сложностиПример. Задача вычисления значения многочленаАлгоритм 2: S0

Асимптотические соотношения оценки временной сложностиПример. Задача вычисления значения многочленаАлгоритм 2, оценка

Асимптотические соотношения оценки временной сложностиОбычно подробная оценка временной сложности не требуетсяДостаточно

Асимптотические соотношения оценки временной сложностиЕсли числа в таблице - микросекунды, то

Время выполнения алгоритмов

Асимптотические соотношения оценки временной сложностиДля описания скорости роста функций используется О-символика

Асимптотические соотношения оценки временной сложностиКогда мы говорим, что Т(n) имеет степень

Асимптотические соотношения оценки временной сложностиВременная сложность алгоритма в худшем случае — функция

Асимптотические соотношения оценки временной сложности

Асимптотические соотношения оценки временной сложностиТакже используется оценка Θ(n), которая является комбинаций

Асимптотические соотношения оценки временной сложностиO( ) – асимптотическая оценка алгоритма на

Сравнительная оценка сложности алгоритмов

Асимптотические соотношения оценки временной сложности

Вычисление временной сложности Базовые принципы определения времени выполнения программ:При оценке за функцию

Некоторые операции с символом О

Сравнительная оценка сложности алгоритмовЗадача Дано: два алгоритма А1 и А2 ,

Сравнительная оценка сложности алгоритмовРешение t1 = 10 12 / 10 8

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

Похожие презентации

Сложность алгоритма
Для практики недостаточно знать, что задача алгоритмически разрешима
Т. к. ресурсы

Сложность алгоритма
Оценка сложности зависит от:
♦ времени, затраченного на выполнение алгоритма
♦ объема

Выбор алгоритма
Какой из множества алгоритмов выбрать для решения конкретной задачи?
Как оценить

Задачи и многообразие алгоритмов их решения
Задача возведения в степень
Дано число x

Задачи и многообразие алгоритмов их решения
Задача возведения в степень
Дано число x

Задачи и многообразие алгоритмов их решения
Задача возведения в степень
Дано число x

Задачи и многообразие алгоритмов их решения
Задача возведения в степень
Дано число x

Задачи и многообразие алгоритмов их решения
Задача возведения в степень – быстрые

Проблема выбора алгоритма. Понятие временной сложности
Программисты должны быть осведомлены не только

Проблема выбора алгоритма. Понятие временной сложности
Время выполнения является
функцией
размера данных
самих исходных

Проблема выбора алгоритма. Понятие временной сложности
- это время T, необходимое для

Проблема выбора алгоритма. Понятие временной сложности
n – это размерность задачи
(для

Асимптотические соотношения оценки временной сложности
Оценка временной сложности алгоритма –
математически оценить

Асимптотические соотношения оценки временной сложности
Оценка временной сложности –
математически оценить время

Асимптотические соотношения оценки временной сложности
Оценка временной сложности –
математически оценить время

Асимптотические соотношения оценки временной сложности
Пример. Задача вычисления значения многочлена
Алгоритм 1:
для

Асимптотические соотношения оценки временной сложности
Пример. Задача вычисления значения многочлена
Алгоритм 1, оценка

Асимптотические соотношения оценки временной сложности
Пример. Задача вычисления значения многочлена
Алгоритм 2:

S0

Асимптотические соотношения оценки временной сложности
Пример. Задача вычисления значения многочлена
Алгоритм 2, оценка

Асимптотические соотношения оценки временной сложности
Обычно подробная оценка временной сложности не требуется
Достаточно

Асимптотические соотношения оценки временной сложности
Если числа в таблице - микросекунды, то

Асимптотические соотношения оценки временной сложности
Для описания скорости роста функций используется О-символика

Асимптотические соотношения оценки временной сложности
Когда мы говорим, что Т(n) имеет степень

Асимптотические соотношения оценки временной сложности
Временная сложность алгоритма в худшем случае — функция

Асимптотические соотношения оценки временной сложности
Также используется оценка Θ(n), которая является комбинаций

Асимптотические соотношения оценки временной сложности
O( ) – асимптотическая оценка алгоритма на

Вычисление временной сложности
Базовые принципы определения времени выполнения программ:
При оценке за функцию

Сравнительная оценка сложности алгоритмов
Задача
Дано: два алгоритма А1 и А2 ,

Сравнительная оценка сложности алгоритмов
Решение
t1 = 10 12 / 10 8