【大话IT】分析有趣算法背后的计算原理，从时间复杂度说起。。。

Aquarius_Joe · 发表于 2017-6-30 09:47

支持一下！

陌路巨额投入 · 发表于 2017-7-4 16:50

随机数的计算
在搜索排序中，有些时候我们需要给每个搜索文档的得分添加一个随机扰动，并且让该扰动符合某种概率分布。假设我们有一个概率密度函数f(x), min<=x<=max, 并且有
随机算法
那么可以利用f(x)和frand设计一个随机计算器r(frand()), 使得r(frand())返回的数据分布，符合概率密度函数f(x)。
令
随机算法
那么函数
随机算法
符合密度函数为f(x)的分布。
下面对这个以上的公式进行简单的证明：

由于g(x)是单调函数，并且x在[0,1]上均匀分布，那么

随机算法
由于上述公式太复杂，计算运算量大，在线上实时计算的时候通常采用线性差值的方法。
算法为：
1）在offline计算的时候，设有数组double A[N+1]；对于所有的i, 0<=i<=N, 令
随机算法
2）在线上实时计算的时候，
令f = frand()，
lindex = (int) (f* N);
rindex = lindex +1;
那么线性插值的结果为 A[lindex]*(A[rindex]-f) + A[rindex] * (f – A[lindex])
我们做了一组实验，令f(x)服从标准正太分布N(0,1)， N=10000，并利用该算法取得了200*N个数。对这些数做了个简单的统计，得到x轴上每个小区间的概率分布图。

随机算法

jieforest · 发表于 2017-7-7 11:14

对于程序员而言，研究算法是很有趣的工作。

下面列举一个以前看到的算法题，如下：
有3个水桶，编号为1#、2#、3#。其中，1#水桶的容积为3升，2#水桶的容积为5升，3#水桶的容积为8升。目前的情况是3#水桶中装满了水，1#和2#水桶是空的。三个水桶都没有体积刻度，现在需要将3#水桶中的8升水均分成两份，即每份水为4升，要求只能使用1#、2#、3#水桶来完成这个工作。

怎么办呢？
实现步骤如下：

【现状】
水桶：  1# 2# 3#
水量：  0    0    8

步骤1：3#向2#倒入5升水（0  5  3）
步骤2：2#向1#倒入3升水（3  2  3）
步骤3：1#向3#倒入3升水（0  2  6）
步骤4：2#向1#倒入2升水（2  0  6）
步骤5：3#向2#倒入5升水（2  5  1）
步骤6：2#向1#倒入1升水（3  4  1）
步骤7：1#向3#倒入3升水（0  4  4）

从而完成了8升水均分成两份的工作。

【算法实现】

我们采用长度为3的一维向量描述这个状态，这组向量的三个值分别是容积为8升的桶中的水量、容积为5升的桶中的水量和容积为3升的桶中的水量。因此算法的初始状态就可以描述为[8, 0, 0]，则终止状态为[4, 4, 0]。

倒水动作与静止状态的结合就产生了状态变化，持续的状态变化就产生了一棵状态树，这个状态树上的所有状态就构成了穷举算法的解空间。以初始状态[8, 0, 0]为例，如果与“倒5升水到5升水桶”动作相结合，就得到了一个新状态[3, 5, 0]，同样，如果与“倒3升水到3升水桶”动作相结合，就得到了另一个新状态[5, 0, 3]。以此类推，可以得到

nail78 · 发表于 2017-7-12 14:27

kmeans聚类算法：

这是最简单的聚类算法之一，算法试图将N个数据，划分成k个不同的类簇。是典型的基于距离的聚类算法，采用欧式距离作为相似性的指标，两个数据对象的距离越近，相似度就越大，算法认为簇是由距离靠近的对象组成的。

算法过程如下：
1）从N个数据对象中，随机选取K个作为中心点
2）计算其余的数据对象测量到中心点的距离，并归到距离最近的中心点的簇中
3）根据各个簇中的数据对象计算平均值，得到新的中心点
4）不停迭代第2）3）步，直到新的中心点与上次迭代前的中心点相等，或者小于一个阈值，算法结束

算法的计算复杂度是 O（NKt），N是数据对象的数目，K是簇的个数，t是迭代的次数