Похожие презентации:
Об алг.сложности
1. Алгоритмическая сложность
По-простому1
2. Оценка производительности алгоритмов
Для оценки производительности алгоритмовможно использовать разные подходы.
Самый бесхитростный - просто запустить
каждый алгоритм на нескольких задачах и
сравнить время исполнения.
Другой способ - оценить время исполнения
через символ O(n)
2
3. Что означает символ O(n) ?
Оценки времени исполнения3
4. Что означает символ O(n) ?
Если оба алгоритма, например, O ( n*log n ), то это отнюдьне значит, что они одинаково эффективны.
Символ О не учитывает константу, то есть первый может
быть, скажем в 1000 раз эффективнее. Это значит лишь
то, что время (или требуемая память или что-либо еще,
что надо оценить) возрастает приблизительно c такой же
скоростью, как функция n*log n
Если в программе одна функция выполняется O(n) раз например, умножение, а сложение - O(n^2) раз, то общая
сложность - O(n^2), так как n^2 возрастает быстрее.
4
5. Про O(n) видео от Сириуса
https://youtu.be/Snyn7EqHJMEhttps://youtu.be/5P-I6RSQGtY (логарифм)
5
6. Master theorem
основная теорема орекуррентных оценках
СПбГУ, 2021
7. Основная теорема (Master theorem)
СПбГУ, 20218. Мастер-теорема. Упрощенно.
СПбГУ, 20219. Пример первого случая
СПбГУ, 202110. Пример второго случая
СПбГУ, 202111. Пример случая 3
СПбГУ, 202112. Задачи для отработки
СПбГУ, 202113. Недопустимые уравнения
СПбГУ, 202114. Практические примеры
MergeSortБинарный поиск
НОД
Быстрое возведение в степень
Умножение в столбик
Умножение Карацубы
СПбГУ, 2021
15. MergeSort
16. Бинарный поиск
17. Алгоритм Карацубы
СПбГУ, 202118. Быстрое умножение - Алгоритм Карацубы
19. Источники
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.Алгоритмы: построение и анализ, 2-е издание.стр. 110
М.: Издательский дом "Вильямс", 2005. ISBN 5-84590857-4
Кнут Д. Искусство программирования. — 3-е изд. — М.:
Вильямс, 2007. — Т. 2. Получисленные алгоритмы. —
832 с. — ISBN 0-201-89684-2.
https://ru.qaz.wiki/wiki/Master_theorem_%28analysis_of_al
gorithms%29
http://algolist.ru/olimp/sor_prb.php
https://habr.com/ru/post/281675/
СПбГУ, 2021