隨筆檔案

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

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

我是覺得最高效的算法應該是恰恰能解決現有問題的算法，不生成多余的冗余信息
生成任何信息都是需要代價的
信息論。。。
算法的高效不高效，一是時間二是空間
上面那個問題，既然不需要計數
只需要給每個元素一個位，節省空間
位圖
海量數據的時候
如果 幾十億個 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
反正總結起來是兩點吧，一是充分挖掘已有的信息，二是盡可能不要產生冗余信息。這樣設計的算法，既可以利用以存在的信息，也不會產生多余的信息，效率自然會高。