В теории сложности вычислений , асимптотическая вычислительная сложность является использованием асимптотического анализа для оценки вычислительной сложности алгоритмов и вычислительных задач , обычно связанных с использованием в большой нотации O .
Сфера
Что касается вычислительных ресурсов , обычно оцениваются асимптотическая временная сложность и асимптотическая пространственная сложность . Другое асимптотически оцененное поведение включает сложность схемы и различные показатели параллельных вычислений , такие как количество (параллельных) процессоров.
С новаторской 1965 статьи Хартманисом и Стернсом [1] и в 1979 году книги Майкла Garey и Дэвид С. Джонсон на NP-полноте , [2] термин « вычислительная сложность » (алгоритмы) становится обычно называют асимптотической вычислительной сложностью.
Кроме того, если не указано иное, термин «вычислительная сложность» обычно относится к верхней границе асимптотической вычислительной сложности алгоритма или проблемы, которая обычно записывается в терминах нотации большого O, например.Другими типами (асимптотических) оценок вычислительной сложности являются нижние оценки ( обозначение « Большой Омеги »; например, Ω ( n )) и асимптотически точные оценки, когда асимптотические верхняя и нижняя границы совпадают (записанные с использованием « большой теты »; например, Θ ( п журнал п )).
Еще одно негласное предположение состоит в том, что рассматривается наихудший анализ вычислительной сложности, если не указано иное. Альтернативный подход - вероятностный анализ алгоритмов .
Типы рассматриваемых алгоритмов
В большинстве практических случаев обсуждаются детерминированные алгоритмы или рандомизированные алгоритмы , хотя теоретическая информатика также рассматривает недетерминированные алгоритмы и другие продвинутые модели вычислений .
Смотрите также
Рекомендации
- ^ Hartmanis, J .; Стернс, Р. Э. (1965). «О вычислительной сложности алгоритмов» . Труды Американского математического общества . 117 : 285–306. DOI : 10.1090 / S0002-9947-1965-0170805-7 .
- ^ Майкл Гэри и Дэвид С. Джонсон : Компьютеры и несговорчивость: Руководство по теории NP-полноты. Нью-Йорк: WH Freeman & Co., 1979.