Контекст вычислительной сложности - Context of computational complexity
В теории сложности вычислений и анализе алгоритмов определяется ряд показателей, описывающих ресурсы, такие как время или пространство, которые необходимы машине для решения конкретной проблемы. Для осмысленной интерпретации этих показателей требуется контекст, который часто является неявным и зависит от области и рассматриваемой проблемы. В этой статье описывается ряд важных частей контекста и их влияние на показатели.
Определения переменных
Метрики обычно описываются в виде переменных, которые являются функцией входных данных. Например, утверждение о том, что сортировка вставкой требует O ( n 2 ) сравнений, не имеет смысла без определения n , которое в данном случае является количеством элементов во входном списке.
Поскольку многие разные контексты используют одни и те же буквы для своих переменных, может возникнуть путаница. Например, сложность тестов на простоту и алгоритмов умножения может быть измерена двумя разными способами: одним с точки зрения проверяемых или умножаемых целых чисел, а другим с точки зрения количества двоичных цифр (битов) в этих целых числах. Например, если n - целое число, проверяемое на простоту, пробное деление может проверить его за Θ (n 1/2 ) арифметических операций; но если n - количество битов целого числа, проверяемого на простоту, для этого требуется (2 n / 2 ) времени. В области криптографии и вычислительной теории чисел более типично определять переменную как количество битов во входных целых числах.
В области теории сложности вычислений ввод обычно задается как двоичная строка (или строка в некотором фиксированном алфавите), а переменная обычно представляет собой количество битов в этой строке. Эта мера зависит от конкретной кодировки ввода, которую необходимо указать. Например, если входное число является целым числом, указанным с использованием унарного кодирования , пробное деление потребует только Θ (n 1/2 ) арифметических операций; но если тот же самый вход задан в двоичном формате (или в любой более крупной базе), сложность возрастает до (2 n / 2 ) операций не потому, что алгоритм требует дополнительного времени, а потому, что количество битов на входе n стало экспоненциально меньше. С другой стороны, сжатые схемы - это компактные представления ограниченного класса графов, которые занимают экспоненциально меньше места, чем обычные представления, такие как списки смежности. Многие алгоритмы графов на сжатых схемах являются EXPTIME-полными , тогда как те же проблемы, выраженные с помощью обычных представлений, являются только P-полными , потому что сжатые входные данные схемы имеют меньшее кодирование.
Чувствительные к выходу алгоритмы определяют свою сложность не только с точки зрения входных данных, но и их выходных данных. Например, алгоритм Чана может вычислить выпуклую оболочку набора точек за время O ( n log h ), где n - количество точек на входе, а h - количество точек в результирующей выпуклой оболочке, подмножество точки ввода. Поскольку каждая входная точка может находиться в выпуклой оболочке, анализ только с точки зрения входа даст менее точное время O ( n log n ).
Сложность некоторых алгоритмов зависит не только от параметров ввода, но и от параметров машины, на которой выполняется алгоритм; как упоминается в разделе «#Metric, измеряемом ниже», это типично для анализа алгоритмов, которые работают в системах с фиксированной иерархией кеша, где сложность может зависеть от таких параметров, как размер кеша и размер блока.
Абстрактная машина
Чтобы точно проанализировать алгоритм, нужно предположить, что он выполняется определенной абстрактной машиной . Например, на случайной машине доступа , двоичный поиск может быть использован для быстрого поиска определенного значения в отсортированном списке только O (журнал п ) сравнения, где п есть число элементов в списке; на машине Тьюринга это невозможно, поскольку она может перемещать только одну ячейку памяти за раз, и поэтому требуется Ω ( n ) шагов, чтобы даже достичь произвольного значения в списке.
Более того, разные абстрактные машины определяют разные примитивные операции, которые могут выполняться за постоянное время. Некоторые машины, такие как машины Тьюринга, позволяют читать или записывать только один бит за раз; они называются битовыми операциями, а количество битовых операций, необходимых для решения проблемы, называется ее битовой сложностью . Битовая сложность распространяется на любую машину, где ячейки памяти имеют фиксированный размер, не зависящий от ввода; по этой причине алгоритмы, которые манипулируют числами, намного большими, чем регистры на обычных ПК, обычно анализируются с точки зрения их битовой сложности. Другими словами, битовая сложность - это сложность, когда размер слова составляет один бит, где размер слова - это размер каждой ячейки памяти и регистра.
В другой широко используемой модели есть слова с log n битами, где n - переменная, зависящая от ввода. Например, в алгоритмах графа обычно предполагается, что вершины пронумерованы от 1 до n и что каждая ячейка памяти может содержать любое из этих значений, так что они могут ссылаться на любую вершину. Это оправдано в задачах, где на входе используются слова памяти Ω ( n ), поскольку на реальных компьютерах ячейка памяти и размер регистра обычно выбираются для того, чтобы иметь возможность индексировать любое слово в памяти. Предполагается, что операции над этими словами, такие как копирование и арифметические операции, выполняются в постоянное время, а не за время O (log n ). Количество операций со словами, необходимых для решения проблемы в этой модели, иногда называют ее сложностью слова .
В теории сложности вычислений исследователи намеренно определяют классы сложности таким образом, чтобы сделать их машинно-независимыми - то есть, если проблема лежит в конкретном классе относительно конкретной «разумной» машины, она будет лежать в этом классе относительно любой "разумная" машина. Например, как упоминалось выше, временная сложность двоичного поиска зависит от того, используется ли машина Тьюринга или машина произвольного доступа; но независимо от выбора машины, он лежит в P , классе алгоритмов с полиномиальным временем. В общем, P считается машинно-независимым классом, потому что любая операция, которая может быть смоделирована за полиномиальное время, может считаться требующей постоянного времени, поскольку ее можно рассматривать как подпрограмму, не выходя за пределы полиномиального времени.
Машины Oracle - это машины, у которых есть определенная операция, которую они могут выполнять в постоянное время; эта операция может быть сколь угодно сложной и может существенно повлиять на сложность алгоритмов, выполняемых на машине. Например, если у кого-то есть оракул для решения любой NP-полной задачи, то любая проблема в NP может быть решена за полиномиальное время (тогда как без оракула для многих из этих проблем не известен ни один алгоритм с полиномиальным временем). Машины Oracle непрактично строить, но они полезны в теории для определения эффективных методов доказательства.
Измеряемая метрика
Обычно без уточнений можно сказать, что сортировка вставкой требует времени O ( n 2 ); однако нет смысла говорить, что битовая сложность сортировки вставкой равна O ( n 2 ), если только сортируемые элементы не имеют постоянного размера. Если предполагается, что элементы являются целыми числами от 1 до n , тогда сложность слова, в котором слова имеют log n битов, будет O ( n 2 ), но предпочтительнее иметь модель, позволяющую сортировать списки, отличные от списков небольших целых чисел, например, списки строк. В этом случае вместо измерения количества временных шагов, которые делает абстрактная машина, предпочтительнее определить конкретную метрику, соответствующую рассматриваемой проблеме. Для алгоритмов сортировки сравнения , которые проверяют входные данные, используя только сравнения, и изменяют их, используя только обмены (свопы), типичной метрикой является либо количество выполненных сравнений элементов, количество выполненных обменов элементами, либо их сумма. С помощью этих показателей можно сравнивать различные алгоритмы сортировки сравнения, но для полезного сравнения с алгоритмами сортировки без сравнения, такими как сортировка по основанию , должна использоваться другая метрика, а набор элементов должен быть ограничен.
Поскольку операции с диском на порядки медленнее, чем доступ к основной памяти, типичная метрика, используемая в дисковых алгоритмах, - это количество обращений к диску или количество блоков, прочитанных с диска, которые зависят как от входных данных, так и от параметров диск. Доступ к ОЗУ и операции ЦП «бесплатны». Точно так же во многих моделях, используемых для изучения структур данных, таких как модель без учета кеширования, операции с кэшированными данными считаются «бесплатными», поскольку на практике они обычно на порядки быстрее, чем доступ к основной памяти. Следовательно, типичный используемый показатель - это количество промахов кеша, которое зависит как от входных данных, так и от параметров кеша.