🗊Презентация Оценка сложности вычислительных алгоритмов. Лекция 22

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №1Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №2Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №3Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №4Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №5Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №6Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №7Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №8Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №9Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №10Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №11Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №12Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №13Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №14Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №15Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №16Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №17Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №18Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №19Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №20Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №21Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №22Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №23Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №24Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №25Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №26Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №27Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №28Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №29Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №30Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №31Оценка сложности вычислительных алгоритмов. Лекция 22, слайд №32
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Оценка сложности вычислительных алгоритмов. Лекция 22. Доклад-сообщение содержит 32 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Оценка сложности вычислительных программ лекция 22
Описание слайда:
Оценка сложности вычислительных программ лекция 22

Слайд 2


План лекции Сложность программы по времени и по памяти Основные понятия Сложность в худшем случае, сложность в среднем Оценка сложности для программы на языке Си Понятие оптимальной программы Пример доказательства оптимальности Асимптотическая сложность и оптимальность
Описание слайда:
План лекции Сложность программы по времени и по памяти Основные понятия Сложность в худшем случае, сложность в среднем Оценка сложности для программы на языке Си Понятие оптимальной программы Пример доказательства оптимальности Асимптотическая сложность и оптимальность

Слайд 3


Основные параметры вычислений и данных Как число необходимых команд и ячеек памяти зависит от размера входных данных? Обозначим Time(А, х) и Space(A, x) число команд и ячеек памяти, необходимых программе А для обработки входных данных х Обозначим |x| >= 0 размер входных данных x
Описание слайда:
Основные параметры вычислений и данных Как число необходимых команд и ячеек памяти зависит от размера входных данных? Обозначим 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
Описание слайда:
Примеры Умножение матриц 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| -> ∞
Описание слайда:
Минимальные требования к |.| Число команд, необходимых программе для обработки входных данных, должно стремиться к ∞ когда размер входных данных стремится к ∞ Time(A, xk) -> ∞ при |xk| -> ∞

Слайд 6


Временная сложность Временной сложностью (сложностью по времени в худшем случае) программы А называется функция от размера входных данных Т(А, n) = max{ Time(A, x) | |x| = n }
Описание слайда:
Временная сложность Временной сложностью (сложностью по времени в худшем случае) программы А называется функция от размера входных данных Т(А, n) = max{ Time(A, x) | |x| = n }

Слайд 7


Сложность по памяти Сложностью по памяти в худшем случае (пространственной сложностью) программы А называется функция от размера входных данных S(А, n) = max{ Space(A, x) | |x|=n }
Описание слайда:
Сложность по памяти Сложностью по памяти в худшем случае (пространственной сложностью) программы А называется функция от размера входных данных 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
Описание слайда:
Сложность в среднем 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) называется временной сложностью программы А в среднем
Описание слайда:
Сложность в среднем 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) называется сложностью по памяти программы А в среднем
Описание слайда:
Сложность в среднем 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) В каждую ячейку памяти нужно хотя бы записать значение
Описание слайда:
Связь между разными мерами сложности Сложность в среднем не превосходит сложность в худшем случае 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
Описание слайда:
Пример вычисления сложности по времени в среднем 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 в х )
Описание слайда:
Пример вычисления сложности по времени в среднем 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
Описание слайда:
Пример вычисления сложности по времени в среднем 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 является рекурсивной
Описание слайда:
Как оценить сложность программы на языке Си? Обозначим 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) снизу Существуют разные методы построения приближенных оценок снизу для сложности программ
Описание слайда:
Оптимальные программы Программа А* называется оптимальной по времени в классе программ АА, если для любой программы А из АА и любого размера n входных данных T(A*, n) <= T(A, n) Для доказательства оптимальности программы по времени требуется оценка T(A, n) снизу Существуют разные методы построения приближенных оценок снизу для сложности программ

Слайд 18


Дерево трасс исполнения Трасса исполнения программы для входных данных х – это множество пар вида (номер шага при обработке х, исполненная на этом шаге команда) Дерево трасс исполнения для входных данных размера n Множество вершин = объединение трасс для всех входных данных размера n Вершина (q, c1) является родителем вершины (r, c2), если q + 1 = r «Дерево трасс исполнения получается склеиванием общих префиксов»
Описание слайда:
Дерево трасс исполнения Трасса исполнения программы для входных данных х – это множество пар вида (номер шага при обработке х, исполненная на этом шаге команда) Дерево трасс исполнения для входных данных размера n Множество вершин = объединение трасс для всех входных данных размера n Вершина (q, c1) является родителем вершины (r, c2), если q + 1 = r «Дерево трасс исполнения получается склеиванием общих префиксов»

Слайд 19


Построение оценки снизу для поиска min и max -- 1/4 Пусть АА – все программы для одновременного нахождения минимума и максимума в массиве Покажем, что сложность по числу сравнений оптимальной программы 3n/2 – 2, и приведем оптимальную программу
Описание слайда:
Построение оценки снизу для поиска min и max -- 1/4 Пусть АА – все программы для одновременного нахождения минимума и максимума в массиве Покажем, что сложность по числу сравнений оптимальной программы 3n/2 – 2, и приведем оптимальную программу

Слайд 20


Построение оценки снизу для поиска min и max -- 2/4 Каждый шаг произвольной программы, решающей эту задачу, характеризуется 4 множествами элементов массива (A, B, C, D): A = не участвовали в сравнениях B = во всех сравнениях были больше C = во всех сравнениях были меньше D = в одних сравнениях были больше, а в других — меньше
Описание слайда:
Построение оценки снизу для поиска 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 сравнений
Описание слайда:
Построение оценки снизу для поиска 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 сравнения
Описание слайда:
Построение оценки снизу для поиска 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))
Описание слайда:
Асимптотические оценки сложности Функции 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 из АА
Описание слайда:
Асимптотически оптимальная программа Программа А* называется асимптотически оптимальной (оптимальной по порядку сложности) в классе АА, если T(А*, n) = Ω(Т(А, n)) для любой другой программы A из АА

Слайд 25


Асимптотически оптимальная программа Если A* и B* -- оптимальные программы в классе АА, то T(А*, n) = Ω(Т(B*, n)) и T(В*, n) = Ω(Т(А*, n)) и T(А*, n) ~ Т(B*, n) Оптимальная асимптотическая сложность определена однозначно
Описание слайда:
Асимптотически оптимальная программа Если A* и B* -- оптимальные программы в классе АА, то T(А*, n) = Ω(Т(B*, n)) и T(В*, n) = Ω(Т(А*, n)) и T(А*, n) ~ Т(B*, n) Оптимальная асимптотическая сложность определена однозначно

Слайд 26


Заключение Сложность программы по времени и по памяти Основные понятия Сложность в худшем случае, сложность в среднем Оценка сложности для программы на языке Си Понятие оптимальной программы Пример доказательства оптимальности Асимптотическая сложность и оптимальность
Описание слайда:
Заключение Сложность программы по времени и по памяти Основные понятия Сложность в худшем случае, сложность в среднем Оценка сложности для программы на языке Си Понятие оптимальной программы Пример доказательства оптимальности Асимптотическая сложность и оптимальность

Слайд 27


Классы сложности задач Под «задачей» будем понимать набор из трех объектов: функция P(.), которую требуется вычислить функция измерения входных данных |.| функция измерения числа операций T(.,.) в алгоритме вычисления функции P(.)
Описание слайда:
Классы сложности задач Под «задачей» будем понимать набор из трех объектов: функция 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
Описание слайда:
Классы сложности задач Задача 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
Описание слайда:
Пример Рассмотрим следующие задачи: 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
Описание слайда:
Пример Можно доказать, что для |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)) – так как делить нужно в с раз более точно
Описание слайда:
Пример 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 -- очевидно
Описание слайда:
Пример 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 -- очевидно

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию