Нотация «о большое» (Big O notation) описывает верхнюю границу сложности алгоритма — как быстро увеличивается время выполнения или объем памяти в зависимости от размера входных данных. Используется для сравнения эффективности алгоритмов.
Основные типы сложности по нотации «о большое»:
| Нотация | Описание | Пример |
|---|---|---|
| O(1) | Постоянное время | Доступ к элементу массива по индексу |
| O(log n) | Логарифмическое время | Бинарный поиск |
| O(n) | Линейное время | Поиск элемента в несортированном списке |
| O(n log n) | Лине-логарифмическое | Быстрая сортировка (в среднем) |
| O(n²) | Квадратичное время | Сортировка пузырьком |
| O(2ⁿ) | Экспоненциальное время | Решение задачи о коммивояжере методом грубой силы |
Пример анализа сложности:
javascriptНотация «о большое» (Big O notation) описывает верхнюю границу сложности алгоритма — как быстро увеличивается время выполнения или объем памяти в зависимости от размера входных данных. Используется для сравнения эффективности алгоритмов.
Основные типы сложности по нотации «о большое»:
| Нотация | Описание | Пример |
|---|---|---|
| O(1) | Постоянное время | Доступ к элементу массива по индексу |
| O(log n) | Логарифмическое время | Бинарный поиск |
| O(n) | Линейное время | Поиск элемента в несортированном списке |
| O(n log n) | Лине-логарифмическое | Быстрая сортировка (в среднем) |
| O(n²) | Квадратичное время | Сортировка пузырьком |
| O(2ⁿ) | Экспоненциальное время | Решение задачи о коммивояжере методом грубой силы |
Пример анализа сложности:
javascriptRegister or sign in to get access to full answers for all questions from the question bank.