В Algorithmica хорошо разобрали, почему классическая оценка сложности всё хуже отражает реальную производительность на современном железе.
Раньше модель была довольно логичной: процессор выполняет инструкции почти последовательно, у каждой есть своя стоимость, а значит можно примерно оценить время работы алгоритма количеством операций.
Потом всё упростили до асимптотики. Например, вместо точного количества операций в умножении матриц мы просто говорим
O(n³) и игнорируем константы. Для сравнения алгоритмов на больших данных это удобно.Но современные CPU устроены намного сложнее: кэши, конвейеры, параллельное выполнение инструкций, SIMD, prefetching, память с разной задержкой.
Поэтому два алгоритма с одинаковым
O(n) могут отличаться по скорости в разы.А иногда алгоритм с формально «хуже» сложностью на реальных размерах данных оказывается быстрее.
Хорошая серия для тех, кто хочет перейти от «у этого O(n), значит быстро» к пониманию того, как код реально выполняется процессором.
en.algorithmica.org/hpc/complexity/
@machinelearning_books