Книга: Разработка ядра Linux

Опасность, связанная со сложностью алгоритмов

Опасность, связанная со сложностью алгоритмов

Очевидно, что будет разумным избегать алгоритмов, которые масштабируются, как О(n!) или O(2?). Более того, замена алгоритма, который масштабируется, как O(n), алгоритмом, который масштабируется, как O(1), — это обычно серьезное улучшение. Тем не менее это не всегда так, и нельзя принимать решение вслепую, базируясь только на описании "большого-О". Вспомните, что в определении множества О(g(x)) фигурирует константа, на которую умножается значение функции g(x). Поэтому есть возможность, что алгоритм, который масштабируется, как O(1), будет выполняться в течение 3 часов. Следовательно, он будет выполняться всегда в течение 3 часов, независимо от количества входных данных, но это может оказаться дольше, по сравнению с алгоритмом, который масштабируется, как O(n), при небольшом количестве входных данных. При сравнении алгоритмов необходимо всегда принимать во внимание количество входных данных. Не стоит слепо оптимизировать для некоторого случайно выбранного варианта.

Оглавление книги