:: 和同学聊了起来
=======================
信息论的角度去讨论算法
一个算法的高效不高效
看它产生的信息量有多大
如果有冗余的信息量,效率就有提高的空间
举个例子
你统计一个集合中重复出现的元素
那么久没有必要对元素计数
直观的方法是对元素计数
然后检测
但是这个计数是冗余的
只需要找到重复的,不需要知道具体出现的次数
针对这个问题
我是觉得最高效的算法应该是恰恰能解决现有问题的算法,不生成多余的冗余信息
生成任何信息都是需要代价的
信息论。。。
算法的高效不高效,一是时间二是空间
上面那个问题,既然不需要计数
只需要给每个元素一个位,节省空间
位图
海量数据的时候
如果 几十亿个 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
反正总结起来是两点吧,一是充分挖掘已有的信息,二是尽可能不要产生冗余信息。这样设计的算法,既可以利用以存在的信息,也不会产生多余的信息,效率自然会高。
posted on 2011-07-11 23:18
unixfy 阅读(199)
评论(0) 编辑 收藏 引用