list - 通过一次显示两个项目来根据用户的偏好对列表中的项目进行排名的最有效方法是什么？

Question

在某些情况下，我建议观看 Tom Scott 的这段视频，他在该视频中确定了最好的“东西”是什么：https ://youtu.be/ALy6e7GbDRQ 。我认为这将有助于解释我的问题。

---

基本上，我正在尝试制作一个算法/程序，使一个用户通过一次选择他最喜欢两个项目之间的哪一个来对列表中的所有项目进行排名。

例如，最基本的列表有 3 个项目：A、B 和 C。操作顺序如下所示：

1. 向用户提供选择：A 或 C。
2. 他更喜欢C。
3. 向用户提供选择：B 或 C。
4. 他更喜欢C。
5. 向用户提供选择：A 或 B。
6. 他更喜欢A。

所以我们知道在 3 次比较中排名顺序是 [C > A > B]。

但是如果在第 4 步，用户会选择 B 怎么办？我们可以通过逻辑假设在第 5 步之前他更喜欢 B 而不是 A。所以我们会知道排名列表将是 [B > C > A] 仅在 2 比较中，它与第一种情况一样准确。因此，我们可以看到步数取决于用户的选择。

---

那么，在最少的比较次数中对所有项目进行排名的正确或最有效的方法是什么？我考虑过从字面上比较每个可能的组合，并为每次选择一个项目而不是另一个项目时上升的每个项目都有一个计数器。但是通过这种方式，要进行的比较次数将根据列表的大小呈指数增长，并且它不会像上面的示例中那样是最有效的方式。我还考虑过使用一种简单的排序算法，用户可以“手动”进行比较，但我对一般的排序算法不太熟悉。

在 Tom Scott 的视频中，该网站随机选择了两个项目，他使用了如此庞大的用户群，以至于问题只是通过概率和统计数据自行纠正，他无需担心每个项目都被平等地挑选以确保准确。由于我只希望一个用户对项目进行排名，因此我需要找到一种方法来选择正确的项目进行比较，以尽可能提高效率（我认为）。另一个区别是我不会像汤姆的版本那样拥有超过 7000 个项目。我想用它来排名例如“所有迪士尼电影”、“某些音乐流派”或“所有塞尔达视频游戏”，所以我很确定我最多可能有 100 个项目。

我的问题是：我在正确的轨道上吗？我应该使用一个简单的排序算法（如果是，我应该使用哪一个？）或者是唯一有效地做到这一点的数学方法是比较每个组合？还是我错过了可以帮助我的东西？如果我暴力破解每个组合，这显然是对项目进行排名的最简单和准确的方法，但肯定不是最有效的。我想比较的顺序和我们比较的项目真的很重要，这才是最有效的，这就是我迷失的地方。

我知道在这里问这不是一个真正的传统问题，但感谢您帮助我或引导我走上正确的道路。

标签： listalgorithmsortingcomparisonranking

Answer 1

假设用户将创建项目的总排序，算法应该维护一个由越来越多的项目组成的完全排序列表。取出下一个无序项并使用二分查找所需的比较将其插入有序列表中。

取下一个无序的项目并使用两个项目的二分搜索比较来插入它。

重复直到所有项目都被订购。

二分搜索应尽量减少每个阶段的比较，并随着时间的推移为每个新项目向用户提供更有意义的比较。