快速排序里的学问:信息熵

从信息熵角度去理解问题
服务器君一共花费了220.880 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

信息是个很抽象的概念。人们常常说信息很多,或者信息较少,但却很难说清楚信息到底有多少。比如一本五十万字的中文书到底有多少信息量。直到1948年,香农提出了“信息熵”的概念,才解决了对信息的量化度量问题。

一条信息的信息量大小和它的不确定性有直接的关系。比如说,我们要搞清楚一件非常非常不确定的事,或是我们一无所知的事情,就需要了解大量的信息。相反,如果我们对某件事已经有了较多的了解,我们不需要太多的信息就能把它搞清楚。所以,从这个角度,我们可以认为,信息量的度量就等于不确定性的多少。

香农指出的信息熵的计算公式如下(本文的对数一律以2为准):

H(x) = -∑p(xi)log(p(xi)) (i=1,2,..n)    (其中p(x)是x事件出现的概率)单位为bit 

在数学之美里是用赛后怎么知道32个球队里谁是冠军来讲解了这个信息熵的概念。

当概率相等时,每次询问用折半查找的原理(如“冠军队伍在1-16吗?”)可以减少一半的队伍,这样就需要5次就能知道结果了。这里就是log32 = 5。

而使用信息熵计算信息量,的确也是5。但是为什么信息熵这个公式会代表信息量呢 

按我的理解,在等概率事件里,1/p(x) 代表那一次所有可能出现的量、在球队问题里,就是32种可能性。

而等概率事件里,因∑p(xi) = 1,所以信息熵可以看成:

信息熵H(x)= -∑p(xi)log(p(xi)) (i=1,2,..n) = -log(p(i)) = -(- log(1/p(x)))= log(1/p(x)) 

也就是说等概率事件里的信息量可以看成:

H(x)= log(所有可能性) 

为了加深对信息量的定义的理解,再回到上述32个球队的问题,我们已经知道他的信息量是5Bit。

问过一次之后,我们可以知道冠军在哪16个队伍中,也就是说我们获得了1bit的信息后不确定性减少,等于信息熵变成了log16 = 4bit =5bit -1bit 。

而最大熵模型呢?它的原理就是保留全部的不确定性,将风险降到最少。

最大熵原理指出,当我们需要对一个随机事件的概率分布进行预测时,我们的预测应当满足全部已知的条件,而对未知的情况不要做任何主观假设。(不做主观假设这点很重要。)在这种情况下,概率分布最均匀,预测的风险最小。因为这时概率分布的信息熵最大,所以人们称这种模型叫“最大熵模型”。

我们常说,“不要把所有的鸡蛋放在一个篮子里”,其实就是最大熵原理的一个朴素的说法,因为当我们遇到不确定性时,就要保留各种可能性。 

也就是说发现不确定信息的时候,不要对不确定的产物任何主观假设使他们的概率分布均匀,则能获得最客观的结果。而这时风险会最小,我们就可以用这个结果来进行最客观的决策。数学上来说就是最优下界。

这种策略的本质可以概括成“让未知世界无机可乘”。它是没有“弱点的”,答案的任何一个分支都是等概率的。反之,一旦某个分支蕴含的可能性更多,当情况落到那个分支上的时候你就郁闷了。二分搜索为什么好,就是因为它每次都将可能性排除一半并且无论如何都能排除一半(它是最糟情况下表现最好的)。

我再用算法的时间复杂度说明一下最大熵原理吧,用几个主流的算法对n个数据进行排序时间复杂度基本上都是从O(nlogn)到O(n2)。而一般情况下为什么O(nlogn)最优呢(透露下,快速排序的平均时间复杂度就是O(nlogn)),因为n个数据的先后顺序是随机的,我们可以看做不确定性相等,则可以用最大熵原理获得最优(最稳定)结果。则信息熵则为:

H(x)= log(所有可能性)= log(n!) 而n->00 则log(n!) 近似于lognn= nlogn

假设我们每次能获得1bit数据,就至少需要获得(nlogn)bit数据才能取消信息的不确定性,也就是要比较nlogn次。但因为各种排序算法策略不同,我们不可能每次都能获得1bit数据,所以按照信息熵的定义这是理论上最优的结果。而最佳的排序算法就是要每次获得1bit数据,越接近于1则越有效。 

虽然快排和堆排序两个是都是时间复杂度O(nlogn)的算法,但是快速排序一般都会比堆排序快,就是因为堆排序每次获取的平均信息量比快排来的低。 

而上面,我们根本没提到具体算法,就算到了最优的时间复杂度。在实际生活中很多时候我们虽然不会想到具体的策略,但我们至少可以知道极限在哪里,可以知道还有没有提高余地。任何排序和猜数字的算法可以理解为通过获得信息量去消减原来的熵。

延伸阅读

此文章所在专题列表如下:

  1. 快速排序里的学问:从猜数字开始
  2. 快速排序里的学问:再看看称球问题
  3. 快速排序里的学问:信息熵
  4. 快速排序里的学问:快速排序的过程
  5. 快速排序里的学问:霍尔与快速排序
  6. 快速排序里的学问:霍尔快排的实现
  7. 快速排序里的学问:枢纽元选择与算法效率
  8. 快速排序里的学问:随机化快排

本文地址:http://www.nowamagic.net/librarys/veda/detail/2389,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2389

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

现代魔法研究协会欢迎你

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《程序员修炼之道:从小工到专家》 亨特(Andrew Hunt) (作者), 托马斯(David Thomas) (作者), 马维达 (译者)

《程序员修炼之道:从小工到专家》内容简介:《程序员修炼之道》由一系列独立的部分组成,涵盖的主题从个人责任、职业发展,知道用于使代码保持灵活、并且易于改编和复用的各种架构技术,利用许多富有娱乐性的奇闻轶事、有思想性的例子及有趣的类比,全面阐释了软件开发的许多不同方面的最佳实践和重大陷阱。无论你是初学者,是有经验的程序员,还是软件项目经理,《程序员修炼之道:从小工到专家》都适合你阅读。

更多计算机宝库...