Здравствуйте, MTD, Вы писали:

S>>Причем Кнут — не понятно.

MTD>При том, что Кнут не учитывал, как алгоритмы выполняются на современном железе, такая теория в вакууме. Знать надо, но каждый раз надо думать, а слепо верить в О.

Я бы сказал "каждый раз надо измерять", а не "думать". "Думать" оно надо, но не это ключевое.

А "неучёт на современном железе" это специфика не только Кнута. Я навскидку сейчас посмотрел Кормена, Сиену, Седжвика — нигде не упоминается — по крайней мере нет ни в оглавлении, ни в предметном указателе. Поэтому следует полагать, что им в пару обязательно читать "Computer achitecture: a quantitative approach" или аналог.

Ещё Вы почему-то распространяете паразитную логическую связь "алгоритмы, сложность -> Кнут". Кнут — фундамент и историческая база, но сейчас его использовать в качестве абсолюта уже поздновато.

S>>Он не утверждает обратного.

MTD>Для оценки скорости алгоритмов предлагается использовать его асиптотику — это не всегда верно. Например, у бинарного дерева и упорядоченного массива асимптотика поиска одинакова — логарифм. Значит ли это, что они одинаково эффективны? Нет, ведь дерево может быть размазано по памяти из-за этого возникнут постоянные промахи в кеш и упорядоченный массив окажется в разы эффективней. Рассматривается это у Кнута? Нет, вот о том и речь.

Реальный мир надо всегда учитывать. Где-то алгоритм в 100 раз быстрее на RAM, но в 2 раза прожорливее по объёму памяти затормозится из-за трэшинга свопа. Где-то очень эффективная обычно сортировка станет вдруг медленнее пузырька из-за того, что сравнение в 1000 раз дороже обмена.

Вы читая Кнута почему-то смотрите только на выводы, а не на проведённый им анализ. А ведь то, чему он учит — это именно анализировать от основ. И при всём при этом не знаете никого, кроме Кнута... просто пугаете этим.