根据投票响应来确定用户的“唯一性”的最大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行。显然，并不是所有的用户都会回答每个投票问题。这会影响时间复杂度的计算吗？)*

Answer 1

让我们让n =用户数，p =投票问题数，r =响应表中的总行数。(在您的示例中为n = 25,000、p = 400、r = 500,000。)

对于单个用户，数据库将遍历所有响应，对每个响应执行散列查找，以确定它是否与该用户的响应之一匹配。如果是这样，则需要O(1)时间来跟踪运行中的计数。然后，它接受该用户的民意调查问题，并进行简单的求和。只要响应的数量远远大于投票问题的数量(在您的情况下)，这将由运行响应的时间决定。所以每个用户都要花时间O(r)。您有n用户，因此总时间为O(n*r)。