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

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

CS>>Приводится случай когда O(N) lookup кроет O(1) как бык овцу[/url].

MTD>Поэтому Кнута и ко надо читать с осторожностью — хоть парни и толковые, но инфа несколько устарела, если не учитывать устройство современного процессора (всякие кеши, предсказание переходов), то можно легко напороться на то, что алгоритм с худшей асимптоматикой внезапно уделывает алгоритм с хорошей.
Асимптотика описывает поведение при стремлении переменной к чему-то. В применении к сложностям алгоритмов рассматривается характер поведения при увеличении переменной, или стремлении к бесконечности. Кроме того, O(f(n)) — это верхняя оценка по определению, которая лишь указывает что существует константа и такое n0, что рост сложности алгоритма при n >= n0 будет соответствовать некоторой модели с точностью до этих констант. То есть, асимптотика не предназначена для описывания нижних оценок на малых n.

Причем Кнут — не понятно. Он не утверждает обратного.