w1100n
This site is best viewed in Google Chrome
wiloon, 6/28/2015 10:05 | Tag:,

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/03.01.md 二叉查找树 由于红黑树本质上就是一棵二叉查找树,所以在了解红黑树之前,咱们先来看下二叉查找树。 二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树: 若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 任意结点的左、右子树也分别为二叉查找树。 没有键值相等的结点(no duplicate nodes)。 因为,一棵由n个结点,随机构造的二叉查找树的高度为lgn,所以顺理成章,一般操作的执行时间为O(lgn).(至于n个结点的二叉树高度为lgn的证明,可参考算法导论 第12章 二叉查找树 第12.4节)。 但二叉树若退化成了一棵具有n个结点的线性链后,则此些操作最坏情况运行时间为O(n)。后面我们会看到一种基于二叉查找树-红黑树,它通过一些性质使得树相对平衡,使得最终查找、插入、删除的时间复杂度最坏情况下依然为O(lgn)。 红黑树 前面我们已经说过,红黑树,本质上来说就是一棵二叉查找树,但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。 但它是如何保证一棵n个结点的红黑树的高度始终保持在h = logn的呢?这就引出了红黑树的5条性质: 1)每个结点要么是红的,要么是黑的。 2)根结点是黑的。 3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。 4)如果一个结点是红的,那么它的俩个儿子都是黑的。 5)对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 正是红黑树的这5条性质,使得一棵n个结点是红黑树始终保持了logn的高度,从而也就解释了上面我们所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论的原因。

wiloon, 1/26/2015 2:33 | Tag:

http://www.cnblogs.com/younggun/p/3249772.html 一、逢“几”中奖 逢“几”中奖,即通过预估抽奖人数和奖品数来判断,“几”=(抽奖人数/奖品数)*N。这是一种最简单抽奖算法,适合抽奖人数众多,而且互相无联系的情况。如今大为流行的微博转发得奖就常常使用这种算法,即根据转发次数来决定奖品归属,透明而且具有激励性。 当然这个“几”也不单只次数,还可能是时间,逢某个时间点就可以抽中,不过这种方案可能产生无人中奖和很多人中奖的情况,时间点的安排很关键!这个时间点一旦公布出去,那就是秒杀,霍霍。。 逢“几”中奖有很多弊端,但是非常简单,很容易实现,被很多抽奖活动所采用,有些会公布抽奖规则,激励抽奖,有些则不会公布,其实后台运行的可能也是这个算法,简单高效又不失公平。在信息不透明的情况下,鬼知道你是第几个抽奖的,哈哈。。 二、概率抽奖 所谓概率抽奖是最容易想到的抽奖算法了,这个概率可以是一成不变的,也可以是一直在变化调整的,最难的是采用多大的概率,何种情况下采用何种概率。这个也没有什么通用的方案,不同的应用场景,所用的概率算法不同。下面介绍一种算法,根据奖品的过期日期来计算它当前时间的中奖率,当时间逐渐接近奖品过期时间时,中奖概率会逐渐发生变化,如果设为1表示线性衰减,2为平方衰减,以此类推。 importjava.util.Date; importjava.util.Random; publicclass LotteryTool { private double factor; private double probability; private Random rand; private LotteryTool(double probability, long expireTime, int reduce){ this.factor = (double) System.currentTimeMillis() / expireTime; this.probability = probability * Math.pow(factor, reduce); … Continue reading

LRU
wiloon, 1/8/2015 5:00 | Tag:

http://baike.baidu.com/view/70151.htm LRU是Least Recently Used 近期最少使用算法。 内存管理的一种页面置换算法,对于在内存中但又不用的数据块(内存块)叫做LRU,Oracle会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。 什么是LRU算法? LRU是Least Recently Used的缩写,即最少使用页面置换算法,是为虚拟页式存储管理服务的。 关于操作系统的内存管理,如何节省利用容量不大的内存为最多的进程提供资源,一直是研究的重要方向。而内存的虚拟存储管理,是现在最通用,最成功的方式—— 在内存有限的情况下,扩展一部分外存作为虚拟内存,真正的内存只存储当前运行时所用得到信息。这无疑极大地扩充了内存的功能,极大地提高了计算机的并发度。虚拟页式存储管理,则是将进程所需空间划分为多个页面,内存中只存放当前所需页面,其余页面放入外存的管理方式。 然而,有利就有弊,虚拟页式存储管理减少了进程所需的内存空间,却也带来了运行时间变长这一缺点:进程运行过程中,不可避免地要把在外存中存放的一些信息和内存中已有的进行交换,由于外存的低速,这一步骤所花费的时间不可忽略。因而,采取尽量好的算法以减少读取外存的次数,也是相当有意义的事情。

辽ICP备14012896