场景：在我的应用程序中，用户可以关注帖子。只要他们的朋友喜欢这个帖子，他们就会收到通知。当成千上万的用户关注并喜欢一篇帖子时，这个问题就变得不那么重要了。
我目前的方法很简单，当一个新用户喜欢一篇帖子时，遍历所有关注该帖子的用户，并检查新用户是否存在于他们的朋友列表中(假设平均大小为N(。我索引了朋友列表，所以查找是O(logN)，这意味着对于每个新的赞，如果有k个人在关注帖子，则计算是O(klogN)，并且由于有k个用户喜欢它，则总体复杂度变为O(k^2logN)。我能做得更好吗？
注：
- 通知不必是即时的，也不必100%发生
- 帖子由用户创建
- 我正在使用Firestore，一个NoSQL数据库，如果这很重要的话
您需要使用的是一种混合方法。利用用户好友列表可能比关注者数量短的事实，反之亦然。有两种选择：
-
现在就做，并根据新用户的好友列表检查每个关注者。时间复杂性反映了追随者的数量。
-
执行相反的操作，并根据帖子的关注者列表检查用户的每个朋友。时间复杂性反映了用户的好友数量。
有了这些策略，现在我们设计了一个算法来检查两者中的哪一个会给出更好的性能。
记录每个用户的好友数量和帖子的关注者数量。当有人喜欢一篇帖子时，如果他们的朋友比喜欢该帖子的人少，那么检查每个朋友是否都在关注者列表中会更快(在实现中使用自平衡BST或哈希表(。如果关注者的数量少于用户的朋友数量，那么反过来会更快。
如果有N个关注者、K个喜欢帖子的用户和F个朋友，则检查好友->关注者将给出O(N*F*log(K))的运行时间，而关注者->好友将是O(N*K*log(F))。最坏的情况仍然是一样的，但是，如果你只关心理论时间界限，那么你可以用哈希表代替你的索引表，不管怎样，它都是O(1)，而不是O(log(n))。
我认为可以通过使用更多的内存空间将其改进为N^2 + k logN^2。这个问题从根本上讲是寻找两个集合(新点赞用户的朋友集和关注者集，或者关注者的朋友集与点赞用户集(的交集。由于仰视是便宜的，我们想让要仰视的布景尽可能大。因此，如果我们把所有追随者的所有朋友放在一个N^2大小的大集合(更具体地说是一个地图(中，如果有k个喜欢的用户，它就会变成k logN^2，再加上N^2的初始迭代
将好友聚合在一起的额外好处是，许多用户都有共同的好友，因此实际大小可能小于N^2