Ocenka-slozhnosti-algoritma.pptxOcenka-slozhnosti-algoritma.pptx

Ocenka-slozhnosti-algoritma.pptxOcenka-slozhnosti-algoritma.pptx

1. Оценка сложности алгоритма Часть 1: Основы классификации, классы алгоритмов

2. Больше, чем просто "быстро" Оптимизация ресурсов Эффективный алгоритм решает задачу за секунды вместо часов, экономя процессорное время и память. Масштабируемость Предсказание производительности при росте данных от тысяч до миллионов элементов. Выбор решения Обоснованный выбор оптимального алгоритма для текущих и будущих потребностей проекта.

3. Что такое сложность алгоритма? Временная сложность Мера количества элементарных операций в зависимости от размера входных данных n . Сравнения и присваивания Арифметические операции Чтение из памяти Оцениваем рост операций, а не время в секундах. Пространственная сложность Мера объема памяти, необходимой для выполнения алгоритма. Входные данные Промежуточные результаты Переменные и рекурсивные вызовы Зависит от размера n входных данных.

4. Как измерить "большую" сложность? О-нотация (Big O notation) Формальный способ описания верхней границы скорости роста функции при больших n . Игнорирование констант 5n² + 3n + 10 → O(n²) При больших n доминирует член n² Наихудший случай О-нотация описывает worst-case, гарантируя верхнюю границу производительности. Универсальный язык Позволяет сравнивать алгоритмы независимо от языка программирования и железа.

5. От константы до логарифма 01 O(1) – Константное время Количество операций не зависит от n . Идеальный случай. Пример: Доступ к элементу массива по индексу array[5]. 02 O(log n) – Логарифмическое время Время растет очень медленно. Размер задачи уменьшается в несколько раз на каждой итерации. Пример: Бинарный поиск в отсортированном массиве. Для 1024 элементов нужно максимум 10 сравнений.

6. От линейного до квадратичного O(n) – Линейное время Время пропорционально n . При n = 1000 → 1000 операций. Поиск в несортированном массиве, суммирование элементов. O(n log n) – Линейно-логарифмическое Эффективный класс для сортировки. Для n = 1000 → ~10000 операций. Quick Sort, Merge Sort, Heap Sort. O(n²) – Квадратичное время Время пропорционально n² . При n = 1000 → 1 000 000 операций. Bubble Sort, два вложенных цикла по n элементов.

7. Экспоненциальный рост и выше O(2ⁿ) – Экспоненциальное время Время растет экспоненциально. Непригодны для n > 20-40. При n = 20: 2²⁰ > 1 млн операций При n = 40: 2⁴⁰ > 1 трлн операций Пример: Наивный алгоритм Фибоначчи, поиск всех подмножеств. O(n!) – Факториальное время Худший класс сложности. Непригоден при n > 10-15. 5! = 120 10! = 3 628 800 20! = астрономическое число Пример: Задача коммивояжера (полный перебор), все перестановки. ⚠️ Эти алгоритмы быстро выходят за рамки возможностей даже самых мощных компьютеров.

8. Как растет 'Большое О' 1 O(1) Горизонтальная линия 2 O(log n) Медленный рост 3 O(n) Прямая линия 4 O(n²) Крутая парабола 5 O(2ⁿ) Вертикальный взлет Для больших n полиномиальные алгоритмы гораздо предпочтительнее экспоненциальных. Правильный выбор — разница между мгновенным ответом и бесконечным ожиданием.

9. Факторы воздействия Что влияет на временную сложность? Размер входных данных (n) Главный фактор. Как ведет себя алгоритм при очень большом n ? Вложенные циклы Один цикл → O(n). Два вложенных → O(n²). Три → O(n³). Рекурсия Глубина и количество вызовов определяют сложность. Без оптимизации может быть очень дорогой. Структуры данных Хеш-таблица: поиск O(1). Связный список: поиск O(n). Выбор критичен.

10. Разрешимые задачи и "трудные" проблемы Классы задач P и NP Класс P Задачи, решаемые за полиномиальное время O(nᵏ). Считаются "легко решаемыми". Примеры: сортировка, поиск, умножение матриц. Класс NP Задачи, решение которых можно проверить за полиномиальное время. Найти решение может быть очень сложно. Примеры: задача коммивояжера, SAT. P = NP? — одна из семи проблем тысячелетия. Премия: $1 000 000. Если P=NP, все задачи с быстро проверяемым решением можно быстро решить.

11. Задачи, которые невозможно решить Неразрешимые задачи (Undecidable Problems) Определение неразрешимых задач: задачи, для которых не существует алгоритма, способного решить их для всех возможных входных данных за конечное время. Это фундаментальное математическое ограничение, а не вопрос вычислительной мощности. Исторический контекст: концепция сформулирована Аланом Тьюрингом в 1936 году. Классический пример - Проблема остановки (Halting Problem) Задача: создать универсальный алгоритм для определения, завершится ли любая программа или будет работать бесконечно. Тьюринг математически доказал невозможность такого алгоритма. Практическое значение Понимание пределов вычислений Необходимость поиска альтернативных подходов: приближенные решения, эвристические алгоритмы, частичные решения

12. Фундамент эффективности Заключение к Части 1 Что мы изучили: Критичность оценки сложности для масштабируемых программ Временная и пространственная сложность О-нотация как стандартный инструмент асимптотической оценки Основные классы временной сложности от O(1) до O(n!) Факторы влияния: размер данных, циклы, рекурсия Классы задач P и NP, неразрешимые задачи Практическое значение: Не просто теория, а основа профессионального мышления разработчика Обоснованные архитектурные решения Выбор оптимальных структур данных Создание эффективного ПО для будущего