优化算法以减少时间复杂度（使用redis数据类型）
在我的网站中，用户正在创建他们的社交网络。这会导致通知传送到网络中的相关节点。例如。好友请求、点赞、评论，都为网络中的相关节点生成一个通知。
为了保持一切透明，用户可以在单独的URL中以列表的形式查看他们的相关通知。此列表由一个支持Redis的排序集支持，称为ss:
。排序集包含散列ID以及自纪元以来的时间（作为分数)。例如：
hash_id | updated_at
np:1:0:544 | 1482234321.48124
np:1:2:454 | 1482235629.73111
np:1:1:701 | 1482237000.59143
而且，每个通知都是可见的或不可见的。这个seed状态存储在相关的散列中，位于键s处。例如。哈希np:1:0:544中的s键为false；告诉我们这是一个看不见的通知。足够简单。
我已经在做的事：
1）从ss:
中获取得分高于cut-off的所有hash_id。例如zrangebyscore ss:
（用redis术语）。
2）遍历每个hash_id，检查它的s键（即。seen键）。如果s为false，则增加一个计数器。例如，为每个哈希对象执行dohget hash_name s。如果返回的值为false，incr一个单独的redis计数器。
步骤1的时间复杂度为O(log(N)+m)。步骤2是O(M)。最大值可能为O(N)。
我需要改进的地方：
有没有什么方法可以降低时间复杂度（例如O(log(N))？例如使用复合索引和词典排序？
性能至关重要；这样的计算在我的网站上每天会发生200万次（并且不断扩大），所以我正在寻找提高可伸缩性的方法。
注意：当然，我可以采取其他措施来减轻这台algo的负荷（例如，降低其发生率，改善基础设施等），但这些都是不同的考虑因素。
共有1个答案
我改变了我的方法。
排序集的score（即updated_at)现在为time.time()+seen[status]其中seen={true:2000000000,false:4000000000}。这将自动按已见和未见对键进行排序，同时保留时间信息（按score-seen[status])。
总体而言，这种方法使我能够从计算中删除步骤2。时间复杂度降低到O（log(N)）。最重要的是，智能制定指数能够真正推动业绩。对于任何感兴趣的人，这里有一篇关于复杂的索引如何完成各种任务的信息性阅读。
-
我有一个算法可以检查是否可以解决游戏行。游戏行是一个正整数数组，其中最后一个元素为 0。游戏标记从索引 0 开始，沿着数组移动它所在的整数指示的步数。 例如，[1，1，0]返回true，而[1，2，0]返回false。标记也可以向左或向右移动以解决游戏。也就是说，[3，3，2，2，0]是可解的。 我尝试了一些游戏行示例，并计算了最坏情况下的时间复杂度： 其他情况下给我的数字，我找不到与输入大小的关
-
注：∈/ 意思是不在，我不能在代码中输入。 这个问题可能与一些帖子重复。 理解Dijkstra算法的时间复杂度计算 Dijkstra算法的复杂性 Dijkstras算法的复杂性 我读过它们，甚至读过Quora上的一些帖子，但仍然无法理解。我在伪代码中添加了一些注释，并试图解决它。我真搞不懂为什么它是O（E log V）
-
Dijkstra算法的这种特殊实现的时间复杂度是多少？ 我知道这个问题的几个答案是，当你使用最小堆时，O（E log V），这篇文章和这篇文章也是如此。然而，这里的文章说的是O（V ElogE），它的逻辑与下面的代码类似（但不完全相同）。 算法的不同实现可以改变时间复杂度，我试图分析下面实现的复杂性，但是像检查和忽略中的重复顶点这样的优化让我怀疑自己。 以下是伪代码： 笔记： 从源顶点可到达的每个
-
如何计算以下函数的时间复杂度？ 现在，我知道循环具有O（n）时间复杂度，但在这种情况下，I以更快的速度增长。一次又一次地迭代，我发现，对于每一个第m次迭代，I=m^2。但我仍然不知道如何计算大O。
-
我最近了解了杂耍算法如何在线性时间内旋转数组 时间复杂度如何线性？？？