Основные классы
- O(1) — константное время. Доступ к массиву по индексу, хеш-таблица. Не зависит от n
- O(log n) — логарифмическое. Бинарный поиск. Быстро даже для миллиардов элементов
- O(n) — линейное. Перебор массива. Удвоили n — удвоили время
- O(n log n) — Merge Sort, QuickSort (средний случай)
- O(n²) — вложенные циклы. Bubble Sort. Непригоден при n > 10000
- O(2ⁿ) — экспоненциальное. Перебор всех подмножеств. Слишком медленно
На практике
SQL-запрос без индекса — O(n). С индексом — O(log n). Именно поэтому индексы в 100 раз важнее оптимизации кода приложения.