Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我有一个帖子列表,其中每个帖子都包含一个标签列表。找到关于标签的类似帖子的最有效方法是什么?也就是说,我将如何根据与当前帖子的相似标签数量对帖子列表进行排序?
我一直在尝试嵌套的 for 循环、比较器和哈希映射,但我无法弄清楚时间复杂度最低的方法是什么。
您可以计算列表中每个帖子与当前帖子的标签的相似性 - 它需要线性O(n)时间,然后对O(n log(n))时间进行排序,因此您的算法将完全适用O(n log(n))。
O(n)
O(n log(n))
如果不扫描所有帖子的所有标签并且没有索引,则无法比较相似性。
至于索引 - 有可能构建反向索引,例如标签 - >帖子集并使用它来查找具有相同标签的帖子并仅对它们进行排序(也许你可以跳过与当前无关的帖子- 取决于业务需求)。但是假设您仍然需要排序 - 它仍然会O(n log(n))但通常 n 应该更小