Введение
Тип алгоритма в информатике
В информатике алгоритм in place – это алгоритм, который работает непосредственно со структурой входных данных, не требуя дополнительного пространства, пропорционального размеру входных данных. Иными словами, он изменяет входные данные на месте, не создавая отдельную копию структуры данных. Алгоритм, который не является in place, иногда называют not in place или out of place. Термин "in place" может иметь несколько различных значений. В самом строгом смысле алгоритм может использовать только постоянный объем дополнительного пространства, учитывая все, включая вызовы функций и указатели. Однако эта форма очень ограничена, так как даже для индекса массива длиной n требуется O(log n) бит. В более широком смысле, in place означает, что алгоритм не использует дополнительное пространство для обработки входных данных, но может потребовать небольшое, хотя и не постоянное, дополнительное пространство для своей работы. Обычно это пространство составляет O(log n), хотя иногда допускается любое пространство, принадлежащее o(n). Важно отметить, что сложность по памяти также может определяться по-разному, в зависимости от того, учитывать ли длину индексов как часть используемого пространства. Часто пространственная сложность указывается с точки зрения количества необходимых индексов или указателей, игнорируя их длину. В данной статье мы используем понятие общей пространственной сложности (DSPACE), учитывающее длину указателей. Следовательно, требования к пространству здесь имеют дополнительный фактор log n по сравнению с анализом, который игнорирует длину индексов и указателей. Алгоритм может учитывать или не учитывать выходные данные как часть используемого пространства. Поскольку алгоритмы in place обычно перезаписывают входные данные выходными, дополнительное пространство не требуется. При записи выходных данных только в память или поток, может быть более целесообразно учитывать только рабочее пространство алгоритма. В теоретических приложениях, таких как логарифмическое сокращение пространства, обычно игнорируют выходное пространство (в этих случаях важнее, чтобы выход был доступен только для записи).
В вычислительной сложности
В теории вычислительной сложности строгое определение алгоритмов in place включает все алгоритмы с пространственной сложностью O(1), класс DSPACE(1). Этот класс очень ограничен; он равен регулярным языкам. Фактически, он даже не включает ни один из примеров, приведенных выше. Обычно алгоритмы, относящиеся к классу L – задачам, требующим O(log n) дополнительного пространства, – считаются in place. Этот класс лучше соответствует практическому определению, поскольку он позволяет использовать числа размера n в качестве указателей или индексов. Однако это расширенное определение все еще исключает быструю сортировку из-за рекурсивных вызовов. Отождествление алгоритмов in place с классом L имеет интересные последствия; например, это означает, что существует (довольно сложный) алгоритм in place для определения наличия пути между двумя узлами в ненаправленном графе – задача, требующая O(n) дополнительного пространства при использовании типичных алгоритмов, таких как поиск в глубину (для каждого узла требуется бит, отмечающий посещение). Это, в свою очередь, позволяет разработать алгоритмы in place для таких задач, как определение, является ли граф двудольным, или проверка, имеют ли два графа одинаковое количество связных компонент.
Роль случайности
Во многих случаях пространственные требования алгоритма можно значительно уменьшить, используя рандомизированный алгоритм. Например, если требуется узнать, находятся ли две вершины в графе из n вершин в одном и том же связном компоненте, простого, детерминированного алгоритма, работающего на месте, для определения этого не существует. Однако, если начать с одной вершины и выполнить случайное блуждание примерно в шагов, вероятность обнаружить другую вершину, при условии, что она находится в том же компоненте, очень велика. Аналогично, существуют простые рандомизированные алгоритмы, работающие на месте, для проверки простоты, такие как тест простоты Миллера — Рабина, а также простые рандомизированные алгоритмы факторизации, такие как алгоритм ро Поларда.
В функциональном программировании
Функциональные языки программирования часто не поощряют или не поддерживают явные алгоритмы изменения данных на месте, поскольку это является видом побочного эффекта; вместо этого они допускают только создание новых данных. Однако, хорошие компиляторы функциональных языков часто распознают, когда создается объект, очень похожий на существующий, а затем старый объект отбрасывается, и оптимизируют это, выполняя простое изменение "под капотом". Важно отметить, что теоретически возможно разработать алгоритмы изменения данных на месте, которые не модифицируют данные, пока они не перестанут использоваться, но на практике это встречается редко.