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

Question

我有一個帖子列表，其中每個帖子都包含一個標籤列表。什麼是尋找與標籤相似的帖子的最有效方式？也就是說，如何在與當前帖子相似的標籤數量之後對帖子列表進行排序？

我一直在試驗嵌套的for-loops，比較器和哈希映射，但我無法弄清楚什麼是最簡單的時間複雜的方法。

Answer 1

您可以使用當前帖子計算列表中每個帖子的標籤的相似度 - 它會採用線性O(n)時間，然後對O(n log(n))時間進行排序，因此您的算法完全適用於O(n log(n))。

如果不掃描所有帖子的所有標籤並且沒有索引，則無法比較相似度。

至於索引 - 有可能建立我。即倒排索引，如標籤 - >一組帖子，並用它來查找具有相同標籤的帖子並僅對其進行排序（可能是您可以跳過與當前無關的帖子 - 取決於業務需求）。但假設你仍然需要排序 - 它仍然會是O(n log(n))，但通常n應該更小