我最近一直在考虑在排序算法中使用面向对象的设计。然而,我无法找到一种正确的方法来更接近地实现在 O(n) 时间内进行排序的排序算法。
好吧,这就是我一周来一直在想的事情。我有一组输入数据。我将为每个输入数据分配一个质量(假设输入数据的类型为Mass
和一种类型Sphere
。如果我们假设所有物体都是形状与其质量成正比的完美球形物体,那么最重的物体首先接触地面。)。我将把所有输入数据放置在距地球相同距离的空间中。我会让他们自由落体。根据万有引力定律,最重的物体首先落地。它们击中的顺序将为我提供排序后的数据。这在某种程度上很有趣,但在内心深处,我觉得使用我迄今为止学到的面向对象应该可以做到这一点
真的有可能制作一种使用重力拉力的排序技术吗?还是我愚蠢/疯狂?
Edit:事实证明所有物体同时撞击地面,因此我引入了球形物体的概念。
问题是,虽然其中之一ideasOOP 的目的可能是对现实世界进行建模,但这并不意味着现实世界中某件事需要多长时间与用计算机模拟它需要多长时间之间存在直接对应关系。
想象一下您的程序所需的实际步骤:
- 必须为数据集中的每个项目构建一个对象。在大多数现代硬件上,仅此一项就需要迭代,因此会使您的策略为 O(n)best.
- 对于每个对象,都需要模拟重力的影响。同样,最明显、最直接的实现方式就是迭代。
- 必须捕获编程模型中每个对象降落在“地球”表面的时间,并且通过某种特定于实现的机制,需要将相应的对象插入到有序列表中。
考虑这个问题会进一步引入额外的复杂性。问问自己:您需要将这些物体放置在多高的位置才能开始?显然足够高,所以实际上最大的一个falls;即距离地球比最大物体的半径更远。但你怎么知道那有多远呢?您需要首先确定集合中最大的对象;这(可能)再次需要迭代。此外,人们可能会想象这种模拟可以是多线程的,以尝试模拟对象概念的实时行为actually坠落;但随后您会发现自己可能在检测到新冲突的同时尝试将项目添加到集合中(该操作显然需要非零时间)。因此这也会产生线程问题。
简而言之,我很难想象如何在没有特殊硬件的情况下仅使用 OOP 来正确实现这个想法。这么说来,确实是is一个好主意。事实上,它让我想起珠子排序 http://en.wikipedia.org/wiki/Bead_sort——一种算法,虽然与你的想法不同,但也是一种利用重力物理概念的排序解决方案,并且毫不奇怪地需要专门的硬件。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)