40 thoughts on “

  1. 組合計數問題,將之轉化成多項式乘法,是很常見的手法,離散數學教科書裡面通常會提到。

    我目前還沒有把這個手法整理到演算法筆記裡面(我目前在搞流體力學/微分幾何,如果李宏毅和吳尚鴻雙雙陣亡的話接下來也許會搞深度學習,之後才可能輪到數論,進度可能以季為單位哈哈)。如果你急著想學的話,這裡有份草稿,可以加減看一下:

    http://www.csie.ntnu.edu.tw/~u91029/Sequence2.html#2

    在章節末有個 X+Y Problem ,類似於這個手法。

    最後補充一下。前面的留言有人問了一個問題,我回覆了三個超連結,也都是同樣的手法。

    我想到一個問題,如果給定一個數列,求所有從中選出k個數的方案中,每個方案中數的乘機的和,有什麽比較優秀的算法嗎?

    我不知道,但是谷歌知道。
    https://cstheory.stackexchange.com/questions/24933/
    https://math.stackexchange.com/questions/786183/
    https://stackoverflow.com/questions/23537120/

  2. 兩個多項式相乘,普通的演算法是直式乘法,時間複雜度是O(n n),n是項次。

    另外還有一個快速的演算法,時間複雜度是 O(n log n)。過程是:多項式的係數,看成是數列,數列長度至少取到剛好是2的次方,而且足以涵蓋多項式相乘結果。兩個數列分別實施快速傅立葉轉換fft,然後兩個數列實施點對點乘法,然後實施快速逆向傅立葉轉換ifft,就完成了多項式乘法。

    回到正題。你連結中的演算法,過程是:把一個幣值變成一個多項式(兩項),再把所有多項式相乘起來(最多c+1項,c是幣值總和),就能從係數判斷正確答案。

    總共要乘 n-1 次,所以時間複雜度應該是 O(n c log c) 喔!而且這跟 dynamic programming 完全沒有關係,而且用 binary tree 的方式相乘也不會比較快。

    至於 probabilistic convolution tree,我找到了原始論文瞄了幾眼,雖然沒讀懂,但是乍看之下跟多項式乘法沒有關係吧。

  3. 因為註解寫錯了。應該是這樣才對:

    因數成雙成對(平方根跟自己一對)。檢查了小於等於sqrt(n)的因數,就不必檢查大於sqrt(n)的因數。

    因數一定可以遞迴分解成質因數,甚至自身就是質因數。檢查小於等於sqrt(n)的質因數,效果等同於檢查小於等於sqrt(n)的因數。

    質因數是質數的一部分。上述內容可以進一步改成檢查小於等於sqrt(n)的質數,一定可以涵蓋到小於等於sqrt(n)的所有質因數。

  4. 匿名 說道:

    我想到一個問題,如果給定一個數列,求所有從中選出k個數的方案中,每個方案中數的乘機的和,有什麽比較優秀的算法嗎?

  5. obelisk 說道:

    http://www.csie.ntnu.edu.tw/~u91029/Sequence2.html
    多項式循環乘法 = 數列循環摺積
    c₁ = a₂b₁ + a₀b₁ + a₁b₁ 是否為 a2b2 + a0b1 + a1b0 ?
    c₂ = a₀b₀ + a₁b₀ + a₂b₀ 是否為 a0b2 + a1b1 + a2b0 ?

    Convolution 的快速演算法
    Polynomial Multiplication 的快速演算法
    “長度補到2的次方" 的 a4 是否為 0 ?

  6. 網站內容比較新,可以直接看網站。
    如果你是要問記憶法單字有沒有拼錯,我應該是沒有拼錯。

  7. 匿名 說道:

    版主您好,看您的書獲益良多,誠心感謝。想請問記憶法(Memoz

  8. 這問題有點大,我分兩段講,這篇講Dijkstra演算法。

    Dijkstra的原始論文:只有大略做法,沒有實作細節,也就沒有明確的時間複雜度。

    O(V^2)版本:Aho, Ullman, Hopcroft的演算法著作,自行弄出了一個演算法,巧妙使用表格,時間複雜度是O(V^2),並且把它叫做Dijkstra演算法(多半是想紀念先人,科學領域常有這種事)。然後,眾所皆知的CLRS抄了這本書。因此,眾所皆知的Dijkstra演算法是O(V^2)版本。

    O(ElogE) = O(ElogV)版本:使用了binary heap。我不知道這是誰發明的。

    O(E + VlogV)版本:使用了Fibonacci heap。發明人是Fredman , Tarjan,叫做Fredman -Tarjan演算法。注意到此演算法的原理跟上面那個完全不同。

    順帶一提Fibonacci heap的發明人也是Fredman 。Fibonacci heap是一個病態的算法(請參考前一篇),沒有任何實用價值。因為CLRS介紹了它,所以就走紅了。也因此至今仍有不明就裡的老師用Fibonacci heap來荼毒學生。

    priority queue是泛稱,是指可以自動自發排序的queue,它可以是binary search tree、binary heap、binomial heap、Fibonacci heap。heap也是泛稱,是指可以隨時得到極值的資料結構,尤其是長得像樹的。priority queue和heap概念很像,儘管有點不一樣,但是我們並不會分得那麼清楚──這種事情不太重要。

  9. 這問題有點大,我分兩段講,這篇講複雜度。

    單論Dijkstra演算法,這是確定性演算法,不是隨機化演算法,時間複雜度上限和下限都是一樣的,都是O(V^2)。這沒有什麼好討論的。

    討論「所有可能的」單源最短路徑演算法,這就不簡單了。一個trivial、沒有討論價值的下限是Ω(V+E)──因為每個點每條邊至少都得讀一次呀。那麼有略大於Ω(V+E)、更逼真、更準確一點的下限嗎?沒有!地球人至今仍然不知道更好的下限。

    (順帶一提,課本上介紹這個概念,通常是以矩陣乘法為例,而不是以最短路徑問題為例。)

    因為搞不定下限,只好搞上限。很多人拼命發明新的演算法,嘗試降低上限。然而演算法往往過於繁雜,無法投入實用,已經發展到了病態的地步。演算法的頂尖會議經常出現這種病態算法。比方說,今年的SODA某篇論文就給了集合分割問題一個精彩的新上限:

    正常人看了都會崩潰。

  10. 另外補充一下。

    即便int改成char,CPU每次還是讀32位元,計算時間不會下降。

    但是int array改成char array,CPU每次得以載入更多變數,cache miss會減少,計算時間會明顯下降。

    填表格時是循序讀取陣列,cache miss理論上會減少為1/4。回溯時不是循序讀取,cache miss理論上會減少但不會到1/4。

  11. 修正好了,謝謝!

    for迴圈索引值打錯了。為了增加可讀性,一維固定用i,二維用j。

    prev原先是虛擬碼,現在改成程式碼了。變數型態正常下是用int。省空間是用char。更省空間是併入array,以位元運算添加於array最高位元,int array改成unsigned int array。更更省空間是用Hirschberg’s Algorithm,array和prev從二維降一維,不需要走旁門左道。為了保持可讀性,我還是用int。

  12. 系統自動分類成垃圾留言了。我手動還原了。

    你說的對。其實我不知道怎麼做。當時我看到Unit Capacity Network,我沒細想就把它們湊一起了。現在已經刪去了。真是抱歉。

  13. 不知道剛才發出來了沒有…自己沒看到就重新發一遍吧(如果看到了就無視這一條好了)
    Capacity Scaling Algorithm 中,每次增加的容量的確是 Unit Capacity Network,但是本來的容量仍然在,乘以二之後加上增加的容量,得到的新圖不一定是 Unit Capacity Network ,那麼如何使用 Unit Capacity Network 的算法進行優化呢?

  14. 請問下Flow中的Capacity Scaling Algorithm里的衍生閲讀中說到,“增加的容量是Unit Capacity Network”,但是原圖中的容量要乘以二再加上“增加的容量”,最後得到的圖並不是Unit Capacity NetWork?那如何處理呢?

  15. 不是遺失,是還沒畫。拖了好幾年了。

    拖稿原因很多。我列出其中幾個:一、我想製做立體圖片,能用滑鼠旋轉觀看,但是目前尚無合適的JavaScript套件。即便要自己動手做,我的程式功力還沒厲害到可以輕輕鬆鬆完成這件事,一想到就覺得麻煩,也就遲遲沒有動手做。二、三維凸包概念簡單不難學習,計算幾何書籍已經做了詳細介紹。我沒有什麼能補充的,也就不急著完成。三、三維凸包用途極少,無論是工程上還是理論上。國內外學校課程幾乎不談三維凸包算法,因此我也沒必要積極推廣。製作三維凸包圖片,性價比偏低,不如先搞其他主題。

  16. 匿名 說道:

    您好,3D Convex Hull那邊有些圖片遺失了,希望能夠修正,謝謝!

  17. 你的網頁裡面有一句話是:「時間複雜度來說的話,用當時論文提出的實作方式,修改邊權的部分為O(|E|)。」所以我才會想說你可能有讀過原始論文。

    正是因為很多paper引用,但是卻找不到原始版本,所以我才形容為都市傳奇。

    1965年朱劉宣稱完成論文,投稿國內期刊《中國科學》。《中國科學》的官方網站沒有提供1965年的論文,無論是中文版還是英文版。我在網路上也搜尋不到,可能沒有電子檔、只有紙本吧。
    https://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E7%A7%91%E5%AD%A6_(%E6%9C%9F%E5%88%8A)

    1967年美國數學年鑑記錄了論文名稱的英文翻譯。不過我不清楚這是1967年出版的,或者是之後出版、之後收錄的。
    https://books.google.com.tw/books?id=6Zw8AAAAMAAJ&q=On+the+Shortest+Arborescence+of+a+Directed+Graph

    根據下面網頁的說法,朱劉投稿後,中國隨即對外失聯。直至1974年英國數學家才發現朱劉算法(是哪位?),看的是英文版(在哪裡?)。
    http://www.qzu5.com/zhuyongjin.htm
    http://www.qzu5.com/lz.htm

    1977年Tarjan的finding optimum branchings,這是我看過最早的引用,翻譯名稱跟年鑑一致。
    https://cw.fel.cvut.cz/wiki/_media/courses/a4m33pal/cviceni/tarjan-finding-optimum-branchings.pdf

    在看到原文之前,我還是傾向認為這是都市傳奇。這就好比課本寫著國父革命11次建立中華民國,但是事實卻是俄國買通孫文建立叛軍、日俄夾攻推翻中華民國。

Leave Message

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s