10

假设我拥有 100 个视频游戏，我想将它们从最喜欢到最不喜欢的顺序排列。很难给每个视频游戏一个代表我有多喜欢它的数值，所以我想把它们相互比较。

我想出的一种解决方案是随机选择 2 个视频游戏，然后选择我更喜欢的一个，然后丢弃另一个。不幸的是，这个解决方案只让我知道排名第一的视频游戏，因为那将是最后一个，并且几乎没有提供关于其他游戏的信息。然后我可以对其他 99 个视频游戏重复这个过程，依此类推，但这是非常不切实际的：O(n^2)。

是否有任何 O(n)（或只是合理的）算法可用于根据相关标准对数据进行排序？

4

10 回答 10

3

如果你想按顺序展示游戏，你需要决定它。

可以从一组成对比较中得出顺序。

这是一个例子。你有 100 个视频游戏。我们假设每个视频游戏都与一个参数ai相关联（其中 i 的范围从 1 到 100）。这是一个实数，描述了您对游戏的“喜欢程度”。我们还不知道这些参数的值。然后，我们选择一个函数来描述您在参数方面更喜欢视频游戏 i 而不是视频游戏 j 的可能性。我们选择逻辑曲线并定义

P[i 优于 j] = 1/(1+e a j - a i )

现在当 a i = a j你有 P = 0.5，当 a i = 1 和 a j = 0 你有 P = 1/(1 + e -1 ) = 0.73，表明相对较高的参数值增加了相应视频游戏被首选的概率。

现在，当您在表格中获得实际比较结果时，您可以使用最大似然法计算参数 a i的实际值。然后按计算参数的降序对视频游戏进行排序。

发生的情况是，最大似然法计算参数ai的值，使实际观察到的偏好尽可能地可能，因此计算的参数代表了对视频游戏之间总排序的最佳猜测。请注意，为此，您需要将视频游戏与其他视频游戏进行足够多次比较——每个游戏都需要至少一次比较，并且比较不能形成不相交的子集（例如，您将 A 与 B 与 C 与 A 进行比较，和 D 到 E 到 F 到 D，但是 {A,B,C} 的游戏和 {D,E,F} 的游戏之间没有可比性）。

于 2013-07-17T13:29:14.157 回答
1

您可以使用快速排序又名枢轴排序。选择一个游戏，并与其他游戏进行比较，这样你就有一组更差的游戏和更好的游戏。递归地重复每一半。平均案例性能为 n log n。

http://en.wikipedia.org/wiki/Quicksort

于 2013-07-16T20:46:24.420 回答
0

至于是否有O(n)办法对 n 个对象进行排序，没有。这种排序的下限是O(nlogn).

然而，有一种特殊情况。如果您有一个独特且有限的偏好，那么您可以执行所谓的桶排序。

如果没有两场比赛打成平手，则偏好是唯一的。如果您的偏好存在最小值和最大值，则偏好是有界的。

让我们1 .. m成为您游戏的界限。

只需创建一个包含元素的数组m，然后根据您的喜好将每个游戏放在索引中。

现在您可以对数组进行线性扫描以获取排序顺序。

但当然，这不是基于比较的。

于 2013-07-16T20:46:20.190 回答
0

首先，您可以保留一个列表并使用二进制搜索一个一个地插入每个元素，从而为您提供一种O(n log n)方法。

我也确定你打不过O(n log n)，除非我误解了你想要什么。基本上，您告诉我的是您希望能够仅使用比较对某些元素（在您的示例中，视频游戏）进行排序。

把你的算法想象成这样：你从n!排列游戏的可能方式开始，每次进行比较时，你将排列分成POSSIBLE和IMPOSSIBLE，丢弃后一组。（这里的可能意味着排列与您所做的比较一致）

在最坏的情况下，该POSSIBLE组始终至少与该IMPOSSIBLE组一样大。在这种情况下，您的任何比较都不会将搜索空间减少至少 2 倍，这意味着您至少需要log_2(n!) = O(n log n)比较才能将空间减少到 1，从而为您提供游戏排序。

于 2013-07-16T20:48:20.173 回答
0

虽然不是 O(n)，但成对比较是一种对集合中的元素进行相对排名的方法。

实现算法：

  1. 创建一个 100x100 矩阵
  2. 每一行代表一部电影，每一列代表一部电影。r1 处的电影与 c1 处的电影相同，r2=c2...r100=c100。

下面是一些快速的伪代码来描述该算法： 


    for each row
        for each column
            if row is better than column
                row.score++
            else 
                column.score++
            end
        end
    movie_rating = movie[row] + movie[column]
    sort_by_movie_rating()

于 2013-07-17T17:26:01.760 回答
0

我不认为它可以在 O(n) 时间内完成。我们能得到的最好的结果是使用合并或快速排序的 O(nlogn)。

于 2013-07-17T13:46:03.993 回答
0

一种可能性是创建几个标准C1, C2, ..., Cn，例如：

  • 视频质量
  • 困难
  • 情景兴趣
  • ...

你通过这个筛子通过每场比赛。

然后你比较游戏对的子集（2 级选择），并告诉你更喜欢哪一个。存在一些多标准决策/分析（MCDM 或 MCDA）算法，可以将您的 2 等级选择转换为多标准等级函数，例如可以计算系数 a1，...，构建一个线性排序函数a1*C1+a2*C2+...+an*Cn。

好的算法不会让你随机选择对，而是会根据非支配子集向你推荐要比较的对。

请参阅 wikipedia http://en.wikipedia.org/wiki/Multi-criteria_decision_analysis，它提供了一些有用的链接，并准备好做/阅读一些数学。

或者购买像 ModeFrontier 这样嵌入了一些算法的软件（如果只是为了对库进行排名，那就有点贵了）。

于 2013-07-16T21:02:45.210 回答
0

我会解决这个问题的方法是有一个包含游戏标题和计数槽的数组。

Object[][] Games = new Object[100][2];
Games[0][0] = "Game Title1";
Games[0][1] = 2;
Games[1][0] = "Game Title2";
Games[1][1] = 1;

每次您投票时，它都应该在Games[*][1]插槽中添加一个，然后您可以从那里进行排序。

于 2013-07-17T15:00:41.553 回答
0

其他方法是扩展您的想法。显示超过 2 个游戏并按您的评分对其进行排序。这个想法类似于合并排序来评价你的游戏。如果您正确选择游戏进行评分，则无需进行大量迭代。只是一点点。IMO O(n) 将非常困难，因为您（作为人类）的观察是有限的。

于 2013-07-16T20:39:18.793 回答
-1

我知道很难量化你喜欢某样东西的程度，但如果你创建了几个“领域”来评判每场比赛怎么办：

graphics
story
multiplayer
etc...

为每个类别给出 5 分中的 1-5 分（更改您认为更重要的类别的权重）。尝试创建一个客观的评判标准（可能使用外部资源，例如 metacritic）

然后你把它们加起来，给出你喜欢它们的总体评价。然后使用排序算法（MergeSort？InsertionSort？）将它们按顺序排列。O(n*m+nlogn) [n = games, m = categories]考虑到 m 可能非常小，这将是非常好的。

如果你真的下定了决心，你可以使用机器学习根据你过去的选择来估计未来的游戏。

于 2013-07-16T20:33:41.373 回答