Что сложнее: перетасовать отсортированную колоду или сортировать перетасованную?

У вас есть массив из отдельных элементов. У вас есть доступ к компаратору (функция черного ящика, принимающая два элемента и и возвращающая true, если ) и действительно случайный источник битов (функция черного ящика, не принимающая аргументов и возвращающая независимо равномерно случайный бит). Рассмотрим следующие две задачи: $n$ $a$ $b$ $a < b$

В настоящее время массив отсортирован. Произведите равномерно (или приблизительно равномерно) случайно выбранную перестановку.
Массив состоит из некоторой перестановки, выбранной равномерно случайным образом по своей природе. Создайте отсортированный массив.

Мой вопрос

Какая задача требует больше энергии асимптотически?

Я не могу определить вопрос более точно, потому что я недостаточно знаю о связи между теорией информации, термодинамикой или чем-то еще, что необходимо для ответа на этот вопрос. Тем не менее, я думаю, что вопрос может быть четко определен (и я надеюсь, что кто-то поможет мне с этим в ответе!).

Теперь, алгоритмически, моя интуиция заключается в том, что они равны. Обратите внимание, что каждый вид - это случайное перемешивание, и наоборот. Для сортировки требуется сравнений во время перемешивания, так как он выбирает случайную перестановку извыбор, требует случайных бит. Для перемешивания и сортировки требуется около перестановок. $\log n! \approx n \log n$ $n!$ $\log n! \approx n \log n$ $n$

Тем не менее, я чувствую, что должен быть ответ, применяющий принцип Ландауэра , который гласит, что требуется энергия, чтобы «стереть» немного. Интуитивно, я думаю, это означает, что сортировка массива более трудна, потому что это требует «стирания» битов информации, переходящих от низкоэнергетического основного состояния с высокой энтропией к беспорядку к высокоупорядоченному. Но с другой стороны, для любого данного вычисления сортировка просто преобразует одну перестановку в другую. Поскольку я здесь совершенно не эксперт, я надеялся, что кто-то, обладающий знанием связи с физикой, сможет помочь с этим разобраться! $n \log n$

(Вопрос не получил никаких ответов на math.se , поэтому я разместил его здесь. Надеюсь, что все в порядке.)

algorithms algorithm-analysis information-theory permutations entropy усул
источник

Я не продумал это вообще, так что будьте осторожны, лектор. Если мы начнем с отсортированного массива, затем используем сортировку слиянием, но вместо сравнения мы используем случайные биты для объединения (поэтому вместо возврата true, если мы возвращаем true, если случайный бит равен ). Базовый случай, когда у нас есть два массива размера один, создает два возможных массива размера два с одинаковой вероятностью. Я не получил дальше, чем это.

a < b

$a<b$

1

$1$

Люк Мэтисон

Я думаю, что для того, чтобы ответить на этот вопрос, сначала нужно определить относительные затраты на эксплуатацию; сколько стоит чтение данных, запись данных и генерация / получение случайного числа?

Митч

@mitchus: Мне в основном любопытно узнать о физических ограничениях, если мы примем «оптимально эффективные» компьютеры. Мое грубое понимание состоит в том, что существует физическая нижняя граница количества энергии, необходимой для «стирания» небольшого количества информации, в то время как другие операции требуют гораздо меньше энергии. Поэтому мне интересно, является ли эта интуиция правильной и достаточно формализуемой, чтобы дать ответ.

Усул

Что вы имеете в виду, стирая немного? Перезаписать это? Насколько я знаю, компьютеры обычно ничего не стирают (за исключением соображений конфиденциальности), а просто «забывают» об этом, удаляя выделенную область памяти. Но, может быть, я не правильно понимаю уровень абстракции здесь :)

mitchus

@ Patrick87 К сожалению, модель однородной энергии слишком далека от истины, чтобы использовать ее; см. Оценочные алгоритмы в соответствии с их потреблением энергии Fudeus née Bayer and Nebel (2009).

Рафаэль

Ответы:

По принципу Ландауэра, если вы хотите взять равномерную случайную перестановку из ключей в отсортированную и не хранить в компьютере никаких битов, которые бы раскрыли, какова была равномерная случайная перестановка, вам нужно стереть бит. Это займет энергии. С другой стороны, вычисление, переводящее отсортированный массив и случайных битов в случайный массив, является обратимым, и, таким образом, затраченная энергия может быть сделана сколь угодно малой. $n$ $log n! \approx n \log_2 n$ $(n \ln n) k T$ $n \log_2 n$

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

Питер Шор
источник

Огромное спасибо! Могу ли я попросить, возможно, наивное продолжение? Предположим, я изменил формулировку вопроса так, чтобы алгоритм сортировки получил некоторую фиксированную перестановку элементов и должен сортировать их. Теперь, если вы согласны с байесовской философией и придерживаетесь единого мнения об этом, похоже, ответ должен быть таким же. Но в соответствии с философией, в которой нет случайности во входных данных (хотя я не знаю, что это такое), аргумент, похоже, проваливается. Как мне решить парадокс? Еще раз спасибо!!

usul

(n \ln n) k T

$(n \ln n) kT$

Ни. Любая схема может быть сделана обратимой , отслеживая вход, и рассеяние энергии обратимого вычисления может быть сделано сколь угодно малым .

rphv
источник

но сделать его обратимым может сделать его неэффективным. Какова связь между оптимальными алгоритмами. Кстати, я не думаю, что они сравнивают. Перестановка по своей природе требует случайности (и любая другая случайность приведет к другому результату). Сортировка может быть детерминированной. «Реверсивная» сортировка будет перетасовываться детерминированным способом.

Ран Г.

Под «эффективным» вы подразумеваете время, пространство или какую-то комбинацию двух? Создание обратимых вычислений не обязательно добавляет асимптотическую сложность времени, и существуют обратимые версии всех вычислений, которые занимают не больше места, чем оригинал [Vitányi05] .

rphv

Пока вы сохраняете вход, любая схема может быть сделана обратимой. Если вы не хотите хранить информацию, которая может восстановить исходную перестановку, схему сортировки нельзя сделать обратимой.

Питер Шор