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

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

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

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

Ресурсы

Время

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

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

Космос

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

Другие

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

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

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

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

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

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

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

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

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

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

Например, обычный алгоритм для целых чисел умножение имеет сложность ${ 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 также могли бы быть решены за полиномиальное время, и одна была бы P = NP. По состоянию на 2017 год^{[Обновить]} обычно предполагают, что П ≠ НП, с практическим подтекстом, что наихудшие случаи проблем NP по своей сути трудноразрешимы, т. е. требуются больше времени, чем любой разумный промежуток времени (десятилетия!) для ввода интересной длины.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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