Контекст вычислительной сложности - Context of computational complexity

Эта статья не цитировать любой источники. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. Найдите источники: «Контекст вычислительной сложности»  – Новости  · газеты  · книги  · ученый  · JSTOR (Январь 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Определения переменных

Метрики обычно описываются в виде переменных, которые являются функцией входных данных. Например, утверждение, что вставка сортировки требует О (п²) сравнения бессмысленны без определения п, который в данном случае является количеством элементов во входном списке.

Поскольку многие разные контексты используют одни и те же буквы для своих переменных, может возникнуть путаница. Например, сложность тесты на простоту и алгоритмы умножения могут быть измерены двумя разными способами: одним с точки зрения проверяемых или умножаемых целых чисел, и одним с точки зрения количества двоичный цифры (биты) в этих целых числах. Например, если п целое число, проверяемое на простоту, судебное отделение можно проверить это в Θ (n^1/2) арифметические операции; но если п - количество битов целого числа, проверяемого на простоту, для него требуется Θ (2^{п / 2}) время. В полях криптография и вычислительная теория чисел, более типично определять переменную как количество битов во входных целых числах.

В области теория сложности вычислений, вход обычно задается как двоичная строка (или строка в некотором фиксированном алфавите), а переменная обычно представляет собой количество битов в этой строке. Эта мера зависит от конкретной кодировки ввода, которую необходимо указать. Например, если ввод - целое число, указанное с помощью унарное кодирование, для пробного деления потребуется всего Θ (n^1/2) арифметические операции; но если тот же самый вход задан в двоичном формате (или в любой более крупной базе), сложность возрастает до Θ (2^{п / 2}) операций не потому, что алгоритм требует дополнительного времени, а потому, что количество битов на входе п стал экспоненциально меньше. В другом направлении, сжатые схемы компактные представления ограниченного класса графики которые занимают экспоненциально меньше места, чем обычные представления, такие как списки смежности. Многие алгоритмы графа на сжатых схемах EXPTIME-завершено, тогда как те же проблемы, выраженные с помощью обычных представлений, только P-полный, потому что сжатые входы схемы имеют меньшее кодирование.

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

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

Абстрактная машина

Чтобы точно проанализировать алгоритм, нужно предположить, что он выполняется конкретным абстрактная машина. Например, на машина с произвольным доступом, бинарный поиск может использоваться для быстрого поиска определенного значения в отсортированном списке только за O (log п) сравнения, где п - количество элементов в списке; на Машина Тьюринга, это невозможно, так как он может перемещать только одну ячейку памяти за раз и поэтому требует Ω (п) шагов, чтобы даже достичь произвольного значения в списке.

Более того, разные абстрактные машины определяют разные примитивный операции, которые могут выполняться в постоянное время. Некоторые машины, такие как машины Тьюринга, позволяют читать или записывать только один бит за раз; они называются битовыми операциями, а количество битовых операций, необходимых для решения проблемы, называется ее битовая сложность.^[1] Битовая сложность распространяется на любую машину, где ячейки памяти имеют фиксированный размер, не зависящий от ввода; по этой причине алгоритмы, которые управляют числами, намного большими, чем регистры на обычных ПК, обычно анализируются с точки зрения их битовой сложности. Другими словами, битовая сложность - это сложность, когда размер слова составляет один бит, где размер слова - это размер каждой ячейки памяти и регистра.^[2]

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

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

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

Измеряемая метрика

Обычно без оговорок можно сказать, что вставка сортировки требуется O (п²) время; однако нет смысла говорить, что битовая сложность сортировки вставкой равна O (п²), если только сортируемые элементы не имеют постоянного размера. Если предполагается, что элементы являются целыми числами от 1 до п, то сложность слова, в котором слова имеют log п бит будет O (п²), но предпочтительнее иметь модель, позволяющую сортировать списки, отличные от списков небольших целых чисел, например списков строк. В этом случае вместо измерения количества временных шагов, которые делает абстрактная машина, предпочтительнее определить конкретную метрику, соответствующую рассматриваемой проблеме. За сортировка сравнения алгоритмы, которые проверяют ввод, используя только сравнения и модифицируют его, используя только обмены (свопы), типичной метрикой является либо количество выполненных сравнений элементов, количество выполненных обменов элементов, либо их сумма. С помощью этих показателей можно сравнивать различные алгоритмы сортировки сравнения, но для полезного сравнения с алгоритмами сортировки без сравнения, такими как радиальная сортировка, необходимо использовать другую метрику и ограничить набор элементов.

Поскольку операции с диском на порядки медленнее, чем доступ к основной памяти, типичная метрика, используемая в дисковых алгоритмах, - это количество обращений к диску или количество блоков, считанных с диска, которые зависят как от входных данных, так и от параметров диск. Доступ к ОЗУ и операции ЦП «бесплатны». Точно так же во многих моделях, используемых для изучения структур данных, таких как модель без кеширования, операции с кэшированными данными считаются «бесплатными», потому что на практике они обычно на порядки быстрее, чем доступ к основной памяти. Следовательно, типичный используемый показатель - это количество промахов кеша, которое зависит как от входных данных, так и от параметров кеша.

Рекомендации