重力排序:这可能是以编程方式吗？

Question

我最近一直在考虑在排序算法中使用面向对象的设计.然而,我无法找到一种合适的方法来进一步制作这种在O(n)时间内进行排序的排序算法.

好的,这是我一周以来的想法.我有一组输入数据.我将为每个输入数据分配一个质量(假设输入数据的类型Mass和类型Sphere.如果我们假设所有对象都是完美的球形物体,其形状与其质量成比例,则最重的物体首先接触地面.).我将把所有输入数据放在距离地球相同距离的空间中.我会让他们自由落体.根据引力定律,最重的一个首先击中地面.它们命中的顺序将为我提供排序数据.这在某种程度上很有趣,但在下面我觉得应该可以使用我迄今为止学到的OO

真的有可能制作一种使用引力拉动场景的分类技术,还是我愚蠢/疯狂？

编辑:同时关闭所有撞击地面的物体,因此我引入了球形物体概念.

Answer 1

问题是,虽然OOP的一个想法可能是对现实世界进行建模,但这并不意味着在现实世界中某些东西需要多长时间与用计算机模拟它需要多长时间.

想象一下您的程序所需的实际步骤:

1. 必须为数据集中的每个项构造一个对象.在最现代化的硬件,仅此一项就需要迭代,因此将让你的战略,为O(n)的最好的.
2. 对于每个物体,需要模拟重力的影响.同样,实现这一点的最明显,最直接的方法是迭代.
3. 必须捕获每个对象在编程模型中落在"地球"表面上的时间,并且通过某些特定于实现的机制,相应的对象将需要作为结果插入到有序列表中.

考虑到该问题进一步引入了其他复杂性.问问自己:你需要多高才能开始定位这些物体？显然足够高,以致最大的一个实际上下降 ; 即离地球比最大物体的半径更远.但你怎么知道那是多远？您需要首先确定集合中的最大对象; 再次,这将(可能)需要迭代.此外,人们可能会想象这个模拟可能是多线程的,试图模拟实际下降的对象概念的实时行为; 但是你会发现自己试图在检测到新碰撞的同时向一个集合中添加项目(显然需要非零时间的操作).所以这也会产生线程问题.

简而言之,我很难想象如何在没有特殊硬件的情况下使用OOP正确实现这个想法.这就是说,它真的是一个好主意.事实上,它让我想起了Bead Sort -一种算法,它虽然与你的想法不一样,但它也是一种利用重力的物理概念的排序解决方案,并且毫不奇怪,它需要专门的硬件.

Answer 2

你刚刚重申了这个问题.计算引力效应的顺序最多只能是你想要击败的排序算法的O.

Answer 3

引力计算仅在现实世界中是免费的.在程序中,您需要对其进行建模.这将是复杂性最小的另一个

Answer 4

这个想法可能看起来很简单,但在这种情况下,现实世界和模型之间的区别在于,在现实世界中,一切都是并行发生的.要按照您描述的方式对引力排序进行建模,您必须首先将每个对象放在一个单独的线程上,并使用线程安全的方式按照它们完成的顺序将它们添加到列表中.实际上,在排序性能方面,您可能只是对时间进行快速排序,或者因为它们与下降速率处于相同的距离.但是,如果你的公式与质量成正比,你只需跳过所有这些并对质量进行排序.

Answer 5

通用分类最好是O(n log n).要改进这一点,您必须了解数据,而不仅仅是如何比较值.

如果值都是数字,则基数排序给出O(n),假设您有数字的上限和下限.这种方法可以扩展到处理任何数字 - 最终,计算机中的所有数据都使用数字表示.例如,您可以在每个传递中对字符串进行基数排序,按一个字符排序,就好像它是一个数字一样.

不幸的是,处理可变大小的数据意味着通过基数排序进行可变数量的传递.最终得到O(n log m),其中m是最大值(因为对于无符号,k位给出的值最多为(2 ^ k)-1,对于有符号则为一半).例如,如果要将整数从0到m-1排序,那么你实际上已经再次获得了O(n log n).

将一个问题转换为另一个问题可能是一种非常好的方法,但有时它只是增加了另一层复杂性和开销.