В информатике вычислительная сложность или просто сложность алгоритма — это количество ресурсов, необходимых для его запуска . [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 стремится к бесконечности. Поэтому сложность обычно выражается с помощью обозначения большого О.
Например, обычный алгоритм умножения целых чисел имеет сложность, означающую, что существует константа, такая, что умножение двух целых чисел, состоящих не более чем из n цифр, может быть выполнено за время, меньшее, чем Эта оценка является точной в том смысле, что наихудшая -сложность случая и сложность среднего случая означают, что существует такая константа, что эти сложности больше, чем Основание системы счисления не появляется в этой сложности, поскольку изменение системы счисления изменяет только константы и
Оценка сложности зависит от выбора модели вычислений , заключающейся в определении основных операций, выполняемых в единицу времени. Когда модель вычислений не указана явно, обычно неявно предполагается, что это многоленточная машина Тьюринга , поскольку несколько более реалистичных моделей вычислений, таких как машины с произвольным доступом, асимптотически эквивалентны для большинства задач. Только для очень специфических и сложных задач, таких как умножение целых чисел во времени , для доказательств требуется явное определение модели вычислений.
Детерминированная модель вычислений — это такая модель вычислений, в которой последовательные состояния машины и выполняемые операции полностью определяются предыдущим состоянием. Исторически первыми детерминистическими моделями были рекурсивные функции , лямбда-исчисление и машины Тьюринга . Модель машин с произвольным доступом (также называемая 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 .
Оценка сложности алгоритма является важной частью разработки алгоритма , поскольку она дает полезную информацию об ожидаемой производительности.
Распространено заблуждение, что оценка сложности алгоритмов станет менее важной в результате действия закона Мура , который постулирует экспоненциальный рост мощности современных компьютеров . Это неправильно, поскольку такое увеличение мощности позволяет работать с большими входными данными ( big data ). Например, когда кто-то хочет отсортировать в алфавитном порядке список из нескольких сотен записей, например библиографию книги, любой алгоритм должен работать хорошо менее чем за секунду. С другой стороны, для списка из миллиона записей (например, телефонных номеров большого города) элементарным алгоритмам, требующим сравнений, пришлось бы выполнить триллион сравнений, что потребовало бы около трех часов со скоростью 10 миллионов сравнений в секунду. С другой стороны, быстрая сортировка и сортировка слиянием требуют только сравнения (как сложность среднего случая для первого и сложность наихудшего случая для второго). Для n = 1 000 000 это дает примерно 30 000 000 сравнений, что займет всего 3 секунды при 10 миллионах сравнений в секунду.
Таким образом, оценка сложности может позволить исключить множество неэффективных алгоритмов перед их реализацией. Это также можно использовать для настройки сложных алгоритмов без тестирования всех вариантов. Определив наиболее затратные этапы сложного алгоритма, исследование сложности позволяет также сосредоточить на этих шагах усилия по повышению эффективности реализации.
