Алгоритм на месте

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

In-place может иметь немного разные значения. В своей самой строгой форме алгоритм может иметь только постоянное количество дополнительного пространства , считая все, включая функций вызовы и указатели . Однако эта форма очень ограничена, поскольку для простого наличия индекса массива длиной $n$ требуется $O (log n)$ бит. В более широком смысле, «на месте» означает, что алгоритм не использует дополнительное пространство для манипулирования входными данными, но может потребовать небольшое, хотя и непостоянное дополнительное пространство для своей работы. Обычно это пространство равно $O (log n)$ , хотя иногда $все, что находится в o (n)$ допускается . Обратите внимание, что сложность пространства также имеет разные варианты: считать ли длину индекса частью используемого пространства. Часто сложность пространства определяется количеством необходимых индексов или указателей, игнорируя их длину. В этой статье мы говорим об общей сложности пространства ( DSPACE ), считая длины указателей. Таким образом, требования к пространству здесь имеют дополнительный $коэффициент log n$ по сравнению с анализом, который игнорирует длину индексов и указателей.

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

Примеры

Учитывая массив a из $n$ элементов, предположим, нам нужен массив, содержащий одни и те же элементы в обратном порядке, и избавиться от оригинала. Один, казалось бы, простой способ сделать это — создать новый массив равного размера и заполнить его копиями из a в соответствующем порядке, а затем удалите a.

 function reverse(a[0..n - 1])
     allocate b[0..n - 1]
     for i from 0 to n - 1
         b[n − 1 − i] := a[i]
     return b

К сожалению, для этого требуется $O (n)$ дополнительного пространства для размещения массивов. a и b доступны одновременно. Кроме того, выделение и освобождение часто являются медленными операциями. Поскольку нам больше не нужно a, вместо этого мы можем перезаписать его собственным обращением, используя этот алгоритм на месте, которому потребуется только постоянное число (2) целых чисел для вспомогательных переменных i и tmp, независимо от того, насколько велик массив.

 function reverse_in_place(a[0..n-1])
     for i from 0 to floor((n-2)/2)
         tmp := a[i]
         a[i] := a[n − 1 − i]
         a[n − 1 − i] := tmp

Другой пример: многие алгоритмы сортировки переупорядочивают массивы в отсортированный порядок на месте, в том числе: пузырьковая сортировка , гребенчатая сортировка , сортировка выбором , сортировка вставкой , пирамидальная сортировка и сортировка Шелла . Этим алгоритмам требуется всего несколько указателей, поэтому их пространственная сложность равна $O (log n)$ . ^[1]

Быстрая сортировка работает с данными, подлежащими сортировке, на месте. Однако быстрая сортировка требует $O (log n)$ указателей пространства стека для отслеживания подмассивов в своей стратегии «разделяй и властвуй» . Следовательно, для быстрой сортировки требуется $O (log 2 п)$ дополнительное пространство. Хотя это непостоянное пространство технически выводит быструю сортировку из категории на месте, быстрая сортировка и другие алгоритмы, требующие только $O (log n)$ дополнительных указателей, обычно считаются алгоритмами на месте.

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

Некоторые алгоритмы манипулирования текстом, такие как обрезка и реверс, могут выполняться на месте.

По вычислительной сложности

В теории сложности вычислений строгое определение алгоритмов на месте включает в себя все алгоритмы с $пространственной сложностью O (1)$ , класс DSPACE (1). Этот класс очень ограничен; он равен обычным языкам . ^[2] Фактически, он даже не включает в себя ни один из примеров, перечисленных выше.

Алгоритмы обычно рассматриваются в L , классе задач, требующих $O (log n)$ дополнительного пространства, чтобы быть на месте. Этот класс больше соответствует практическому определению, поскольку он допускает числа размера $n$ в качестве указателей или индексов. Однако это расширенное определение по-прежнему исключает быструю сортировку из-за ее рекурсивных вызовов.

Идентификация алгоритмов на месте с помощью L имеет некоторые интересные последствия; например, это означает, что существует (довольно сложный) алгоритм определения того, существует ли путь между двумя узлами в неориентированном графе , ^[3] проблема, которая требует $O (n)$ дополнительного пространства с использованием типичных алгоритмов, таких как поиск в глубину (посещенный бит для каждого узла). Это, в свою очередь, дает алгоритмы на месте для решения таких задач, как определение того, является ли граф двудольным , или проверка того, имеют ли два графа одинаковое количество связных компонентов .

Роль случайности

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

В функциональном программировании

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

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

См. также

Таблица алгоритмов сортировки по месту и не по месту

Ссылки

^ Требование к битовому пространству указателя равно $O (log n)$ , но размер указателя можно считать константой в большинстве приложений сортировки.
^ Мачей Лискевич и Рюдигер Райщук. Сложный мир ниже логарифмического пространства . Конференция «Структура в теории сложности» , стр. 64–78. 1994. Интернет: с. 3, теорема 2.
^ Рейнгольд, Омер (2008), «Ненаправленная связность в пространстве журналов», Журнал ACM , 55 (4): 1–24, doi : 10.1145/1391289.1391291 , MR 2445014 , S2CID 207168478 , ECCC TR04-094

[1] Требование к битовому пространству указателя равно $O (log n)$ , но размер указателя можно считать константой в большинстве приложений сортировки.

[2] Мачей Лискевич и Рюдигер Райщук. Сложный мир ниже логарифмического пространства . Конференция «Структура в теории сложности» , стр. 64–78. 1994. Интернет: с. 3, теорема 2.

[3] Рейнгольд, Омер (2008), «Ненаправленная связность в пространстве журналов», Журнал ACM , 55 (4): 1–24, doi : 10.1145/1391289.1391291 , MR 2445014 , S2CID 207168478 , ECCC TR04-094

[1]

[2]

[3]