我想对由人类执行比较的项目进行排序：
对于这些任务，比较次数是性能的限制因素。
- 需要的最少比较次数是多少（我假设>N for N items)?
- 哪种算法可以保证这个最小数量？
为了回答这个问题，我们需要做出很多假设。
假设我们正在按可爱程度对图片进行排序。目标是在最短的时间内从人类那里获得最大的可用信息。这种交互将主导所有其他计算，因此它是唯一重要的一种。
正如其他人提到的，人类可以很好地在一次交互中订购多个商品。假设我们每轮可以按相对顺序获得八个项目。
每轮将七个边引入有向图中，其中节点是图片。如果节点 A 可从节点 B 访问，则节点 A 比节点 B 更可爱。请记住此图。
现在，让我告诉你一个海军和空军以不同方式解决的问题。他们都希望快速、有序地召集一群人。海军告诉人们排队，如果你比前面的人矮，就交换位置，然后重复直到完成。最坏的情况是N*N比较。
空军告诉人们要站在方格内。他们对 sqrt(N) 个人进行从前到后的洗牌，这意味着最坏情况 sqrt(N)*sqrt(N) == N 比较。然而，人们只能按照一个维度进行排序。因此，人们面向左，然后再次进行相同的洗牌。现在我们进行了 2*N 次比较，排序仍然不完美，但对于政府工作来说已经足够了。有一个短角，对面有一个高角，还有明显的对角线高度梯度。
如果您不关心完美，您可以看到空军方法如何在更短的时间内获得结果。您还可以了解如何有效地达到完美。您已经知道最矮和最长的人位于两个角落。第二矮的可能在最矮的后面或旁边，第三矮的可能在他的后面或旁边。一般来说，某人的身高等级也是他距短角球的最大可能曼哈顿距离。
回顾一下图的类比，每轮呈现的八个节点是当前最长入站路径最常见长度的八个节点。最长入站路径的长度也表示节点的最小可能排序等级。
遵循此计划，您将使用大量 CPU，但您将最大限度地利用您的人力资源。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
