Вот в этом и "теоретичность" этих оценок, что учитывают только строго оговорённые вещи типа количества сравнений, а на остальные забивают
Нет, вы ошибаетесь. Можно посчитать сложность по количеству сравнений. Можно - по количеству копирований. Можно - по количеству операций с адресами и указателями. Что хотите, на ваш выбор.
Но во-первых, редко когда получается оценка сильно хуже, чем по сравнениям. Когда получается, об этом начинают резко громко вопить. Такие случаи известны в мире алгоритмов.
И во-вторых, часто сравнение оказывается самой дорогостоящей операцией. Например, когда вы сортируете строки, то каждое сравнение строк - это отдельный цикл
(Кстати, если строки длины
но самих строк
что обычно и имеет место, то можно сначала их как-то "умно похэшировать" с хэш-функцией, примерно сохраняющей порядок.) Иногда ещё дорогостоящей операцией является копирование, но в сортировке можно этого избежать: сортировать указатели.
Пример: медленные по записи устройства типа flash, hdd.
Это не новость и не секрет, и в таких ситуациях разрабатывают специальные алгоритмы и структуры данных. Можно просто частично кэшировать вычисления в более быстродействующей памяти.
И потому реально представляют интерес не только оценки количества сравнений, но и количество перестановок, и особенно для почти отсортированных входных данных (такие на практике встречаются достаточно часто).
Вообще если данные почти отсортированы, то лучше применять другую стратегию: не добавлять ворох мусора, а потом снова сортировать; а сразу при добавлении новых данных insert-ить их в нужное место, сохраняя отсортированность. Впрочем, опять же, это вариант, а надо сравнивать конкретику.
С другой стороны, знать асимптотику применённого алгоритма всё равно полезно, как только данные вылезут за кэши
Скорее, учитывать кэши необходимо и для понимания profile, и для разработки алгоритмов, но асимптотика - это тот язык, на котором вы должны разговаривать в любом случае.
И всё равно, без аппаратного умножителя самый быстрый алгоритм будет именно линейный: крутить циклы
Странно, ну да ладно. Раз вы говорите, что три сложения медленнее, чем десять вычитаний, то наверное, вы проверяли.