按相似元素的元素排序列表

Question

我有一个帖子列表，其中每个帖子都包含一个标签列表。什么是寻找与标签相似的帖子的最有效方式？也就是说，如何在与当前帖子相似的标签数量之后对帖子列表进行排序？

我一直在试验嵌套的for-loops，比较器和哈希映射，但我无法弄清楚什么是最简单的时间复杂的方法。

Answer 1

您可以使用当前帖子计算列表中每个帖子的标签的相似度 - 它会采用线性O(n)时间，然后对O(n log(n))时间进行排序，因此您的算法完全适用于O(n log(n))。

如果不扫描所有帖子的所有标签并且没有索引，则无法比较相似度。

至于索引 - 有可能建立我。即倒排索引，如标签 - >一组帖子，并用它来查找具有相同标签的帖子并仅对其进行排序（可能是您可以跳过与当前无关的帖子 - 取决于业务需求）。但假设你仍然需要排序 - 它仍然会是O(n log(n))，但通常n应该更小