Нотация “О-большое”
“О-большое” описывает, насколько быстро работает алгоритм.
- не сообщает скорость в секундах, а позволяет сравнить количество операций.
- указывает, насколько быстро возрастает время выполнения алгоритма.
- описывает худший возможный случай (максимальное количество операций, которое потребуется).
Типичные примеры “О-большого” в порядке убывания скорости выполнения:
- O(log n), или логарифмическое время. Пример: бинарный поиск.
- O(n), или линейное время. Пример: простой поиск.
- O(n * log n). Пример: эффективные алгоритмы сортировки – быстрая сортировка.
- O(n ** 2). Пример: медленные алгоритмы сортировки – сортировка выбором, пузырьком.
- O(n!). Пример: очень медленные алгоритмы – задача о коммивояжере.
📂 Алгоритмы | Последнее изменение: 07.02.2024 20:18