算法:从用户列表中查找朋友

您需要使用混合方法。利用这样一个事实:用户朋友列表可能比关注者的数量短,反之亦然。有两种选择:

• 做你现在做的,然后检查 每个追随者 反对新用户的 朋友名单 . 时间复杂性反映了追随者的数量。

• 倒过来检查一下 每一个朋友 对用户的 追随者名单 担任职务。时间复杂性反映了用户的朋友数量。

在这些策略的帮助下,我们设计了一个算法来检查这两个算法中哪一个性能更好。

保持一个活跃的计数,每个用户的朋友数量,以及一个帖子的追随者。当有人喜欢一个帖子时,如果他们的朋友比喜欢这个帖子的人少,那么检查每个朋友是否在关注者列表中会更快(在实现中使用一个自平衡的BST或哈希表)。如果追随者比用户的朋友少,那么反向的速度会更快。

如果有n个追随者,k个用户喜欢这个帖子,f个朋友,那么检查朋友--gt;追随者会给出运行时间 O(N*F*log(K)) 和追随者——朋友 O(N*K*log(F)) . 最坏的情况仍然是一样的,但是如果您只关心理论上的时间界限,那么您可以用哈希表替换索引表,不管怎样,这是 O(1) 而不是 O(log(n)) 不管怎样。

我想可以改进到 N^2 + k logN^2 通过使用更多的内存空间。这个问题从根本上说就是找到两个集合的交集(新喜欢的用户的朋友集和追随者的朋友集,或者追随者的朋友集和喜欢的用户的朋友集)。因为查找是便宜的,我们想使要查找的集尽可能大。所以如果我们把所有追随者的朋友放在一个大的集合(更具体地说是一张地图)中 N^2 它变成了 k logN^2 如果有k个喜欢的用户,加上初始迭代 N 2

将朋友聚合在一起的另一个好处是,许多用户有共同的朋友,因此实际大小可能小于 N 2