随笔档案

：： 和同学聊了起来
=======================
信息论的角度去讨论算法
一个算法的高效不高效
看它产生的信息量有多大
如果有冗余的信息量，效率就有提高的空间

举个例子
你统计一个集合中重复出现的元素
那么久没有必要对元素计数
直观的方法是对元素计数
然后检测
但是这个计数是冗余的
只需要找到重复的，不需要知道具体出现的次数
针对这个问题

我是觉得最高效的算法应该是恰恰能解决现有问题的算法，不生成多余的冗余信息
生成任何信息都是需要代价的
信息论。。。
算法的高效不高效，一是时间二是空间
上面那个问题，既然不需要计数
只需要给每个元素一个位，节省空间
位图
海量数据的时候
如果 几十亿个 int 数
看里面是否存在重复的
重复出现的时候，检测到对应为为 1 ，说明之前存在了
所以就是重复出现的数
遍历这个集合
可以将结果存起来
我的意思是，这个问题就是找到重复出现的，没有必要对每个数计数
这样，就可以节省空间

还有时间的
还有就是充分挖掘问题中的信息
充分利用问题中的信息，提高获取的信息量，充分利用了隐藏的信息量就会涉及出高效的算法
基于比较的算法，不会是 O(N) 的，最优就是 O(NlogN)。
基数排序、桶排序，这样的就是有限制性的算法，这个限制就是元素有个范围，限制是给了隐含的信息，利用这个可以就有了 O(N) 的排序
尽可能从问题中挖掘潜在的信息，获得的信息越多越有利于解决问题，也就越有可能获得高效的解法。

控制论、系统论、信息论
信息论是香农创建的，也属于数学，算法就是解决问题的，解决问题的就是想得到结果，结果就是一种信息，算法的设计可以用信息论的角度解释
反正总结起来是两点吧，一是充分挖掘已有的信息，二是尽可能不要产生冗余信息。这样设计的算法，既可以利用以存在的信息，也不会产生多余的信息，效率自然会高。

======================

FOO 21:57:39
信息论的角度去讨论算法
FOO 21:57:57
一个算法的高效不高效
FOO 21:58:09
看它产生的信息量有多大
FOO 21:58:36
如果有冗余的信息量，效率就有提高的空间
BAR 22:00:18
额
FOO 22:00:53
呵呵
FOO 22:01:05
后面的几句是我最近感受的
BAR 22:01:11
呵呵
BAR 22:01:14
我不懂
FOO 22:01:17
呃
BAR 22:01:20
我还是码农级别的
FOO 22:01:23
呃
FOO 22:01:27
举个例子
FOO 22:01:57
你统计一个集合中重复出现的元素
FOO 22:02:10
那么久没有必要对元素计数
FOO 22:02:16
直观的方法是对元素计数
FOO 22:02:27
然后检测
FOO 22:02:38
但是这个计数是冗余的
FOO 22:02:51
只需要找到重复的，不需要知道具体出现的次数
FOO 22:02:55
针对这个问题
BAR 22:03:28
额
BAR 22:04:14
你继续
BAR 22:04:11
 
FOO 22:04:24
我是觉得最高效的算法应该是恰恰能解决现有问题的算法，不生成多余的冗余信息
FOO 22:04:33
生成任何信息都是需要代价的
FOO 22:04:36
信息论。。。
BAR 22:04:41
你先说上面那个问题
FOO 22:06:05
算法的高效不搞笑，一是时间二是空间
FOO 22:06:14
上面那个问题，既然不需要计数
BAR 22:06:20
上面那个问题什么方法好？
FOO 22:06:29
只需要给每个元素一个位，节省空间
FOO 22:06:43
位图吧
FOO 22:06:44
呵呵
BAR 22:06:50
那你怎么做
FOO 22:06:51
海量数据的时候
FOO 22:07:00
如果 几十亿个 int 数
BAR 22:07:08
把位置1
BAR 22:07:14
第二次出现呢
FOO 22:07:15
看里面是否存在重复的
BAR 22:07:20
也就是重复的时候出现呢
BAR 22:07:00
一个元素出现了一次
FOO 22:07:53
重复出现的时候，检测到对应为为 1 ，说明之前存在了
BAR 22:08:00
是撒
FOO 22:08:03
所以就是重复出现的数
BAR 22:08:05
你只找一个么
FOO 22:08:11
所有
BAR 22:08:17
还是说你有另一个输出结果的地方
FOO 22:08:22
遍历这个集合
FOO 22:08:36
可以将结果存起来
BAR 22:08:41
就是出现重复的时候把这个重复的放到另外一个地方或者输出
FOO 22:09:07
恩
BAR 22:09:22
恩，我先洗澡去了
FOO 22:09:31
我的意思是，这个问题就是找到重复出现的，没有必要对每个数计数
FOO 22:09:36
这样，就可以节省空间
FOO 22:09:51
还是时间的
FOO 22:14:58
还有就是充分挖掘问题中的信息
FOO 22:15:38
充分利用问题中的信息，提高获取的信息量，充分利用了隐藏的信息量就会涉及出高效的算法
FOO 22:16:11
基于比较的算法，不会是 O(N) 的，最优就是 O(NlogN)。
FOO 22:17:09
基数排序、桶排序，这样的就是有限制性的算法，这个限制就是元素有个范围，限制是给了隐含的信息，利用这个可以就有了 O(N) 的排序
FOO 22:17:37
尽可能从问题中挖掘潜在的信息，获得的信息越多越有利于解决问题，也就越有可能获得高效的解法。

FOO 22:18:04
呵呵
FOO 22:18:23
控制论、系统论、信息论
FOO 22:19:47
信息论是香农创建的，也属于数学，算法就是解决问题的，解决问题的就是想得到结果，结果就是一种信息，算法的设计可以用信息论的角度解释，呃。。
FOO 22:21:24
反正总结起来是两点吧，一是充分挖掘已有的信息，二是尽可能不要产生冗余信息。这样设计的算法，既可以利用以存在的信息，也不会产生多余的信息，效率自然会高。