 | Эта статья требует дополнительных ссылок для проверки . ( январь 2021 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
В теории сложности вычислений и анализе алгоритмов определяется ряд показателей, описывающих ресурсы, такие как время или пространство, которые необходимы машине для решения конкретной проблемы. Для осмысленной интерпретации этих показателей требуется контекст, который часто является неявным и зависит от области и рассматриваемой проблемы. В этой статье описывается ряд важных частей контекста и их влияние на показатели.
Определения переменных [ править ]
Метрики обычно описываются с помощью переменных, которые являются функцией входных данных. Например, утверждение о том, что сортировка вставкой требует 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 ) шагов даже для достижения произвольного значения в списке.
Более того, разные абстрактные машины определяют разные примитивные операции, которые могут выполняться за постоянное время. Некоторые машины, такие как машины Тьюринга, позволяют читать или писать только один бит за раз; они называются битовыми операциями, а количество битовых операций, необходимых для решения проблемы, называется ее битовой сложностью . [1]Битовая сложность распространяется на любую машину, где ячейки памяти имеют фиксированный размер, не зависящий от ввода; по этой причине алгоритмы, которые манипулируют числами, намного большими, чем регистры на обычных ПК, обычно анализируются с точки зрения их битовой сложности. Другими словами, битовая сложность - это сложность, когда размер слова составляет один бит, где размер слова - это размер каждой ячейки памяти и регистра. [2]
В другой часто используемой модели есть слова с 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), но предпочтительнее иметь модель, позволяющую сортировать списки, отличные от списков небольших целых чисел, например списков строк. В этом случае вместо измерения количества временных шагов, которые делает абстрактная машина, предпочтительнее определить конкретную метрику, соответствующую рассматриваемой проблеме. Для алгоритмов сортировки сравнения , которые проверяют ввод, используя только сравнения, и изменяют его, используя только обмены (свопы), типичным показателем является либо количество выполненных сравнений элементов, количество выполненных обменов элементами, либо их сумма. С помощью этих показателей можно сравнивать различные алгоритмы сортировки сравнения, но для полезного сравнения с алгоритмами сортировки без сравнения, такими как сортировка по основаниюнеобходимо использовать другую метрику и ограничить набор элементов.
Поскольку дисковые операции на порядки медленнее, чем доступ к основной памяти, типичная метрика, используемая в дисковых алгоритмах, - это количество обращений к диску или количество блоков, прочитанных с диска, которые зависят как от входных данных, так и от параметров диск. Доступ к оперативной памяти и операции с ЦП «бесплатны». Точно так же во многих моделях, используемых для изучения структур данных, таких как модель без учета кеширования, операции с кэшированными данными считаются «бесплатными», поскольку на практике они обычно на несколько порядков быстрее, чем доступ к основной памяти. Следовательно, типичный используемый показатель - это количество промахов кеша, которое зависит как от входных данных, так и от параметров кеша.
Ссылки [ править ]
- ^ «О битовой сложности нахождения точек в компонентах связности гладкой реальной гиперповерхности | Труды 45-го Международного симпозиума по символьным и алгебраическим вычислениям» . dl.acm.org . DOI : 10.1145 / 3373207.3404058 . Проверено 29 июля 2020 .
- ^ ElliottJesse; SchostÉric (17 декабря 2019 г.). «Битовая сложность для вычисления критических точек в гладких и компактных реальных гиперповерхностях» . ACM-коммуникации в компьютерной алгебре . DOI : 10.1145 / 3377006.3377014 .
