mysql - 根据民意调查响应确定用户的 "uniqueness"的大 O 是什么？

Question

我有一个 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 行。显然，并非所有用户都响应每个 poll 问题。这会影响时间复杂度计算吗？)*

Answer 1

对于每个用户，你必须计算与所有其他用户的相似度；即 n² - n，或者实际上是 n²。但您还必须对这些结果进行排序才能找到中位数。因此，假设您的排序为 n log n，则主导项将为 n² log n。

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