Кратко — главное отличие.
- Оптимизация алгоритмического уровня меняет порядок роста сложности (асимптотику): $\mathcal{O}(f(n))\to \mathcal{O}(g(n))$ с существенно меньшим $g(n)$. При росте входа даёт выигрыш в порядки.
- Микрооптимизации меняют константу перед асимптотикой (низкоуровневые приёмы, убирают лишние действия). Они полезны только в «горячих» местах после профилирования; обычно дают небольшое ускорение (факторы порядка единиц, редко десятков).
Пример большой выгоды (несколько порядков):
- Случай: сортировка.
- Плохой алгоритм: сортировка вставками — $\mathcal{O}(n^2)$.
- Хороший: быстрая сортировка/сортировка слиянием — $\mathcal{O}(n\log n)$.
- Пусть $n=10^6$. Тогда
$$n^2=10^{12},n{\log }_{2}n\approx 10^6\cdot 20=2\cdot 10^7.$$ Отношение $\frac{10^{12}}{2\cdot 10^7}=5\cdot 10^4$ — выигрыш ≈ $5\cdot 10^4$ раз (порядки величины).
Другой частый пример: поиск элемента — линейный поиск $\mathcal{O}(n)$ против использования хеш-таблицы $\mathcal{O}(1)$ при множестве запросов — тоже даёт многократный выигрыш при больших $n$.
Пример бессмысленной микрооптимизации:
- Замена умножения на два на битовый сдвиг: вместо $x\ast 2$ писать $x<<1$.
- Оба варианта — $\mathcal{O}(n)$ при повторении $n$ раз; разница — только в константе.
- Пусть выполняется $n=10^8$ операций. Если $x\ast 2$ стоит условно «1» единицу времени, а $x<<1$ — «0.9», то
$$T_{\text{mul}}=1\cdot 10^8,T_{\text{shift}}=0.9\cdot 10^8,$$ выигрыш ≈ $1/0.9\approx 1.11$ (≈11%). На современных компиляторах/JIT такая замена зачастую вообще оптимизируется и не даёт никакой разницы. То же касается кэширования длины контейнера в цикле, ручной развёртки небольших функций и т.п. — до профилирования такие изменения чаще бесполезны или вредны для читаемости.
Краткие рекомендации:
- Сначала анализируйте сложность; если асимптотика не устраивает — меняйте алгоритм/структуру данных.
- Микрооптимизации делайте только после профилирования и там, где это действительно горяча точка.