Об алг.сложности

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/Snyn7EqHJME
https://youtu.be/5P-I6RSQGtY (логарифм)
5

6. Master theorem

основная теорема о
рекуррентных оценках
СПбГУ, 2021

7. Основная теорема (Master theorem)

СПбГУ, 2021

8. Мастер-теорема. Упрощенно.

СПбГУ, 2021

9. Пример первого случая

СПбГУ, 2021

10. Пример второго случая

СПбГУ, 2021

11. Пример случая 3

СПбГУ, 2021

12. Задачи для отработки

СПбГУ, 2021

13. Недопустимые уравнения

СПбГУ, 2021

14. Практические примеры

MergeSort
Бинарный поиск
НОД
Быстрое возведение в степень
Умножение в столбик
Умножение Карацубы
СПбГУ, 2021

15. MergeSort

16. Бинарный поиск

17. Алгоритм Карацубы

СПбГУ, 2021

18. Быстрое умножение - Алгоритм Карацубы

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