Введение
Количество ресурсов для выполнения алгоритма
В информатике вычислительная сложность, или просто сложность алгоритма, — это количество ресурсов, необходимых для его выполнения. Особое внимание уделяется времени вычислений (обычно измеряемому количеством необходимых элементарных операций) и требованиям к объему памяти. Сложность задачи — это сложность наилучших алгоритмов, позволяющих решить эту задачу. Изучение сложности явно заданных алгоритмов называется анализом алгоритмов, а изучение сложности задач — теорией вычислительной сложности. Обе области тесно связаны, поскольку сложность алгоритма всегда является верхней границей сложности задачи, решаемой этим алгоритмом. Более того, при разработке эффективных алгоритмов часто необходимо сравнивать сложность конкретного алгоритма со сложностью решаемой задачи. Кроме того, в большинстве случаев единственное, что известно о сложности задачи, — это то, что она меньше сложности наиболее эффективных известных алгоритмов. Поэтому анализ алгоритмов и теория сложности имеют значительное пересечение. Поскольку количество ресурсов, необходимых для выполнения алгоритма, обычно изменяется в зависимости от размера входных данных, сложность обычно выражается функцией n → f(n), где n — размер входных данных, а f(n) — либо сложность в худшем случае (максимум количества ресурсов, необходимых для всех входных данных размера n), либо сложность в среднем случае (среднее количество ресурсов для всех входных данных размера n). Временная сложность обычно выражается как количество необходимых элементарных операций для входных данных размера n, при этом предполагается, что элементарные операции занимают постоянное время на данном компьютере и изменяются только на постоянный множитель при выполнении на другом компьютере. Пространственная сложность обычно выражается как объем памяти, требуемый алгоритму для входных данных размера n.
Время
Наиболее часто рассматриваемым ресурсом является время. Когда термин "сложность" используется без уточнения, обычно подразумевается временная сложность. Обычные единицы измерения времени (секунды, минуты и т.д.) не используются в теории сложности, поскольку они слишком сильно зависят от выбора конкретного компьютера и развития технологий. Например, современный компьютер может выполнять алгоритм значительно быстрее, чем компьютер 1960-х годов; однако это не является неотъемлемой характеристикой самого алгоритма, а скорее следствием технологического прогресса в области компьютерного оборудования. Теория сложности стремится к количественной оценке внутренних временных требований алгоритмов, то есть базовых временных ограничений, которые алгоритм накладывает на любой компьютер. Это достигается путем подсчета количества элементарных операций, выполняемых в процессе вычисления. Предполагается, что выполнение этих операций занимает постоянное время (то есть не зависит от размера входных данных) на конкретной машине, и их часто называют шагами.
Сложность битов
Формально, битовая сложность относится к количеству операций над битами, необходимых для выполнения алгоритма. Для большинства моделей вычислений она равна временной сложности с точностью до постоянного множителя. На компьютерах количество операций над машинными словами, необходимых для выполнения, также пропорционально битовой сложности. Таким образом, временная сложность и битовая сложность эквивалентны для практических моделей вычислений.
Пространство
Другой важный ресурс — объем компьютерной памяти, требуемый для выполнения алгоритмов.
Сообщение
Для класса распределенных алгоритмов, которые обычно выполняются несколькими взаимодействующими участниками, наиболее важным ресурсом является сложность обмена сообщениями. Это необходимый объем коммуникации между взаимодействующими участниками.
Другие
Число арифметических операций — еще один часто используемый ресурс. В этом случае говорят об арифметической сложности. Если известно верхнее ограничение на размер двоичного представления чисел, возникающих в процессе вычисления, то временная сложность обычно представляет собой произведение арифметической сложности на постоянный множитель. Для многих алгоритмов размер целых чисел, используемых в вычислениях, не ограничен, и нереалистично полагать, что арифметические операции занимают постоянное время. Поэтому временная сложность, обычно называемая в этом контексте битовой сложностью, может значительно превышать арифметическую сложность. Например, арифметическая сложность вычисления определителя целочисленной матрицы размера n×n для стандартных алгоритмов (метод Гаусса) равна [значение]. Битовая сложность тех же алгоритмов экспоненциальна относительно n, поскольку размер коэффициентов может экспоненциально возрастать в процессе вычисления. Однако, если эти алгоритмы сочетаются с многомодульной арифметикой, битовая сложность может быть снижена до мягкой O-нотации. При сортировке и поиске обычно рассматривается количество сравнений элементов. Это, как правило, является хорошей мерой временной сложности, если данные организованы соответствующим образом.
Сложность в зависимости от размера входных данных
Невозможно подсчитать количество шагов алгоритма для всех возможных входных данных. Поскольку сложность обычно возрастает с увеличением размера входных данных, она обычно выражается как функция размера n (в битах) входных данных, и, следовательно, сложность является функцией от n. Однако сложность алгоритма может существенно различаться для разных входных данных одного и того же размера. Поэтому обычно используются несколько функций сложности. Сложность в наихудшем случае – это максимум сложности по всем входным данным размера n, а сложность в среднем случае – это среднее значение сложности по всем входным данным размера 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 миллионов сравнений в секунду. Таким образом, оценка сложности позволяет исключить множество неэффективных алгоритмов еще до их реализации. Ее также можно использовать для оптимизации сложных алгоритмов без необходимости тестировать все возможные варианты. Определяя наиболее ресурсоемкие этапы сложного алгоритма, анализ сложности позволяет сосредоточить усилия по повышению эффективности реализации именно на них.