Вычислительная сложность

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

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

Поскольку количество ресурсов, необходимых для запуска алгоритма, обычно зависит от размера входных данных, сложность обычно выражается как функция $n \to f (n)$ , где $n$ - размер входных данных, а $f (n)$ - либо сложность наихудшего случая (максимум количества ресурсов, необходимых для всех входов размера $n$ ) или сложность среднего случая (среднее количество ресурсов по всем входам размера $n$ ). Сложность времени обычно выражается как количество требуемых элементарных операций над входом размера $n$ , где предполагается, что элементарные операции занимают постоянное количество времени на данном компьютере и изменяются только с постоянным коэффициентом при выполнении на другом компьютере. Сложность пространства обычно выражается как объем памяти, необходимый алгоритму для ввода размера $n$ .

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

Ресурсы [ править ]

Время [ править ]

Чаще всего считается время. Когда термин «сложность» используется без уточнения, это обычно означает временную сложность.

Обычные единицы времени (секунды, минуты и т. Д.) Не используются в теории сложности, потому что они слишком зависят от выбора конкретного компьютера и развития технологий. Например, современный компьютер может выполнять алгоритм значительно быстрее, чем компьютер 1960-х годов; однако это не внутренняя особенность алгоритма, а, скорее, следствие технического прогресса в компьютерном оборудовании . Теория сложности стремится количественно оценить внутренние требования алгоритмов ко времени, то есть основные временные ограничения, которые алгоритм может установить на любом компьютере. Это достигается подсчетом количества элементарных операций.которые выполняются во время вычисления. Предполагается, что эти операции занимают постоянное время (то есть не зависят от размера ввода) на данной машине и часто называются шагами .

Пробел [ править ]

Еще один важный ресурс - это объем памяти компьютера, который необходим для работы алгоритмов.

Другое [ править ]

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

Для многих алгоритмов размер целых чисел, используемых во время вычислений, не ограничен, и нереально считать, что арифметические операции занимают постоянное время. Следовательно, временная сложность, обычно называемая битовой сложностью в этом контексте, может быть намного больше, чем арифметическая сложность. Например, арифметическая сложность вычисления определителя о наличии $п \times п$ целочисленной матрице является для обычных алгоритмов ( исключения Гаусса ). Битовая сложность тех же алгоритмов экспоненциальна по $n$ ${\ Displaystyle О (п ^ {3})}$ , потому что размер коэффициентов может экспоненциально расти во время вычисления. С другой стороны, если эти алгоритмы объединены с многомодульной арифметикой , битовая сложность может быть уменьшена до $O ~ ( n 4 )$ .

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

Сложность как функция размера ввода [ править ]

Для ясности в этом разделе рассматривается только временная сложность, но все относится (с небольшими изменениями) к сложности по отношению к другим ресурсам.

Невозможно подсчитать количество шагов алгоритма на всех возможных входах. Поскольку сложность обычно увеличивается с размером ввода, сложность обычно выражается как функция размера $n$ (в битах ) ввода, и, следовательно, сложность является функцией $n$ . Однако сложность алгоритма может сильно различаться для разных входных данных одного и того же размера. Поэтому обычно используются несколько функций сложности.

Сложность в худшем случае это максимум сложности по всем входам размера $п$ , а сложность в среднем случае представляет собой среднее значение сложности по всем входам размера $п$ (это имеет смысл, так как число возможных входов данных размер конечен). Как правило, когда термин «сложность» используется без дополнительных указаний, рассматривается временная сложность наихудшего случая.

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

Обычно сложно точно вычислить сложность наихудшего и среднего случая. Кроме того, эти точные значения не имеют практического применения, поскольку любое изменение компьютера или модели вычислений несколько изменит сложность. Более того, использование ресурсов не критично для малых значений $n$ , и это делает, что при малых $n$ простота реализации обычно более интересна, чем хорошая сложность.

По этим причинам обычно сосредотачиваются на поведении сложности при больших $n$ , то есть на ее асимптотическом поведении, когда $n$ стремится к бесконечности. Следовательно, сложность , как правило , выражается с помощью большого обозначения O .

Например, обычный алгоритм умножения целых чисел имеет сложность, заключающуюся в том, что существует такая константа , что умножение двух целых чисел, состоящих не более чем из $n$ цифр, может быть выполнено за время меньшее, чем эта граница является точной в том смысле, что наихудшее -случае сложность и сложность в среднем случае является это означает , что существует постоянные таким образом, что эти сложности больше , чем The поразрядной не появляется в этих сложностях, так как изменение поразрядного изменяет только константу и ${\ Displaystyle О (п ^ {2}),}$ ${\ displaystyle c_ {u}}$ ${\ displaystyle c_ {u} n ^ {2}.}$ ${\ displaystyle \ Omega (п ^ {2}),}$ ${\ displaystyle c_ {l}}$ ${\ displaystyle c_ {l} n ^ {2}.}$ ${\ displaystyle c_ {u}}$ ${\ displaystyle c_ {l}.}$

Модели вычислений [ править ]

Оценка сложности зависит от выбора модели вычислений , которая заключается в определении основных операций, которые выполняются за единицу времени. Когда модель вычислений не указана явно, это обычно подразумевается как многолента-машина Тьюринга .

Детерминированные модели [ править ]

Детерминированная модель вычислений представляет собой модель вычисления таким образом, что последовательные состояния машины и операции должны быть выполнены полностью определяются предыдущим состоянием. Исторически первыми детерминированными моделями были рекурсивные функции , лямбда-исчисление и машины Тьюринга . Модель машин с произвольным доступом (также называемых RAM-машинами) также широко используется как более близкий аналог реальным компьютерам .

Когда модель вычислений не указана, обычно предполагается, что это многоленточная машина Тьюринга . Для большинства алгоритмов временная сложность на многопленочных машинах Тьюринга такая же, как и на RAM-машинах, хотя может потребоваться некоторая осторожность в том, как данные хранятся в памяти, чтобы получить эту эквивалентность.

Недетерминированное вычисление [ править ]

В недетерминированной модели вычислений , такой как недетерминированные машины Тьюринга , некоторые варианты могут быть сделаны на некоторых этапах вычислений. В теории сложности каждый рассматривает все возможные варианты одновременно, а недетерминированная временная сложность - это время, необходимое, когда всегда делается лучший выбор. Другими словами, считается, что вычисления выполняются одновременно на таком количестве (идентичных) процессоров, сколько необходимо, а недетерминированное время вычислений - это время, затрачиваемое первым процессором, который завершает вычисление. Этот параллелизм частично поддается квантовым вычислениям через наложенные запутанные состояния при выполнении определенных квантовых алгоритмов , таких как, например,Факторизация Шора только маленьких целых чисел (по состоянию на март 2018 г . ^{[Обновить]}: 21 = 3 × 7).

Даже когда такая модель вычислений еще не реалистична, она имеет теоретическое значение, в основном связанное с проблемой P = NP , которая ставит под сомнение идентичность классов сложности, образованных путем принятия «полиномиального времени» и «недетерминированного полиномиального времени» как минимум верхние границы. Моделирование NP-алгоритма на детерминированном компьютере обычно занимает «экспоненциальное время». Проблема относится к классу сложности NP , если она может быть решена за полиномиальное время на недетерминированной машине. Проблема является NP-полной, если, грубо говоря, она находится в NP и не легче любой другой NP-задачи. Многие комбинаторные задачи, такие как задача о ранце ,проблема коммивояжера, и проблема булевой выполнимости являются NP-полными. Для всех этих проблем самый известный алгоритм имеет экспоненциальную сложность. Если бы любая из этих проблем могла быть решена за полиномиальное время на детерминированной машине, то все проблемы NP также могли бы быть решены за полиномиальное время, и одна из них имела бы P = NP. По состоянию на 2017 год ^{[Обновить]}обычно высказывается предположение, что P with NP, с практическим подтекстом, что наихудшие случаи проблем NP по сути трудно решить, т. Е. Требуются больше времени, чем любой разумный промежуток времени (десятилетия!) Для интересной длины ввода.

Параллельные и распределенные вычисления [ править ]

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

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

Таким образом, основная сложная проблема заключается в разработке таких алгоритмов, чтобы произведение времени вычисления на количество процессоров было как можно ближе ко времени, необходимому для того же вычисления на одном процессоре.

Квантовые вычисления [ править ]

Квантовый компьютер представляет собой компьютер , чья модель вычислений базируется на квантовой механике . Тезис Черча-Тьюринга относится к квантовым компьютерам; то есть каждая проблема, которую может решить квантовый компьютер, также может быть решена машиной Тьюринга. Однако некоторые проблемы теоретически могут быть решены с гораздо меньшей временной сложностью, используя квантовый компьютер, а не классический компьютер. На данный момент это чисто теоретически, поскольку никто не знает, как построить эффективный квантовый компьютер.

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

Сложность задачи (нижняя граница) [ править ]

Сложность проблемы - это максимальная сложность алгоритмов, которые могут решить проблему, включая неизвестные алгоритмы. Таким образом, сложность проблемы не превышает сложности любого алгоритма, решающего эти проблемы.

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

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

Для решения большинства проблем требуется прочитать все входные данные, для чего обычно требуется время, пропорциональное размеру данных. Таким образом, такие задачи имеют сложность, по крайней мере, линейную , то есть с использованием больших омега-обозначений сложность ${\ Displaystyle \ Omega (п).}$

Решение некоторых проблем, обычно в компьютерной алгебре и вычислительной алгебраической геометрии , может быть очень большим. В таком случае сложность ограничивается снизу максимальным размером вывода, так как вывод должен быть записан. Например, система п полиномиальных уравнений степени д в п неизвестных может иметь до сложных решений, если число решений конечна (это теорема Безу ). Поскольку эти решения должны быть записаны, сложность этой проблемы равна. Для этой задачи известен алгоритм сложности , который, таким образом, можно рассматривать как асимптотически квазиоптимальный. ${\ displaystyle d ^ {n}}$ ${\ displaystyle \ Omega (d ^ {n}).}$ ${\ Displaystyle d ^ {О (п)}}$

Нелинейная нижняя граница известна для количества сравнений, необходимых для алгоритма сортировки . Таким образом, лучшие алгоритмы сортировки являются оптимальными, так как их сложность равна. Эта нижняя граница является результатом того факта, что существует $n$ $!$ способы заказа $n$ объектов. Поскольку каждое сравнение разбивается на две части, этот набор из $n$ $!$ заказы, количество $N$ сравнений, которые необходимы для различения всех заказов должны проверить , что означает , по формуле Стирлинга . ${\ Displaystyle \ Omega (п \ журнал п)}$ ${\ Displaystyle O (п \ журнал п).}$ ${\ displaystyle 2 ^ {N}> п !,}$ ${\ Displaystyle N = \ Omega (п \ журнал п),}$

Стандартный метод получения нижних оценок сложности состоит в сведении одной проблемы к другой. Точнее, предположим, что можно закодировать проблему $A$ размера $n$ в подзадачу размера $f (n)$ задачи $B$ , и что сложность $A$ равна Без потери общности, можно предположить, что функция $f$ увеличивается с $n$ и имеет обратную функцию $h$ . Тогда сложность задачи $B$ равна. Этот метод используется для доказательства того, что если P ≠ NP ${\ Displaystyle \ Omega (г (п)).}$ $\Omega (g(h(n))).$ (нерешенная гипотеза), сложность любой NP-полной задачи равна любому положительному целому числу $k$ . $\Omega (n^{k}),$

Использование в разработке алгоритмов [ править ]

Оценка сложности алгоритма является важной частью разработки алгоритма , так как это дает полезную информацию о ожидаемой производительности.

Распространено заблуждение, что оценка сложности алгоритмов станет менее важной в результате закона Мура , который утверждает экспоненциальный рост мощности современных компьютеров . Это неправильно, потому что такое увеличение мощности позволяет работать с большими входными данными ( big data ). Например, если кто-то хочет отсортировать в алфавитном порядке список из нескольких сотен записей, такой как библиография книги, любой алгоритм должен работать менее чем за секунду. С другой стороны, для списка из миллиона записей (например, телефонных номеров большого города) элементарные алгоритмы, требующие $O(n^{2})$ Для сравнения потребуется триллион сравнений, на что потребуется около трех часов при скорости 10 миллионов сравнений в секунду. С другой стороны, быстрая сортировка и сортировка слиянием требуют только сравнений (как средняя сложность для первого, так и сложность наихудшего для второго). Для $n$ $= 1 000 000$ это дает примерно 30 000 000 сравнений, что займет всего 3 секунды при 10 миллионах сравнений в секунду. $n\log _{2}n$

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

См. Также [ править ]

Вычислительная сложность математических операций

Ссылки [ править ]

Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Кембридж , ISBN 978-0-521-42426-4, Zbl 1193,68112
Ду, Дин-Чжу; Ко, Кер-I (2000), Теория вычислительной сложности , John Wiley & Sons , ISBN 978-0-471-34506-0
Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , У. Х. Фриман , ISBN 0-7167-1045-5
Голдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press
ван Леувен, Ян , изд. (1990), Справочник по теоретической информатике (том A): алгоритмы и сложность , MIT Press , ISBN 978-0-444-88071-0
Пападимитриу, Христос (1994), Вычислительная сложность (1-е изд.), Аддисон Уэсли, ISBN 0-201-53082-1
Сипсер, Майкл (2006), Введение в теорию вычислений (2-е изд.), США: Thomson Course Technology , ISBN 0-534-95097-3