В информатике вычислительная сложность или просто сложность алгоритма — это количество ресурсов, необходимых для его выполнения. [ 1] Особое внимание уделяется времени вычислений (обычно измеряемому числом необходимых элементарных операций) и требованиям к памяти . Сложность задачи — это сложность лучших алгоритмов, которые позволяют решить задачу.
Изучение сложности явно заданных алгоритмов называется анализом алгоритмов , в то время как изучение сложности задач называется теорией вычислительной сложности . Обе области тесно связаны, поскольку сложность алгоритма всегда является верхней границей сложности задачи, решаемой этим алгоритмом. Более того, для разработки эффективных алгоритмов часто бывает принципиально важно сравнить сложность конкретного алгоритма со сложностью решаемой задачи. Кроме того, в большинстве случаев единственное, что известно о сложности задачи, — это то, что она ниже сложности наиболее эффективных известных алгоритмов. Поэтому существует большое совпадение между анализом алгоритмов и теорией сложности.
Поскольку количество ресурсов, необходимых для запуска алгоритма, обычно зависит от размера входных данных, сложность обычно выражается как функция n → f ( n ) , где n — размер входных данных, а f ( n ) — либо наихудшая сложность (максимальное количество ресурсов, необходимых для всех входных данных размера n ), либо средняя сложность (среднее количество ресурсов для всех входных данных размера n ). Временная сложность обычно выражается как количество требуемых элементарных операций на входных данных размера n , где предполагается, что элементарные операции занимают постоянное количество времени на данном компьютере и изменяются только на постоянный множитель при запуске на другом компьютере. Пространственная сложность обычно выражается как объем памяти, требуемый алгоритму на входных данных размера n .
Наиболее часто рассматриваемым ресурсом является время. Когда «сложность» используется без уточнения, это обычно означает временную сложность.
Обычные единицы времени (секунды, минуты и т. д.) не используются в теории сложности , поскольку они слишком зависят от выбора конкретного компьютера и от развития технологий. Например, современный компьютер может выполнять алгоритм значительно быстрее, чем компьютер 1960-х годов; однако это не внутренняя особенность алгоритма, а скорее следствие технологических достижений в области компьютерного оборудования . Теория сложности стремится количественно оценить внутренние временные требования алгоритмов, то есть основные временные ограничения, которые алгоритм накладывает на любой компьютер. Это достигается путем подсчета количества элементарных операций , которые выполняются во время вычисления. Предполагается, что эти операции занимают постоянное время (то есть не зависят от размера входных данных) на данной машине и часто называются шагами .
Формально, битовая сложность относится к числу операций над битами , которые необходимы для выполнения алгоритма. Для большинства моделей вычислений она равна временной сложности с точностью до постоянного множителя. На компьютерах число операций над машинными словами , которые необходимы, также пропорционально битовой сложности. Таким образом, временная сложность и битовая сложность эквивалентны для реалистичных моделей вычислений.
Другим важным ресурсом является объем памяти компьютера , необходимый для выполнения алгоритмов.
Для класса распределенных алгоритмов , которые обычно выполняются несколькими взаимодействующими сторонами, ресурсом, представляющим наибольший интерес, является сложность коммуникации. Это необходимый объем коммуникации между исполняющими сторонами.
Количество арифметических операций — еще один ресурс, который обычно используется. В этом случае говорят об арифметической сложности . Если известна верхняя граница размера двоичного представления чисел, которые возникают во время вычисления, временная сложность обычно является произведением арифметической сложности на постоянный множитель.
Для многих алгоритмов размер целых чисел, используемых во время вычисления, не ограничен, и нереалистично считать, что арифметические операции занимают постоянное время. Поэтому временная сложность, обычно называемая в этом контексте битовой сложностью , может быть намного больше арифметической сложности. Например, арифметическая сложность вычисления определителя целочисленной матрицы n × n для обычных алгоритмов ( исключение Гаусса ). Битовая сложность тех же алгоритмов экспоненциальна по n , поскольку размер коэффициентов может экспоненциально расти во время вычисления. С другой стороны, если эти алгоритмы связаны с многомодульной арифметикой , битовая сложность может быть снижена до O ~ ( n 4 ) .
При сортировке и поиске ресурс, который обычно рассматривается, — это количество сравнений записей. Это, как правило, хорошая мера временной сложности, если данные соответствующим образом организованы.
Невозможно подсчитать количество шагов алгоритма на всех возможных входных данных. Поскольку сложность обычно увеличивается с размером входных данных, сложность обычно выражается как функция размера n (в битах ) входных данных, и, следовательно, сложность является функцией n . Однако сложность алгоритма может существенно различаться для разных входных данных одинакового размера. Поэтому обычно используются несколько функций сложности.
Сложность в худшем случае — это максимум сложности по всем входам размера n , а сложность в среднем случае — это среднее значение сложности по всем входам размера n (это имеет смысл, поскольку количество возможных входов заданного размера конечно). Обычно, когда «сложность» используется без дополнительных уточнений, это и есть временная сложность в худшем случае, которая рассматривается.
Обычно сложно точно вычислить сложность в худшем и среднем случае. Кроме того, эти точные значения малоприменимы на практике, поскольку любое изменение компьютера или модели вычислений несколько изменит сложность. Более того, использование ресурсов не критично для малых значений n , и это делает то, что для малых n простота реализации, как правило, более интересна, чем низкая сложность.
По этим причинам обычно фокусируются на поведении сложности при больших n , то есть на ее асимптотическом поведении, когда n стремится к бесконечности. Поэтому сложность обычно выражается с помощью нотации O большое .
Например, обычный алгоритм умножения целых чисел имеет сложность, равную . Это означает, что существует константа, такая что умножение двух целых чисел, состоящих не более чем из n цифр, может быть выполнено за время, меньшее, чем Эта граница является точной в том смысле, что сложность в худшем случае и сложность в среднем случае равны . Это означает, что существует константа, такая что эти сложности больше, чем Основание системы счисления не появляется в этих сложностях, так как изменение основания системы счисления изменяет только константы и
Оценка сложности зависит от выбора модели вычислений , которая заключается в определении основных операций, выполняемых за единицу времени. Когда модель вычислений явно не указана, она, как правило, неявно предполагается как многоленточная машина Тьюринга , поскольку несколько более реалистичных моделей вычислений, таких как машины с произвольным доступом, асимптотически эквивалентны для большинства задач. Только для очень специфических и сложных задач, таких как целочисленное умножение во времени , явное определение модели вычислений требуется для доказательств.
Детерминированная модель вычислений — это модель вычислений, в которой последовательные состояния машины и выполняемые операции полностью определяются предыдущим состоянием. Исторически первыми детерминированными моделями были рекурсивные функции , лямбда-исчисление и машины Тьюринга . Модель машин с произвольным доступом (также называемых RAM-машинами) также широко используется как более близкий аналог реальных компьютеров .
Если модель вычисления не указана, то обычно предполагается, что это многоленточная машина Тьюринга . Для большинства алгоритмов временная сложность одинакова на многоленточных машинах Тьюринга и на RAM-машинах, хотя может потребоваться некоторая осторожность в том, как данные хранятся в памяти, чтобы получить эту эквивалентность.
В недетерминированной модели вычислений , такой как недетерминированные машины Тьюринга , некоторые выборы могут быть сделаны на некоторых этапах вычислений. В теории сложности рассматриваются все возможные выборы одновременно, и недетерминированная временная сложность — это необходимое время, когда всегда делается лучший выбор. Другими словами, считается, что вычисление выполняется одновременно на стольких (идентичных) процессорах, сколько необходимо, и недетерминированное время вычислений — это время, потраченное первым процессором, который заканчивает вычисление. Этот параллелизм частично поддается квантовым вычислениям через суперпозицию запутанных состояний при запуске определенных квантовых алгоритмов , таких как, например, факторизация Шора еще только небольших целых чисел (по состоянию на март 2018 года [обновлять]: 21 = 3 × 7).
Даже когда такая модель вычислений еще не реалистична, она имеет теоретическое значение, в основном связанное с проблемой P = NP , которая ставит под сомнение идентичность классов сложности, образованных путем взятия «полиномиального времени» и «недетерминированного полиномиального времени» в качестве наименьших верхних границ. Моделирование NP-алгоритма на детерминированном компьютере обычно занимает «экспоненциальное время». Задача находится в классе сложности NP , если ее можно решить за полиномиальное время на недетерминированной машине. Задача является NP-полной, если, грубо говоря, она находится в NP и не проще любой другой NP-задачи. Многие комбинаторные задачи, такие как задача о рюкзаке , задача о коммивояжере и задача о булевой выполнимости , являются NP-полными. Для всех этих задач самый известный алгоритм имеет экспоненциальную сложность. Если бы любую из этих задач можно было решить за полиномиальное время на детерминированной машине, то все задачи NP также можно было бы решить за полиномиальное время, и можно было бы иметь P = NP. По состоянию на 2017 год [обновлять]обычно предполагалось, что P ≠ NP, с практическим выводом, что худшие случаи задач NP изначально трудно решить, т. е. требуется больше времени, чем любой разумный промежуток времени (десятилетия!) для интересных длин входных данных.
Параллельные и распределенные вычисления состоят из разделения вычислений на нескольких процессорах, которые работают одновременно. Разница между различными моделями заключается в основном в способе передачи информации между процессорами. Обычно при параллельных вычислениях передача данных между процессорами происходит очень быстро, тогда как при распределенных вычислениях передача данных осуществляется через сеть и, следовательно, намного медленнее.
Время, необходимое для вычисления на N процессорах, по крайней мере равно частному от N времени, необходимого для одного процессора. Фактически эта теоретически оптимальная граница никогда не может быть достигнута, поскольку некоторые подзадачи не могут быть распараллелены, а некоторым процессорам, возможно, придется ждать результата от другого процессора.
Таким образом, основная проблема сложности заключается в разработке алгоритмов таким образом, чтобы произведение времени вычислений на количество процессоров было как можно ближе ко времени, необходимому для тех же вычислений на одном процессоре.
Квантовый компьютер — это компьютер, модель вычислений которого основана на квантовой механике . Тезис Чёрча–Тьюринга применим к квантовым компьютерам; то есть каждая задача, которую может решить квантовый компьютер, может быть решена и машиной Тьюринга. Однако некоторые задачи теоретически могут быть решены с гораздо меньшей временной сложностью с использованием квантового компьютера, а не классического компьютера. На данный момент это чисто теоретическое предположение, поскольку никто не знает, как построить эффективный квантовый компьютер.
Квантовая теория сложности была разработана для изучения классов сложности задач, решаемых с помощью квантовых компьютеров. Она используется в постквантовой криптографии , которая заключается в проектировании криптографических протоколов , устойчивых к атакам квантовых компьютеров.
Сложность проблемы — это инфимум сложностей алгоритмов, которые могут решить проблему [ требуется ссылка ] , включая неизвестные алгоритмы. Таким образом, сложность проблемы не больше сложности любого алгоритма, который решает проблемы.
Отсюда следует, что каждая сложность алгоритма, выраженная с помощью нотации O большое , также является верхней границей сложности соответствующей задачи.
С другой стороны, обычно трудно получить нетривиальные нижние оценки сложности задачи, и существует мало методов для получения таких нижних оценок.
Для решения большинства задач требуется прочитать все входные данные, что, как правило, требует времени, пропорционального размеру данных. Таким образом, такие задачи имеют сложность, которая является по крайней мере линейной , то есть, используя большую омега-нотацию , сложность
Решение некоторых задач, обычно в компьютерной алгебре и вычислительной алгебраической геометрии , может быть очень большим. В таком случае сложность ограничена снизу максимальным размером вывода, поскольку вывод должен быть записан. Например, система из n полиномиальных уравнений степени d с n неизвестными может иметь до комплексных решений, если число решений конечно (это теорема Безу ). Поскольку эти решения должны быть записаны, сложность этой задачи равна Для этой задачи известен алгоритм сложности , который, таким образом, можно считать асимптотически квазиоптимальным.
Известна нелинейная нижняя граница для числа сравнений, необходимых для алгоритма сортировки . Таким образом, лучшие алгоритмы сортировки являются оптимальными, так как их сложность равна Эта нижняя граница вытекает из того факта, что существует n ! способов упорядочения n объектов. Поскольку каждое сравнение разбивает на две части этот набор из n ! порядков, число N сравнений, необходимых для различения всех порядков, должно быть проверено, что следует из формулы Стирлинга .
Стандартный метод получения нижних границ сложности состоит в сведении проблемы к другой проблеме. Точнее, предположим, что можно закодировать проблему A размера n в подпроблему размера f ( n ) проблемы B , и что сложность A равна Без потери общности можно предположить, что функция f возрастает с n и имеет обратную функцию h . Тогда сложность проблемы B равна Это метод, который используется для доказательства того, что если P ≠ NP (неразрешенная гипотеза), сложность каждой NP-полной проблемы равна для каждого положительного целого числа k .
Оценка сложности алгоритма является важной частью его проектирования , поскольку она дает полезную информацию об ожидаемой производительности.
Распространено заблуждение, что оценка сложности алгоритмов станет менее важной в результате закона Мура , который постулирует экспоненциальный рост мощности современных компьютеров . Это неверно, поскольку это увеличение мощности позволяет работать с большими входными данными ( большими данными ). Например, когда требуется отсортировать в алфавитном порядке список из нескольких сотен записей, например, библиографию книги, любой алгоритм должен хорошо работать менее чем за секунду. С другой стороны, для списка из миллиона записей (например, телефонных номеров большого города) элементарные алгоритмы, требующие сравнений, должны были бы выполнить триллион сравнений, что потребовало бы около трех часов при скорости 10 миллионов сравнений в секунду. С другой стороны, быстрая сортировка и сортировка слиянием требуют только сравнений (как средней сложности для первой, как наихудшей сложности для второй). Для n = 1 000 000 это дает приблизительно 30 000 000 сравнений, что займет всего 3 секунды при 10 миллионах сравнений в секунду.
Таким образом, оценка сложности может позволить исключить многие неэффективные алгоритмы до любой реализации. Это также может быть использовано для настройки сложных алгоритмов без тестирования всех вариантов. Определяя наиболее затратные шаги сложного алгоритма, изучение сложности позволяет также сосредоточить усилия на этих шагах для повышения эффективности реализации.
