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

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

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

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

Ресурсы

Время

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

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

Космос

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

Другие

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

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

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

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

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

Невозможно подсчитать количество шагов алгоритма на всех возможных входах. Поскольку сложность обычно увеличивается с размером ввода, сложность обычно выражается как функция размера 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 ≠ NP, с практическим подтекстом, что наихудшие случаи проблем NP по сути трудно решить, т. Е. Требуются больше времени, чем любой разумный промежуток времени (десятилетия!) Для интересной длины ввода.

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

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

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

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

Квантовые вычисления

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

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

Сложность задачи (нижние оценки)

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

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

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

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

Решение некоторых проблем, обычно в компьютерной алгебре и вычислительной алгебраической геометрии , может быть очень большим. В таком случае сложность ограничивается снизу максимальным размером вывода, так как вывод должен быть записан. Например, система п полиномиальных уравнений степени д в п неизвестных может иметь до сложных решений, если число решений конечна (это теорема Безу ). Поскольку эти решения должны быть записаны, сложность этой проблемы равна. Для этой задачи известен алгоритм сложности , который, таким образом, может считаться асимптотически квазиоптимальным. ${\ 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 (нерешенная гипотеза), сложность каждой NP-полной проблемы равна любому положительному целому числу k . ${\ Displaystyle \ Omega (г (п)).}$ ${\ Displaystyle \ Omega (г (ч (п))).}$${\ Displaystyle \ Омега (п ^ {к}),}$

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

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

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

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

Смотрите также

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

использованная литература

• Арора, Санджив ; Барак, Боаз (2009), Вычислительная сложность: современный подход , Кембридж , ISBN 978-0-521-42426-4, Zbl  1193,68112
• Ду, Дин-Чжу; Ко, Кер-И (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