2

我有一个用户对是/否投票问题的回答的 MySQL 表。看起来有点像这样：

| user_id    | poll_id    | response
| 111        | 1         | 'yes'
| 111        | 2         | 'no'
| 111        | 3         | 'no'
| 222        | 1         | 'yes'
| 222        | 2         | 'yes'
| 222        | 3         | 'yes'
| 333        | 1         | 'no'
| 333        | 2         | 'no'
| 333        | 3         | 'no'

对于给定的 user_id，我想计算他们的响应与每个其他用户的响应之间的相似性。因此，用户 111 和用户 222 的相似度为 0.333（因为他们有 3 个相同的响应中的 1 个），用户 111 和用户 333 的相似度为 0.666（因为他们有 3 个相同的响应中的 2 个）。

然后，我想确定给定用户的相似度中值，并将其与所有其他用户的相似度中值进行排名，以衡量该用户的“唯一性”。

这种操作的时间复杂度是多少？

*（注意：目前，我的响应表中大约有 25,000 个 user_ids、400 个 poll_ids 和大约 500,000 行。显然，并非所有用户都对每个投票问题做出响应。这会影响时间复杂度计算吗？）*

4

2 回答 2

2

对于每个用户，您必须计算与所有其他用户的相似度；那是n 2 - n，或者实际上是n 2。但是您还必须对这些结果进行排序以找到中位数。因此，假设您的排序是n log n，主要术语将是n 2 log n。

如果您使用均值而不是中位数，则可以摆脱排序；那么时间复杂度将是O(n 2 )。

于 2012-04-26T14:35:07.303 回答
0

让我们让n= 用户数、p= 投票问题数和r= 响应表中的总行数。（在你的情况下n = 25,000，，，p = 400。r = 500,000）

对于单个用户，数据库将遍历所有响应，每个响应都进行哈希查找以确定它是否与该用户的响应之一匹配。如果确实如此，则需要O(1)时间来跟踪运行记录。然后，它会接受该用户的投票问题并进行简单的求和。只要响应的数量远大于投票问题的数量（在您的情况下），这取决于通过响应的时间。所以每个用户都需要时间O(r)。你有n用户，所以总时间是O(n*r).

于 2012-04-26T14:45:42.913 回答