Асимптотическая вычислительная сложность

В вычислительной сложности теории асимптотическая вычислительная сложность — это использование асимптотического анализа для оценки вычислительной сложности алгоритмов и вычислительных задач , обычно связанное с использованием большой нотации O.

Объем

Что касается вычислительных ресурсов , асимптотическая временная сложность и асимптотическая пространственная сложность обычно оцениваются . Другое асимптотически оцениваемое поведение включает сложность схемы и различные показатели параллельных вычислений , такие как количество (параллельных) процессоров.

Со времени новаторской статьи Юриса Хартманиса и Ричарда Стернса в 1965 году. и книга Майкла Гэри и Дэвида С. Джонсона 1979 года о NP-полноте , Термин « вычислительная сложность » (алгоритмов) стал обычно называть асимптотической вычислительной сложностью.

Кроме того, если не указано иное, термин «вычислительная сложность» обычно относится к верхней границе асимптотической вычислительной сложности алгоритма или задачи, которая обычно записывается в терминах большой записи О, например. $O(n^{3}).$ Другими типами (асимптотических) оценок сложности вычислений являются нижние границы (обозначение « Большая Омега »; например, Ω( n )) и асимптотически точные оценки, когда асимптотические верхние и нижние границы совпадают (записанные с использованием « большой Теты »; например, Θ( n log n )).

Еще одно неявное предположение состоит в том, что анализ вычислительной сложности в наихудшем случае находится под вопросом, если не указано иное. Альтернативный подход — вероятностный анализ алгоритмов .

Типы рассматриваемых алгоритмов

В большинстве практических случаев детерминированные алгоритмы или рандомизированные алгоритмы обсуждаются , хотя теоретическая информатика также рассматривает недетерминированные алгоритмы и другие продвинутые модели вычислений .

См. также

• Асимптотически оптимальный алгоритм