 | Эта статья требует дополнительных ссылок для проверки . ( январь 2015 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон ) |
В информатике , на месте алгоритм является алгоритмом , который преобразует входной сигнал , используя не вспомогательную структуру данных . Однако для вспомогательных переменных допускается небольшой объем дополнительного места для хранения. Вход обычно перезаписывается выходом по мере выполнения алгоритма. Алгоритм на месте обновляет свою входную последовательность только путем замены или перестановки элементов. Алгоритм, который не на месте, иногда называют не на месте или не на месте .
На месте может иметь несколько иное значение. В самой строгой форме алгоритм может иметь только постоянное количество дополнительного пространства , включая все, включая вызовы функций и указатели . Однако эта форма очень ограничена, поскольку для простого наличия индекса с массивом длины n требуется O (log n ) бит. В более широком смысле, на месте означает, что алгоритм не использует дополнительное пространство для управления вводом, но может потребовать небольшое, хотя и непостоянное дополнительное пространство для его работы. Обычно это пространство O (log n ) , хотя иногда что-нибудь в O ( n )разрешено. Обратите внимание, что сложность пространства также имеет различные варианты того, следует ли считать длину индекса как часть используемого пространства. Часто сложность пространства выражается в количестве необходимых индексов или указателей без учета их длины. В этой статье мы говорим об общей сложности пространства ( DSPACE ), считая длину указателя. Следовательно, требования к пространству здесь имеют дополнительный коэффициент log n по сравнению с анализом, который игнорирует длину индексов и указателей.
Алгоритм может или не может считать вывод как часть используемого пространства. Поскольку локальные алгоритмы обычно перезаписывают свои входные данные выходными, дополнительное пространство не требуется. При записи вывода в постоянную память или поток может быть более целесообразным учитывать только рабочее пространство алгоритма. В теоретических приложениях, таких как сокращение пространства журнала , более типично всегда игнорировать пространство вывода (в этих случаях более важно, чтобы вывод был доступен только для записи ).
Примеры [ править ]
Учитывая массив a из n элементов, предположим, что нам нужен массив, который содержит те же элементы в обратном порядке и избавляется от оригинала. Один, казалось бы, простой способ сделать это - создать новый массив равного размера, заполнить его копиями из aв соответствующем порядке и затем удалить a.
функция реверс (a [0..n - 1]) выделить b [0..n - 1] для i от 0 до n - 1 b [n - 1 - i]: = a [i] вернуть б
К сожалению, это требует O ( п ) дополнительное пространство для имеющих массивы aи bдоступны одновременно. Кроме того, выделение и освобождение часто являются медленными операциями. Поскольку нам больше не нужно a, мы можем вместо этого перезаписать его собственным изменением, используя этот алгоритм на месте, которому потребуется только постоянное число (2) целых чисел для вспомогательных переменных iи tmp, независимо от размера массива.
функция reverse_in_place (a [0..n-1]) для i от 0 до этажа ((n-2) / 2) tmp: = a [i] a [i]: = a [n - 1 - i] a [n - 1 - i]: = tmp
В качестве другого примера, многие алгоритмы сортировки переставить массивы в отсортированный порядок на месте, в том числе: пузырь сортировки , расческу сортировки , выбор сортировки , вставки сортировки , пирамидальной сортировку и сортировке Шелла . Для этих алгоритмов требуется всего несколько указателей, поэтому их пространственная сложность равна O (log n ) . [1]
Quicksort работает с данными, которые нужно отсортировать. Однако для быстрой сортировки требуется O (log n ) указателей пространства стека, чтобы отслеживать подмассивы в своей стратегии « разделяй и властвуй» . Следовательно, для быстрой сортировки требуется O (log 2 n ) дополнительного места. Хотя это непостоянное пространство технически выводит быструю сортировку из категории на месте, быстрая сортировка и другие алгоритмы, требующие только O (log n ) дополнительных указателей, обычно считаются алгоритмами на месте.
Также имеется большинство алгоритмов выбора , хотя некоторые из них значительно изменяют входной массив в процессе нахождения окончательного результата с постоянным размером.
Некоторые алгоритмы обработки текста, такие как обрезка и реверс, могут выполняться на месте.
По вычислительной сложности [ править ]
В теории вычислительной сложности строгое определение локальных алгоритмов включает в себя все алгоритмы с пространственной сложностью O (1) , класс DSPACE (1). Этот класс очень ограничен; он равен обычным языкам . [2] Фактически, он даже не включает ни одного из перечисленных выше примеров.
Обычно мы рассматриваем алгоритмы в L , классе задач, требующих O (log n ) дополнительного пространства, чтобы быть на месте. Этот класс больше соответствует практическому определению, поскольку он позволяет использовать числа размера n в качестве указателей или индексов. Однако это расширенное определение по-прежнему исключает быструю сортировку из-за ее рекурсивных вызовов.
Идентификация алгоритмов на месте с помощью L имеет некоторые интересные последствия; например, это означает, что существует (довольно сложный) алгоритм на месте, чтобы определить, существует ли путь между двумя узлами в неориентированном графе , [3] проблема, которая требует O ( n ) дополнительного пространства с использованием типичных алгоритмов, таких как глубина -первый поиск (бит посещения для каждого узла). Это, в свою очередь, дает на месте алгоритмы для таких проблем, как определение того, является ли граф двудольным, или проверка того, имеют ли два графа одинаковое количество связанных компонентов . См. SL для получения дополнительной информации.
Роль случайности [ править ]
Во многих случаях требования к пространству для алгоритма можно резко сократить, используя рандомизированный алгоритм . Например, предположим, что мы хотим знать, находятся ли две вершины в графе из n вершин в одной и той же компоненте связности графа. Не существует известного простого детерминированного локального алгоритма для определения этого, но если мы просто начнем с одной вершины и выполним случайное блуждание примерно из 20 n 3 шагов, вероятность того, что мы наткнемся на другую вершину, при условии, что это в том же компоненте очень высока. Точно так же существуют простые рандомизированные локальные алгоритмы для проверки простоты, такие как тест на простоту Миллера – Рабина., а также существуют простые оперативные алгоритмы рандомизированного факторинга, такие как алгоритм ро Полларда . См. RL и BPL для более подробного обсуждения этого явления.
В функциональном программировании [ править ]
Функциональные языки программирования часто не одобряют или не поддерживают явные на месте алгоритмы перезаписи данных, поскольку это своего рода побочный эффект ; вместо этого они позволяют создавать только новые данные. Однако хорошие компиляторы функционального языка часто распознают, когда создается объект, очень похожий на существующий, а затем старый отбрасывается, и оптимизируют это до простой мутации «под капотом».
Обратите внимание, что в принципе возможно тщательно создавать алгоритмы на месте, которые не изменяют данные (если только данные больше не используются), но на практике это делается редко. Смотрите чисто функциональные структуры данных .
См. Также [ править ]
- Таблица алгоритмов сортировки по месту и не по месту
Ссылки [ править ]
- ^ Требуемое битовое пространство указателя равно O (log n ) , но размер указателя можно считать постоянным в большинстве приложений сортировки.
- ^ Maciej Liśkiewicz и Рюдигер Reischuk. Сложный мир под логарифмическим пространством . Конференция "Структура в теории сложности" , стр. 64-78. 1994. Онлайн: с. 3, теорема 2.
- ^ Рейнгольд, Омер (2008), "неориентированный подключения в лог-пространстве", Журнал ACM , 55 (4): 1-24, DOI : 10,1145 / 1391289,1391291 , MR 2445014 , ECCC TR04-094
