EITC/IS/CCTF Основы теории вычислительной сложности

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

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

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

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

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

Размер целых чисел, используемых во время вычислений, не ограничен для многих методов, и нереалистично предположить, что арифметические операции требуют фиксированного количества времени. В результате временная сложность, также известная как битовая сложность, может быть значительно выше арифметической сложности. Например, арифметическая сложность вычисления определителя целочисленной матрицы nn составляет O (n ^ 3) для стандартных методов (исключение Гаусса). Поскольку размер коэффициентов может увеличиваться экспоненциально во время вычислений, битовая сложность тех же методов экспоненциальна относительно n. Если эти методы используются в сочетании с многомодульной арифметикой, сложность битов может быть уменьшена до O (n ^ 4).

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

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

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

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

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

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

Вычислительные модели

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чтобы решить большинство проблем, все входные данные должны быть прочитаны, что занимает время, пропорциональное величине данных. В результате такие задачи имеют по крайней мере линейную сложность или, в больших омега-обозначениях, сложность Ω(n).

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

Количество сравнений, необходимых для алгоритма сортировки, имеет нелинейную нижнюю границу Ω(nlogn). В результате лучшие алгоритмы сортировки являются наиболее эффективными, поскольку их сложность составляет O(nlogn). Тот факт, что есть n! способов организации n вещей приводит к этой нижней границе. Потому что каждое сравнение делит этот набор на n! порядков на две части, количество сравнений N, необходимых для различения всех порядков, должно быть 2N > n!, что означает O(nlogn) по формуле Стирлинга.

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

Разработка алгоритма

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

Распространено заблуждение, что в результате действия закона Мура, который предсказывает экспоненциальный рост мощности современных компьютеров, оценка сложности алгоритмов станет менее актуальной. Это неверно, потому что повышенная мощность позволяет обрабатывать огромные объемы данных (большие данные). Например, любой алгоритм должен работать менее чем за секунду при сортировке в алфавитном порядке списка из нескольких сотен записей, например библиографии книги. С другой стороны, для миллиона записей (например, телефонных номеров большого города) базовые алгоритмы, требующие O(n2) сравнений, должны были бы выполнить триллион сравнений, что заняло бы три часа при скорости 10 миллионов сравнений в секунду. Быстрая сортировка и сортировка слиянием, с другой стороны, требуют только nlogn сравнений (как сложность в среднем для первого, так и сложность в наихудшем случае для второго). Это дает около 30,000,000 1,000,000 3 сравнений для n = 10 XNUMX XNUMX, что займет всего XNUMX секунды при XNUMX миллионах сравнений в секунду.

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