вычислительная сложность всегда определяется относительно некоторой вычислительной модели. Например, алгоритм, который O(n) на обычном компьютере может быть O(2ⁿ), если они реализуются в Brainfuck.

вычислительная модель центробежки имеет некоторые интересные свойства, например:

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

учитывая, что у нас нет возможности реализовать что-то подобное в вычислений общего назначения аппаратное обеспечение, модель может не иметь практического значения; но все же ее стоит изучить, чтобы увидеть, есть ли что-нибудь, что можно узнать из нее. недетерминированные алгоритмы и квантовые алгоритмы оба были активными областями исследований, например, хотя ни один из них не может быть реализован сегодня.

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

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

реальный пример компьютерного "заказа" - это автономные дроны, которые совместно работают друг с другом, известные как"рои дронов". Дроны действуют и общаются как индивидуально, так и в группе, и могут отслеживать несколько целей. Дроны коллективно решают, какие дроны будут следовать за какими целями и очевидной необходимостью избегать столкновений между дронами. Ранние версии этого были беспилотники, которые двигались через точки пути, оставаясь в строю, но формирование может изменить.

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

возвращаясь к сортировке на основе компьютера, одна из проблем заключается в том, что существует одна основная шина памяти, и нет возможности для параллельного перемещения большого количества объектов в памяти.

узнать позицию каждый элемент

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

ИМХО, люди overthink log (n). O(nlog(n)) - это практически O (n). И Вам нужно O (n) просто прочитать данные.

многие алгоритмы, такие как quicksort, обеспечивают очень быстрый способ сортировки элементов. Вы можете реализовать варианты quicksort, которые будут очень быстрыми на практике.

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

из комментариев:

1. учитывая физический процессор, который имеет k число элементов, он может достичь параллельности не более O(k). Если вы обрабатываете n чисел произвольно, он все равно будет обрабатывать его со скоростью, связанной с k. кроме того, вы можете сформулировать эту проблему физически. Вы смогли создать N стальных шариков с весами пропорциональными к число, которое вы хотите закодировать, которое может быть решено центрифугой в теории. Но вот количество атомов, который вы используете, пропорциональна N. В то время как в стандартном случае у вас есть ограниченное количество атомов в процессор.

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

Я работал в офисе летом после окончания школы, когда я поступил в колледж. Я учился в AP Computer Science, среди прочего,сортировка и поиск.

я применил это знание в нескольких физических системах, которые я могу вспомнить:

естественная сортировка слиянием для начала...

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

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

затем, слияние каждая пара стеков, производя больший стек. Повторяйте, пока не останется только один стек.

... сортировка вставки для завершения

легче подать сортированные карты, так как каждый следующий немного ниже того же открытого выдвижной ящик.

Radix sort

этот никто другой не понял, как я сделал это так быстро, несмотря на неоднократные попытки научить его.

большая коробка чековых заглушек (размер перфокарт) должна быть отсортирована. Это похоже на игру в пасьянс на большом столе-раздайте, сложите, повторите.

в общем

30 лет назад я заметил, о чем вы спрашиваете: идеи переносятся в физические системы довольно прямо, потому что есть относительные затраты из сравнения и обработка записей и уровней кэширования.

выход за пределы хорошо понял эквиваленты

Я вспоминаю эссе о вашей теме, и он поднял вроде спагетти. Вы обрезаете длину сушеной лапши, чтобы указать значение ключа, и помечаете его идентификатором записи. Это O (n), просто обрабатывая каждый элемент один раз.

затем вы хватаете пачку и нажимаете один конец на стол. Они выравнивают на дне ребра, и они теперь отсортированы. Вы можете тривиально снять самый длинный и повторить. Считывание также O (n).

здесь, в "реальном мире", происходят две вещи, которые не соответствуют алгоритмам. Во-первых, выравнивание кромок является параллельной операцией. Каждый элемент данных также является процессором (к нему применяются законы физики). Итак, в общем случае вы масштабируете доступную обработку с n, по существу разделяя вашу классическую сложность на коэффициент на n.

во-вторых, как выравнивание краев выполняет сортировку? Реальная сортировка находится в считывании, которое позволяет вам найти самый длинный за один шаг, даже если вы сделал сравните все из них, чтобы найти самый длинный. Опять же, разделите на коэффициент n, поэтому нахождение наибольшего теперь O (1).

другой пример - использование аналоговых вычислений: физическая модель решает проблему "мгновенно", а подготовительная работа-O(n). В принципе, вычисление масштабируется с количеством взаимодействующих компонентов, а не с количеством взаимодействующих компонентов. количество подготовленных элементов. Таким образом, вычислительные масштабы с n2. Пример, о котором я думаю,-это взвешенное многофакторное вычисление, которое было сделано путем сверления отверстий в карте, подвешивания Весов из строк, проходящих через отверстия, и сбора всех строк на кольце.

сортировка по-прежнему O(n) общее время. Что это быстрее, чем это из-за распараллеливание.

вы можете рассматривать центрифугу как Bucketsort из n атомов, распараллеленных по n ядрам (каждый атом действует как процессор).

вы можете сделать сортировку быстрее путем распараллеливания, но только с постоянным коэффициентом, потому что количество процессоров ограничено, O(n/C) по-прежнему O(n) (процессоры обычно имеют

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

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

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

было бы возможно с некоторыми накладными расходами на каждом узле (некоторое значение или метод привязан к каждому из узлов), чтобы "заставить" порядок список?

при сортировке с помощью компьютерных программ мы выбираем свойство сортируемых значений. Это обычно величина числа или алфавитный порядок.

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

эта аналогия метко напоминает мне о простой пузырьковой сортировке. Как меньшие числа пузырятся в каждой итерации. Как и твоя центрифужная логика.

Итак, чтобы ответить на этот вопрос, разве мы на самом деле не делаем что-то подобное в Сортировке на основе программного обеспечения?

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

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

другая перспектива заключается в том, что то, что вы описываете с помощью центрифуги, аналогично тому, что было названо "спагетти" (https://en.wikipedia.org/wiki/Spaghetti_sort). скажем, у вас есть коробка сырых спагетти стержней различной длины. Держите их в кулаке, и ослабьте руку, чтобы опустить их вертикально, так что концы все отдыхают на горизонтальном столе. Бум! Они отсортированы по высоте. О(постоянное) время. (Или O (n) если вы включаете выбор стержней по высоте и положив их в А. . . спагетти стойку, я думаю?)

вы можете отметить там, что это O(константа) в количестве кусочков спагетти, но, из-за конечной скорости звука в спагетти, Это O(n) в длине самой длинной нити. Так что ничего не приходит бесплатно.

рассмотрим: является ли "центрифуга сортировка"действительно масштабирование лучше? Подумайте о том, что происходит, когда вы увеличиваете масштаб.

• пробирки должны становиться все длиннее и длиннее.
• тяжелые вещи, чтобы ехать дальше и дальше, чтобы добраться до дна.
• момент инерции увеличивается, требуя больше мощности и больше времени для ускорения до скорости сортировки.

также стоит рассмотреть другие проблемы с сортировкой центрифуги. Для например, вы можете работать только в узком масштабе размеров. Алгоритм сортировки компьютера может обрабатывать целые числа от 1 до 2^1024 и выше, без проблем. Поместите что-то, что весит в 2^1024 раза больше, чем атом водорода в центрифугу, и, ну, это черная дыра, и галактика была уничтожена. Алгоритм не сработал.

конечно, реальный ответ здесь заключается в том, что вычислительная сложность относительно некоторой вычислительной модели, как упоминалось в другом ответе. А "центрифужная сортировка" -нет имеет смысл в контексте общих вычислительных моделей, таких как модель ОЗУ или модель ввода-вывода или многолучевые машины Тьюринга.