Полный курс: оценка сложности алгоритмов. Нотация Big O

• Для чего нужна оценка сложности алгоритмов

• Причины изучения нотации Big O

• Что такое Математическая функция простыми словами

• Описания процесса из реальной жизни с помощью математической функции

• Сложность алгоритма (вычислительная сложность алгоритма, сложность работы алгоритма).

• Виды сложности алгоритмов

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

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

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

• Временная функция сложности алгоритмов

• Сложность в лучшем случае.

• Сложность в худшем случае.

• Порядок функции.

• Сравнение порядков функций.

• Нахождение функции с меньшим порядком.

• Нотация О большое (запись О большое, Big O, сложность алгоритма О)

• Объяснение нотации Big O

• Сравнение функций с помощью Big O

• Цель оценки сложности

• Константы и сложность

• Проблемы нотации Big O

• Арифметические операции с Big O

• Классификация сложностей (порядок сложности алгоритма, классы сложности алгоритмов, виды функций сложности алгоритмов)

• Константная сложность алгоритма

• Логарифмическая сложность алгоритма

• Сублинейная сложность алгоритма

• Линейная сложность алгоритма (сложность алгоритма N, сложность алгоритма O(N))

• Линейно-логарифмическая сложность алгоритма

• Квадратичная сложность алгоритма

• Экспоненциальная сложность алгоритма

• Факториальная сложность алгоритма

• Некоторые типичные функции сложностей и как с ними работать.

• Арифметическая прогрессия.

• Геометрическая прогрессия.

• Логарифм.

• Факториал.

• Сложность последовательных операций

• Сложность вложенных операций

• Логарифмическая сложность алгоритма

• Алгоритм двоичного поиска

• Внутренние алгоритмы работы со строками и их влияние на конечную сложность

• Временная сложность работы рекурсивной функции (сложность рекурсивного алгоритма)

• Что такое амортизационный анализ и для чего он нужен

• Амортизационный анализ методом агрегации

• Сложность по памяти (пространственная сложность алгоритма, объемная сложность алгоритма) обычной функции

• Сложность по памяти рекурсивной функции

Подробные примеры анализа сложности алгоритмов, которые позволяют закрепить понятие сложности алгоритма и подходы к ее оценке.