廣告

55 thoughts on “

  1. rio 說道:

    XD 看見如此粉紅的改版心跳漏了一拍,在留言看見改版原因了,祝大大安好~

  2. 判斷邊界條件,開頭多一行if、少一行if──其實不是很重要的事情。兩者時間大概只相差0.00001秒吧。應當需要加if時,就加if吧。

    第一個超連結,使用遞推法,長度翻倍,比較直覺,不過需要O(n)記憶體。我網頁裡面的兩個方法都不需要額外記憶體。

    第二個超連結,我看不太懂。你可以解釋一下嗎?

  3. obelisk 說道:

    http://www.csie.ntnu.edu.tw/~u91029/Permutation.html#1
    生成 Gray Code 的第一個程式碼

    前面可以加上下面這幾行來加入 0
    cout << 0;
    if (N == 0)
    return;

    最後一位和最後第二位是一樣的
    可以加一個 if 判斷式來決定是否輸出最後一位

    假如用 list 來存入所有生成的 Gray Code, 可以不用 if
    只需要在離開 for 迴圈後, pop 最後一位

  4. 類似的情況還有:判斷無向圖是否只有偶環(即二分圖)是P,同樣情況換成奇環則是NP。我不清楚是什麼原因造成了差別。

  5. Yu-Han 說道:

    這題讓我想到中央資工 95 年的考題:給定一無向圖,判斷有沒有 4-cycle。這似乎用 BFS 就可以在 O(n^2) 時間和 O(n) 空間做出來?

    不過有趣的地方是,給定任何偶數 k ,判斷有沒有 k-cycle 都可以在 O(n^2) 時間內完成,但是找 triangle 目前卻沒有 O(n^2) 的方法。
    https://mathoverflow.net/a/16464

  6. 這個方法乍看不太實用,不是很想仔細看懂。reduction似乎很粗暴:每次BFS結束之後,把可能是奇環的cross edges,加入到新圖G’裡面,直接改成了三角形。

  7. 看了連結後,要做兩件事:

    1. 找最小環O(n n)。優先遭遇的環,可能是偶環或奇環。如果運氣不好優先遇見奇環且最小環是偶環,導致答案+1。
    2. 判斷圖上是否有三角形,藉由矩陣相乘。

    不過我看不出來2.如何解決「答案可能+1」。因為三角形代表最小偶環與最小奇環形成連體嬰?

  8. Yu-Han 說道:

    Shortest cycle 的長度叫做 girth 。如果知道 girth 是偶數,那麼找出來只需要花 O(n^2),從每個點出發作 BFS,一旦找到 cycle 必定就是包含該點的最小 cycle ,就換另一個點當起點作 BFS 。所以每個點的 BFS 頂多只花 O(n) 的時間。如果 girth 是奇數,這方法不一定會找到 girth ,有可能會找到 girth + 1(想像一個圖只有一個 3-cycle 和 4-cycle ,而且這兩個 cycle 只共用一條邊,BFS 可能會在 3-cycle 前找到 4-cycle )。如果像版主的方法,每個頂點都做完整的 BFS ,那麼就可以保證找到 girth ,只是時間就變成 O(n(n+m))。

    要如何快速找到奇數的 girth 可以參考下面的討論:
    https://cstheory.stackexchange.com/questions/10983/optimal-algorithm-for-finding-the-girth-of-a-sparse-graph

  9. to EtaoinWu:
    搜索框的半透明效果,導致隱蔽吧。反正搜索框不是閱讀重點,隱蔽還是比較好。

    WordPress使用Unicode,頁面同時支援各國文字。另一方面,新的作業系統(操作系統)已經內建了各國文字的字型,例如win10,繁中有微軟正黑體,簡中有微軟雅黑體。因此,正常情況下,每個人都能看的到各國文字,包括我。

    to ryan_lee:
    我是覺得有女兒比較可能會做出這種風格的網站啦。女朋友喜歡這種風格的話,這女朋友應該很瞎吧。

    我沒有女朋友啦。眼睛有問題,沒工作,月領1500網友救濟金,光聽到都嚇跑了。今天才勸退一個好心阿姨,說是有個29歲女兒,學歷台大植病。光是學歷就比我好太多了哈哈。

    至於新網站的由來,是因為幾年前我看了幾個影片:

    看完後就一直很想試做看看。於是我先把網站主題改成粉紅色,試試水溫。馬上有讀者反映說他看了感覺心情激動,希望可以改回來。所以我就把這件事情擱置了。

    去年我的金主向我問起網站改版的事情,我就想起了這件事,並且說給他聽。他有點錯愕,不過也沒反對就是了。可是由於那時候我很忙、眼睛狀況也沒很好,所以又擱置了。

    最近整理流體力學有點卡關,剛好師大資工FTP爆了,所以就又想起這件事,一時興起花了幾天把它完成,一邊做一邊笑。說到粉紅色系,當然必須要有黃色星星,於是我也順便想好了網站主題曲,正在考慮要不要再弄個撥放器:

  10. ryan_lee 說道:

    版主你是有女朋友了?粉紅色的演算法筆記是怎樣啦…

  11. 唔。新页面的搜索框看起来很隐蔽呢。我觉得带个Background color会更好。
    (话说版主您能看简体吗?如果不行我可以OpenCC上转换一下

  12. 啊不好意思…我本地浏览器里html内容变了,css内容却没变…所以看到的是错误的渲染(然而没有截图)新html下用旧的css渲染效果就是错位的…

  13. 一個簡單的O(n(n+m))算法:

    1. 窮舉n種起點。
    2. 針對一種起點,窮舉經過起點的cycle。
    2-1. 建立bfs tree或dfs tree。
    2-2. 每一條cross edge恰好對應一個經過起點的cycle。
    2-3. 這玩意叫做fundamental cycle basis。

    由於重複列舉了同樣的cycle,複雜度應該可以更低。不過我想不出來、也懶得想。

    依照經驗,這個問題應該在1980年代就被徹底研究過了,老早有完美答案了。

    要找答案比較麻煩一點,我懶得找,就講兩個方法。一種方法是用谷歌搜尋「Unweighted Undirected Graph review paper」看看能不能找到學術論文、或是學校教授整理的筆記。
    https://www.google.com.tw/search?q=Unweighted+Undirected+Graph+review+paper

    另一種方法是去圖書館翻閱標題為handbook of xxx這類書籍。
    https://www.crcpress.com/p/book/9781584885955

  14. 版主您好,请问一下Shortest Cycle在无向无权图(Unweighted Undirected Graph)上有低于O(min(m^2,n^3))的算法吗

  15. 已經修正好了,謝謝!

    師大資工自從上次停電之後,FTP就無法正常登入。因此我沒有辦法馬上更新圖片。

  16. ryan_lee 說道:

    今天演算法筆記的網站進不了,請問是出了問題還是之後都不再開了?

  17. 可以呀。你要用哪國的語言都行,唯一的問題是我不見得看得懂。

    如果你想問我能閱讀簡體中文嗎?大致上讀得懂吧。

    如果是想問網站內容可以翻譯成簡體中文嗎?目前沒有翻譯成簡體中文的計劃。

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

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

    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/

  19. 兩個多項式相乘,普通的演算法是直式乘法,時間複雜度是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,我找到了原始論文瞄了幾眼,雖然沒讀懂,但是乍看之下跟多項式乘法沒有關係吧。

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

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

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

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

  21. 匿名 說道:

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

  22. 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 ?

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

  24. 匿名 說道:

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

Leave Message

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s