计算机科学中的排序与"真实"世界中的排序

我正在考虑用软件排序算法,以及可以克服O(nlogn)障碍的可能方法.我不认为在实际意义上可以更快地排序,所以请不要认为我这样做.

话虽如此,似乎几乎所有的排序算法,软件必须知道每个元素的位置.这是有道理的,否则,它如何知道根据某些排序标准放置每个元素的位置？

但是,当我将这个想法与现实世界交叉时,离心机不知道每个分子在按密度分类时的位置.事实上,它并不关心每个分子的位置.然而,由于每个分子都遵循密度和引力定律 - 这让我思考,因此它可以在相对较短的时间内将数万亿个项目分类万亿.

是否有可能在每个节点上有一些开销(某些值或方法加到每个节点上)以"强制"列表的顺序？像离心机这样的东西,只有每个元素都关心它在空间中的相对位置(与其他节点相关).或者,这是否违反了计算中的某些规则？

我认为这里提出的一个重点是自然的量子力学效应以及它们如何同时平行应用于所有粒子.

也许经典计算机固有地限制了对域的排序O(nlogn),其中量子计算机可能能够跨越该阈值并入O(logn)并行的算法.

离心机基本上是平行气泡排序似乎是正确的,其时间复杂度为O(n).

我想下一个想法是,如果大自然可以排序O(n),为什么不能计算机？

编辑:我误解了离心机的机制,看起来它做了一个比较,一个大规模平行的比较.但是,有些物理过程对正在排序的实体的属性进行操作,而不是比较两个属性.这个答案涵盖了那种性质的算法.

离心机应用的排序机制通过元件之间的比较实际上不起作用,但实际上是通过单独的每个元件上的属性("离心力")来实现的.一些排序算法属于这个主题,尤其是Radix Sort.当这种排序算法并行化时,它应该接近离心机的例子.

其他一些非比较排序算法是Bucket sort和Counting Sort.您可能会发现铲斗类型也符合离心机的一般概念(半径可能对应于箱柜).

另一个所谓的"排序算法"是单独考虑每个元素的是睡眠排序.在这里,时间而不是离心力作为用于分选的量级.

计算复杂性总是根据某些计算模型来定义.例如,如果在Brainfuck中实现,则典型计算机上的O(n)算法可能为O(2 ⁿ).

离心机计算模型具有一些有趣的特性; 例如:

它支持任意并行性; 无论溶液中有多少颗粒,它们都可以同时分选.

它没有按质量给出严格的线性粒子,而是非常接近(低能量)近似.

检查结果中的单个粒子是不可行的.

不可能通过不同的属性对粒子进行排序; 只支持质量.

鉴于我们没有能力在通用计算硬件中实现这样的功能,该模型可能没有实际意义; 但它仍然值得研究,看看是否有任何可以从中学到的东西.例如,非确定性算法和量子算法都是研究的活跃领域,尽管今天它们都没有实际实现.

诀窍在于,您只能使用离心机对列表进行排序.与其他真实世界的排序[需要引证]一样,您可以更改已对列表进行排序的概率,但如果不检查所有值(原子),则永远不会确定.

考虑一下这个问题:"你应该多久运行离心机？"
如果你只运行了一个皮秒,你的样本可能没有初始状态那样排序..或者如果你运行它几天,它可能是完全排序的.但是,如果没有实际检查内容,你就不会知道.

基于计算机的"订购"的真实世界示例将是彼此协作工作的自主无人机,称为"无人机群".无人机作为个人和团体行动和交流,并且可以跟踪多个目标.无人机共同决定哪些无人机将遵循哪些目标,以及明显需要避免无人机之间的碰撞.早期版本的这些无人机在保持阵型的同时通过航路点移动,但是阵型可能会发生变化.

对于"分类",无人机可以被编程为以特定顺序形成线或图案,最初以任何排列或形状释放,并且共同地并且平行地,它们将快速形成有序线或图案.

回到基于计算机的排序,一个问题是有一个主内存总线,并且大量对象无法在内存中并行移动.

知道每个元素的位置

在磁带排序的情况下,每个元素(记录)的位置仅对"磁带"是"已知的",而不是计算机.基于磁带的排序一次只需要处理两个元素,以及表示磁带上的运行边界(文件标记或不同大小的记录)的方法.