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

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

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

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

Ресурсы

Время

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

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

Битовая сложность

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

Космос

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

Коммуникация

Основная статья: сложность связи

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

Другие

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

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

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

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

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

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

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

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

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

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

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

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

Модели вычислений

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

Детерминированные модели

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

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

Недетерминированные вычисления

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

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

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

Основные статьи: Параллельные вычисления и Распределенные вычисления

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Ссылки

• Арора, Санджив ; Барак, Воаз (2009), Сложность вычислений: современный подход , Кембридж , ISBN  978-0-521-42426-4 , Збл   1193,68112
• Калуд, Кристиан (1988), Теории вычислительной сложности , Elsevier , стр. 487, ISBN  9780444703569
• Ду, Дин-Чжу; Ко, Кер-И (2000), Теория вычислительной сложности , John Wiley & Sons , ISBN  978-0-471-34506-0 , ISSN   0167-5060
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Серия книг по математическим наукам (1-е изд.). Нью-Йорк: WH Freeman and Company . ISBN  9780716710455 . МР   0519066 . OCLC   247570676 .
• Гольдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press
• ван Леувен, Ян , изд. (1990), Справочник по теоретической информатике (том A): алгоритмы и сложность , MIT Press , ISBN  978-0-444-88071-0
• Пападимитриу, Христос (1994), Вычислительная сложность (1-е изд.), Аддисон Уэсли, ISBN  0-201-53082-1
• Сипсер, Майкл (2006), Введение в теорию вычислений (2-е изд.), США: Технология курса Thomson , ISBN  0-534-95097-3