Нотация «о большое» (Big O notation) описывает верхнюю границу сложности алгоритма — как быстро увеличивается время выполнения или объем памяти в зависимости от размера входных данных. Используется для сравнения эффективности алгоритмов.
Основные типы сложности по нотации «о большое»:
| Нотация | Описание | Пример |
|---|---|---|
| O(1) | Постоянное время | Доступ к элементу массива по индексу |
| O(log n) | Логарифмическое время | Бинарный поиск |
| O(n) | Линейное время | Поиск элемента в несортированном списке |
| O(n log n) | Лине-логарифмическое | Быстрая сортировка (в среднем) |
| O(n²) | Квадратичное время | Сортировка пузырьком |
| O(2ⁿ) | Экспоненциальное время | Решение задачи о коммивояжере методом грубой силы |
Пример анализа сложности:
javascriptНотация «о большое» позволяет абстрагироваться от конкретной машины и константных множителей, фокусируясь на росте сложности при увеличении размера данных. Это помогает выбрать наиболее подходящий алгоритм для решения задачи, особенно при работе с большими объемами данных.