Algorithm

使用map降低算法的时间复杂度

在前两周在开发新接口时,遇到了今天要介绍的两种场景,我都通过map降低了整个算法的时间复杂度。我认为有必要记录一下思考过程,也顺便分享给各位读者。虽然简单,但确实很好用。 1. 群组中的好友 背景 各位读者应该都知道在微信聊天框中输入@之后,会出现各群员的列表。新接口功能上差不多,只是在这基础上还要加上一个限制条件:“列表中的群成员必须是好友”。我可以从其他微服务已经有的“好友接口”获取某一个用户的好友列表(list),那么我只需要找出和群成员列表的交集即可。 实现 当时想到有两种方法可以实现上面说的效果(设群有N个群成员,M个好友): 采用两层遍历查询方式,遍历群成员list + 二分查找好友list(查询的时间复杂度:O(N * logM)) 采用map,将群成员id作为map的key,role作为value(查询的时间复杂度:O(1)) 哪种方式更好?通过时间复杂度来看,答案就不言而喻了。部分代码如下: // 获取群内成员(我的源码有用到role做别的业务逻辑处理) func GetMemberInGroup(groupID int64) (map[int64]int8, error) dataSet := make(map[int64]int8) strSql :=...

Continue reading...

根据离散函数概率返回int值

笔者在阅读《算法》一书的时候看到这样一道示例题,刚开始没有想清楚,而后结合一些帖子和高数的知识便将算法想要传达的意思想明白了,下边我会从均匀分布函数开始记录笔者思考的过程。 简单回顾均匀分布函数的知识,更多详情资料读者需自行查阅。 均匀分布也叫矩形分布,是指任意相同间隔所对应的概率分布都相等,该分布有两个参数:最小值(a)和最大值(b),缩写为U(a, b)。函数为: 当a=0,b=1时,为标准均匀分布。 对Java语言的Random库,似乎只能产生服从正态分布N(0,1)和均匀分布U(0,1)的随机数,那么如何按照特定的概率生成随机数呢? X 0 1 P(X = x) p 1 – p 容易想到,对于服从均匀分布U(0,1)的随机变量,产生的随机数落在[0,p)的概率就为p, 而落在[p,1)的概率为1−p。 接下来,我们考虑稍微复杂的情况: X 0 1 2 P(X = x)...

Continue reading...