Презентация Оценка сложности вычислительных алгоритмов. Лекция 22 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Оценка сложности вычислительных алгоритмов. Лекция 22 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 32 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:32 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:81.82 kB
- Просмотров:80
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Оценка сложности вычислительных программ
лекция 22
№2 слайд
Содержание слайда: План лекции
Сложность программы по времени и по памяти
Основные понятия
Сложность в худшем случае, сложность в среднем
Оценка сложности для программы на языке Си
Понятие оптимальной программы
Пример доказательства оптимальности
Асимптотическая сложность и оптимальность
№3 слайд
Содержание слайда: Основные параметры вычислений и данных
Как число необходимых команд и ячеек памяти зависит от размера входных данных?
Обозначим Time(А, х) и Space(A, x) число команд и ячеек памяти, необходимых программе А для обработки входных данных х
Обозначим |x| >= 0 размер входных данных x
№4 слайд
Содержание слайда: Примеры
Умножение матриц MM
|x| = порядок матрицы x
Space(MM, x) = 3*|x|^2
Time(MM, x) = число умножений и сложений = 2 * |x|^3
Сортировка массива простыми вставками I
|x| = длина массива х
Space(I, x) = |x|
|x| - 1 <= Time(I, x) = число сравнений <= |x| *(|x| - 1)/2
№5 слайд
Содержание слайда: Минимальные требования к |.|
Число команд, необходимых программе для обработки входных данных, должно стремиться к ∞ когда размер входных данных стремится к ∞
Time(A, xk) -> ∞ при |xk| -> ∞
№6 слайд
Содержание слайда: Временная сложность
Временной сложностью (сложностью по времени в худшем случае) программы А называется функция от размера входных данных Т(А, n) = max{ Time(A, x) | |x| = n }
№7 слайд
Содержание слайда: Сложность по памяти
Сложностью по памяти в худшем случае (пространственной сложностью) программы А называется функция от размера входных данных S(А, n) = max{ Space(A, x) | |x|=n }
№8 слайд
Содержание слайда: Сложность в среднем 1/3
Обозначим Input(n) = { x ||x| = n } множество входных данных размера n
Обозначим P(n, x) вероятность входных данных x ∈ Input(n)
Можно считать P(n, x) = 1 / (число элементов в Input(n))
Иногда считают, что вероятность разных входных данных разная
По определению вероятности Σx ∈ Input(n) P(n, x) = 1
№9 слайд
Содержание слайда: Сложность в среднем 2/3
Величина T(A, n) = Σx ∈ Input(n) Time(A, x) P(n, x) называется временной сложностью программы А в среднем
№10 слайд
Содержание слайда: Сложность в среднем 2/3
Величина S(A, n) = Σx ∈ Input(n) Space(A, x) P(n, x) называется сложностью по памяти программы А в среднем
№11 слайд
Содержание слайда: Связь между разными мерами сложности
Сложность в среднем не превосходит сложность в худшем случае
T(A, n) <= T(A, n)
S(A, n) <= S(A, n)
T(A, n) = Σx ∈ Input(n) Time(A, x) P(n, x) <=
<= Σx ∈ Input(n) max { Time(A, x) | |x| = n } P(n, x) =
= T(A, n) Σx ∈ Input(n) P(n, x) = T(A, n)
Сложность по памяти не превосходит сложность по времени
S(A, n) < = T(A, n)
В каждую ячейку памяти нужно хотя бы записать значение
№12 слайд
Содержание слайда: Пример вычисления сложности по времени в среднем 1/3
Возведение a в степень x методом повторных квадратов RS
RS(a, x):
q = a
u = 1
for bit in запись х в двоичной с.с. :
if bit == 1:
u *= q
q *= q
return u
№13 слайд
Содержание слайда: Пример вычисления сложности по времени в среднем 2/3
Input(n) = { x | 2n – 1 <= x < 2n – 1 }
|x| = число битов в x
P(n, x) = 1 / (число элементов в Input(n)) = 1 / 2n – 1
T(RS, n) = (1 / 2n – 1) Σx ∈ Input(n)( |x| + (число битов = 1 в х) – 2 ) =
= n – 2 + 1 + (1 / 2n – 1) Σx ∈ Input(n) ( число битов = 1 в х )
№14 слайд
Содержание слайда: Пример вычисления сложности по времени в среднем 3/3
Как известно, k∙C(n, k) = n∙C(n – 1, k – 1)
Σx ∈ Input(n)( число битов = 1 в х) =
= Σ0<=k<=n-1 k∙C(n – 1, k) = Σ1<=k<=n-1 (n – 1)∙C(n – 2, k – 1) =
= (n – 1) ∙ Σ0<=k<=n-2 C(n – 2, k) = (n – 1) ∙ 2n – 2
T(RS, n) = n – 1 + (1 / 2n – 1) ∙ Σx ∈ Input(n)(число битов = 1 в х) =
= n – 1 + (1 / 2n – 1) ∙ (n – 1 )∙2n – 2 = 3 ∙ (n – 1) / 2
№15 слайд
Содержание слайда: Оценка сложности с практической точки зрения
Точное число команд и ячеек памяти на практике не важно
Зависит от набора команд
Для входных данных большого размера слагаемые низших составляют исчезающий % от общего числа команд и ячеек памяти
Обычно приближенно оценивают сверху самое быстро растущее слагаемое в зависимости от размера данных
Существуют разные методы построения приближенных оценок сверху для сложности программ
№16 слайд
Содержание слайда: Как оценить сложность программы на языке Си?
Обозначим T(A, n) оценку сверху для T(A, n) на основе записи А на языке Си
T({ А1; А2; }, n) = T (A1, n) + T(A2, n)
T({ if (C) A1; else A2; }, n) = T (C, n) + max(T(A1, n), T(A2, n))
T({ for (i = N(n); i > 0; --i) A(i); }, n) = T (N(n), n) + Σ0<i<=N(n) T(A(i), n)
T({ F(A1, A2, …, AN); }, n) = T(A1, n) + … + T(AN, n) + T(тело(F), n)
Не применимо, если F является рекурсивной
№17 слайд
Содержание слайда: Оптимальные программы
Программа А* называется оптимальной по времени в классе программ АА, если для любой программы А из АА и любого размера n входных данных T(A*, n) <= T(A, n)
Для доказательства оптимальности программы по времени требуется оценка T(A, n) снизу
Существуют разные методы построения приближенных оценок снизу для сложности программ
№18 слайд
Содержание слайда: Дерево трасс исполнения
Трасса исполнения программы для входных данных х – это множество пар вида (номер шага при обработке х, исполненная на этом шаге команда)
Дерево трасс исполнения для входных данных размера n
Множество вершин = объединение трасс для всех входных данных размера n
Вершина (q, c1) является родителем вершины (r, c2), если q + 1 = r
«Дерево трасс исполнения получается склеиванием общих префиксов»
№19 слайд
Содержание слайда: Построение оценки снизу для поиска min и max -- 1/4
Пусть АА – все программы для одновременного нахождения минимума и максимума в массиве
Покажем, что сложность по числу сравнений оптимальной программы 3n/2 – 2, и приведем оптимальную программу
№20 слайд
Содержание слайда: Построение оценки снизу для поиска min и max -- 2/4
Каждый шаг произвольной программы, решающей эту задачу, характеризуется 4 множествами элементов массива (A, B, C, D):
A = не участвовали в сравнениях
B = во всех сравнениях были больше
C = во всех сравнениях были меньше
D = в одних сравнениях были больше, а в других — меньше
№21 слайд
Содержание слайда: Построение оценки снизу для поиска min и max -- 3/4
Пусть λ(a, b, c) = 3*a/2 + b + c − 2
a, b и c -- число элементов в A, B и C
Начинаем с λ(n, 0, 0) = 3n/2-2
Заканчиваем λ(0, 1, 1) = 0
При движении в дереве трасс исполнения от корня к самому глубокому листу λ уменьшается не более, чем на 1 – см. таблицу справа
Следовательно, в худшем случае требуется не менее 3n/2 – 2 сравнений
№22 слайд
Содержание слайда: Построение оценки снизу для поиска min и max -- 4/4
Дан массив из n элементов x1, ..., xn
Образуем пары x1, x2 ; x3, x4 ; …
В каждой паре найдём минимум и максимум за одно сравнение
Пусть m1, m2, … – массив минимальных элементов пар размера n/2
Пусть M1, M2, ... – массив максимальных элементов пар размера n/2
Минимальный элемент исходного массива среди mi
Максимальный элемент исходного массива среди Mi
Если на первом шаге был непарный элемент (n — нечётное), то на него потребуется ещё два сравнения с найденными минимумом и максимумом
В итоге на каждую пару тратится 3 сравнения
№23 слайд
Содержание слайда: Асимптотические оценки сложности
Функции f и g называются функциями одного порядка, если найдутся такие c1 и c2, что для любого n
c1|g(n)| < |f(n)| < c2|g(n)|
Обозначается f ~ g
Функция f -- омега функции g, если найдется такая константа c, что |f (n)| > c | g(n) | для всех n
Обозначается f (n) = Ω(g(n))
№24 слайд
Содержание слайда: Асимптотически оптимальная программа
Программа А* называется асимптотически оптимальной (оптимальной по порядку сложности) в классе АА, если T(А*, n) = Ω(Т(А, n)) для любой другой программы A из АА
№25 слайд
Содержание слайда: Асимптотически оптимальная программа
Если A* и B* -- оптимальные программы в классе АА, то T(А*, n) = Ω(Т(B*, n)) и T(В*, n) = Ω(Т(А*, n)) и T(А*, n) ~ Т(B*, n)
Оптимальная асимптотическая сложность определена однозначно
№26 слайд
Содержание слайда: Заключение
Сложность программы по времени и по памяти
Основные понятия
Сложность в худшем случае, сложность в среднем
Оценка сложности для программы на языке Си
Понятие оптимальной программы
Пример доказательства оптимальности
Асимптотическая сложность и оптимальность
№27 слайд
Содержание слайда: Классы сложности задач
Под «задачей» будем понимать набор из трех объектов:
функция P(.), которую требуется вычислить
функция измерения входных данных |.|
функция измерения числа операций T(.,.) в алгоритме вычисления функции P(.)
№28 слайд
Содержание слайда: Классы сложности задач
Задача P не сложнее Q, если для любой программы QA, решающей задачу Q, найдётся программа PA, решающая задачу P, такая что T(PA, n) = O(T(QA, n))
Обозначение P ≤ Q
Задачи P и Q, для которых одновременно верно P ≤ Q и Q ≤ P , называются эквивалентными (по сложности)
Обозначение P >< Q
№29 слайд
Содержание слайда: Пример
Рассмотрим следующие задачи:
M: умножение 2-х целых чисел a и b
D: деление целого a битовой длины ≤ 2m на целое b битовой длины m
S: возведение в квадрат целого a
R: обращение целого a
Покажем, что M >< D >< S >< R
№30 слайд
Содержание слайда: Пример
Можно доказать, что для |x| = число битов в x cложность f(.) любого из этих алгоритмов
не убывает
f(m) >= m
af(m) <= f(am) <= a^2f(m) для a > 1
№31 слайд
Содержание слайда: Пример
M < S
ab = ((a+b)^2-a^2-b^2)/2
T(MA, m) = T(SA, m+1)+2T(SA,m)+O(m) = O(T(SA,m))
S < R
a^2 = 1/(1/a-1/(a+1))-a
T(SA, m) = O(T(RA, с*m)) – так как делить нужно в с раз более точно
№32 слайд
Содержание слайда: Пример
R < M
x[i]=2*x[i-1]-a*x[i-1]^2
Cходится к 1/а и x[i-1]=1/a*(1- ε) ==> x[i]=1/a*(1- ε^2)
Почему?
T(RA, m) = O(T(MA,m))
M >< S >< R
D < M
a/b = a*(1/b)
R < D -- очевидно
Скачать все slide презентации Оценка сложности вычислительных алгоритмов. Лекция 22 одним архивом:
