隨筆檔案

：： 和同學(xué)聊了起來
=======================
信息論的角度去討論算法
一個算法的高效不高效
看它產(chǎn)生的信息量有多大
如果有冗余的信息量，效率就有提高的空間

舉個例子
你統(tǒng)計一個集合中重復(fù)出現(xiàn)的元素
那么久沒有必要對元素計數(shù)
直觀的方法是對元素計數(shù)
然后檢測
但是這個計數(shù)是冗余的
只需要找到重復(fù)的，不需要知道具體出現(xiàn)的次數(shù)
針對這個問題

我是覺得最高效的算法應(yīng)該是恰恰能解決現(xiàn)有問題的算法，不生成多余的冗余信息
生成任何信息都是需要代價的
信息論。。。
算法的高效不高效，一是時間二是空間
上面那個問題，既然不需要計數(shù)
只需要給每個元素一個位，節(jié)省空間
位圖
海量數(shù)據(jù)的時候
如果 幾十億個 int 數(shù)
看里面是否存在重復(fù)的
重復(fù)出現(xiàn)的時候，檢測到對應(yīng)為為 1 ，說明之前存在了
所以就是重復(fù)出現(xiàn)的數(shù)
遍歷這個集合
可以將結(jié)果存起來
我的意思是，這個問題就是找到重復(fù)出現(xiàn)的，沒有必要對每個數(shù)計數(shù)
這樣，就可以節(jié)省空間

還有時間的
還有就是充分挖掘問題中的信息
充分利用問題中的信息，提高獲取的信息量，充分利用了隱藏的信息量就會涉及出高效的算法
基于比較的算法，不會是 O(N) 的，最優(yōu)就是 O(NlogN)。
基數(shù)排序、桶排序，這樣的就是有限制性的算法，這個限制就是元素有個范圍，限制是給了隱含的信息，利用這個可以就有了 O(N) 的排序
盡可能從問題中挖掘潛在的信息，獲得的信息越多越有利于解決問題，也就越有可能獲得高效的解法。

控制論、系統(tǒng)論、信息論
信息論是香農(nóng)創(chuàng)建的，也屬于數(shù)學(xué)，算法就是解決問題的，解決問題的就是想得到結(jié)果，結(jié)果就是一種信息，算法的設(shè)計可以用信息論的角度解釋
反正總結(jié)起來是兩點吧，一是充分挖掘已有的信息，二是盡可能不要產(chǎn)生冗余信息。這樣設(shè)計的算法，既可以利用以存在的信息，也不會產(chǎn)生多余的信息，效率自然會高。

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

FOO 21:57:39
信息論的角度去討論算法
FOO 21:57:57
一個算法的高效不高效
FOO 21:58:09
看它產(chǎn)生的信息量有多大
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
我還是碼農(nóng)級別的
FOO 22:01:23
呃
FOO 22:01:27
舉個例子
FOO 22:01:57
你統(tǒng)計一個集合中重復(fù)出現(xiàn)的元素
FOO 22:02:10
那么久沒有必要對元素計數(shù)
FOO 22:02:16
直觀的方法是對元素計數(shù)
FOO 22:02:27
然后檢測
FOO 22:02:38
但是這個計數(shù)是冗余的
FOO 22:02:51
只需要找到重復(fù)的，不需要知道具體出現(xiàn)的次數(shù)
FOO 22:02:55
針對這個問題
BAR 22:03:28
額
BAR 22:04:14
你繼續(xù)
BAR 22:04:11
 
FOO 22:04:24
我是覺得最高效的算法應(yīng)該是恰恰能解決現(xiàn)有問題的算法，不生成多余的冗余信息
FOO 22:04:33
生成任何信息都是需要代價的
FOO 22:04:36
信息論。。。
BAR 22:04:41
你先說上面那個問題
FOO 22:06:05
算法的高效不搞笑，一是時間二是空間
FOO 22:06:14
上面那個問題，既然不需要計數(shù)
BAR 22:06:20
上面那個問題什么方法好？
FOO 22:06:29
只需要給每個元素一個位，節(jié)省空間
FOO 22:06:43
位圖吧
FOO 22:06:44
呵呵
BAR 22:06:50
那你怎么做
FOO 22:06:51
海量數(shù)據(jù)的時候
FOO 22:07:00
如果 幾十億個 int 數(shù)
BAR 22:07:08
把位置1
BAR 22:07:14
第二次出現(xiàn)呢
FOO 22:07:15
看里面是否存在重復(fù)的
BAR 22:07:20
也就是重復(fù)的時候出現(xiàn)呢
BAR 22:07:00
一個元素出現(xiàn)了一次
FOO 22:07:53
重復(fù)出現(xiàn)的時候，檢測到對應(yīng)為為 1 ，說明之前存在了
BAR 22:08:00
是撒
FOO 22:08:03
所以就是重復(fù)出現(xiàn)的數(shù)
BAR 22:08:05
你只找一個么
FOO 22:08:11
所有
BAR 22:08:17
還是說你有另一個輸出結(jié)果的地方
FOO 22:08:22
遍歷這個集合
FOO 22:08:36
可以將結(jié)果存起來
BAR 22:08:41
就是出現(xiàn)重復(fù)的時候把這個重復(fù)的放到另外一個地方或者輸出
FOO 22:09:07
恩
BAR 22:09:22
恩，我先洗澡去了
FOO 22:09:31
我的意思是，這個問題就是找到重復(fù)出現(xiàn)的，沒有必要對每個數(shù)計數(shù)
FOO 22:09:36
這樣，就可以節(jié)省空間
FOO 22:09:51
還是時間的
FOO 22:14:58
還有就是充分挖掘問題中的信息
FOO 22:15:38
充分利用問題中的信息，提高獲取的信息量，充分利用了隱藏的信息量就會涉及出高效的算法
FOO 22:16:11
基于比較的算法，不會是 O(N) 的，最優(yōu)就是 O(NlogN)。
FOO 22:17:09
基數(shù)排序、桶排序，這樣的就是有限制性的算法，這個限制就是元素有個范圍，限制是給了隱含的信息，利用這個可以就有了 O(N) 的排序
FOO 22:17:37
盡可能從問題中挖掘潛在的信息，獲得的信息越多越有利于解決問題，也就越有可能獲得高效的解法。

FOO 22:18:04
呵呵
FOO 22:18:23
控制論、系統(tǒng)論、信息論
FOO 22:19:47
信息論是香農(nóng)創(chuàng)建的，也屬于數(shù)學(xué)，算法就是解決問題的，解決問題的就是想得到結(jié)果，結(jié)果就是一種信息，算法的設(shè)計可以用信息論的角度解釋，呃。。
FOO 22:21:24
反正總結(jié)起來是兩點吧，一是充分挖掘已有的信息，二是盡可能不要產(chǎn)生冗余信息。這樣設(shè)計的算法，既可以利用以存在的信息，也不會產(chǎn)生多余的信息，效率自然會高。