Вычислительная сложность: различия между версиями

(викификация)
|место = М.
|издательство = [[Вильямс (издательство)|«Вильямс»]]
}}</ref>. Вместе с тем и понятие «малости» входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как [[алгоритм целочисленного умножения]], асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее «эффективных» алгоритмов. Другой пример — [[Фибоначчиева куча|фибоначчиевы кучи]], несмотря на асимптотическую эффективность, с практической точки зрения программная сложность реализации и большие значения констант в формулах времени работы делают их менее привлекательными, чем обычные [[Двоичная куча|бинарные пирамидыдеревья]]<ref name='cormen'/>.
{{цитата|автор=А. А. Зыков|1=Если решение некоторой задачи для n-вершинного графа при одном алгоритме занимает время (число шагов) порядка n<sup>C</sup>, а при другом — порядка n+n!/C, где C — постоянное число, то согласно «полиномиальной идеологии» первый алгоритм практически эффективен, а второй — нет, хотя, например, при С=10<sup>(10<sup>10</sup>)</sup> дело обстоит как раз наоборот.<ref>{{книга
|автор = А. А. Зыков