世界上最複雜的程序演算法有哪些？是如何設計和用來做什麼的？

01-04

我猜你這裡的複雜不是計算複雜度, 而是讓人感覺非常複雜.

不存在最複雜的程序演算法... 因為總是可以將兩個演算法合併起來. 當然有時候合併兩個演算法並不是很有意義- -

我可以告訴你一個我所認為最複雜的發表成paper的演算法. Chazelle的linear time triangulation algorithm.

設計我不知道是怎麼作的.

但是用來做什麼... polygon triangulation. 不懂去查查.

Chazelle本人說這個演算法"elementary", 因為沒有用到cs裡面的很高級的演算法/數據結構.

但是這個paper的難度在於, 用到了很多非常高級的數學結論(比如拓撲...). 至今這個演算法都沒有被實現(能看懂這個paper的未必想實現這個演算法, 能實現這個演算法的未必讀得懂這個paper)

Paper在這裡

http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf

, 有興趣可以考慮閱讀. 我忘了哪個大學的一個門一學期的研究生課程, 就是為了讀懂這個paper.

當然這個可能未必是解決這個問題最簡單的方法, 這是至今我們知道的最簡單的演算法. 計算幾何領域一個非常大的open problem就是是否存在簡單的線性polygon triangulation演算法. (有意思的是, 沒有看到多少人去研究這個問題, 因為計算幾何裡面的一大批人是理論計算機學家, 不少是得知演算法的存在性就高興了...)

Edit:

我感覺給這種演算法似乎沒有什麼用, 因為連我都不能完全讀懂這個paper, 無法提供"如何設計"這樣的回答. 而且提問者的"程序演算法"至少被人寫成程序的演算法吧. 學術界存在很多無法被寫成程序的演算法. (或者說, 沒有人願意寫成程序的演算法)

我來增加一個答案. 想說的是Level Ancestor Problem. 這個問題做到了我先前說的"總是可以把兩個演算法合併起來".

給一個有n個節點的樹. 求用linear preprocess time + constant query time里找到LA(v,d)的演算法.

其中v是樹的一個節點. LA(v,d)就是樹的第d層的一個節點, 並且是v的ancestor.

在Bender和Farach-Colton之前, 存在這樣的演算法, 但是他們給了一個很"簡單"的演算法, 雖然還有比較"複雜". 這裡的"複雜"定義為需要用到幾個不同的技巧才能創建這個演算法.

可能這個並不是提問者想要知道的類型的"複雜"的演算法, 但是我感覺這個演算法裡面的一些思維用在了不少"複雜"的演算法的構造上.

paper地址

http://www.cs.sunysb.edu/~bender/pub/latin02-level.ps

演算法的設計:

1. Jump-pointer: 在作LA(v,d)的時候, 如果一層一層的往上搜索很慢. 有沒有可能直接跳呢? 比如我們知道LA(u,d) = LA(v,d),如果u是v的一個ancestor. 如果直接儲存了LA(u,d), 並且可以在log(n)的時間"跳"到u, 那麼只要log n的時間就能找到LA(v,d). 這個演算法要用 O(n log n)的preprocess time + O(log n)的time. 每一次跳的距離是上一次的1/2倍. [這個演算法很簡單的]

2. The Ladder Algorithm. 如果把整棵樹直接改為n個path. 知道知道v在哪一個path里. 找到LA(v,d)是O(1). (就是path裡面的第d個元素). 所以要做的就只是找v在哪一個path里. 但是儲存所有的path並不高明, 因為直接儲存所有的path可能要花掉O(n^2)的時間. 所以要找比較"長"的path...然後弄點短的分支... 叫這些path為ladder. 在一個ladder裡面爬是constant time的. 因為ladder儲存為一個array. 可以想想剛開始ladder都比較長. 離葉子越近ladder越短. paper中證明了可以創建這樣的ladder, 是的每一次爬的距離是上一次的2倍. O(n)的preprocess time + O(log n)的time [這個演算法有點複雜, 因為ladder的創作不是那麼的trivial]

3. 得到這兩個演算法之後, 就可以考慮合體了. 因為剛開始跳的會很快, 後來如果爬會非常快. 所以先跳再加上爬就能做到O(1)時間了.

演算法最後的形態:

4. 但是jump-pointer要O(n log n)的preprocess time, 所以這個方法不夠完美, 於是這paper開始考慮能否把這個稍微改進. 方法就是看到, 沒有必要給每一個節點都一個jump pointer, 而是讓某些節點走一點的距離, 找到一個足夠近的jump pointer的節點, 然後往上跳. 這paper有詳細的結果, 還算是有點複雜的. [現在第一個演算法也複雜了]

所以整個演算法=2個複雜的演算法和在一起.

演算法的用途:

這個演算法本身的目的就是它的用途. 如果需要更多"現實"一點的用途我還真想不到呢. 很多時候數據結構都是先創建出來解決點很抽象的問題, 後來才被發現真實的用處.

P.S. + 八卦

準確的說這個問題算是數據結構的問題. 但是Bender有句名言. "有人說, 演算法是液體化的數據結構, 我更願意說數據結構是晶體化的演算法." Bender由於非常喜歡"研究把學術界一些難得令人髮指的演算法能讓人可以寫出來的數據結構"什麼的, 所以自己開了一個資料庫公司...

http://www.tokutek.com/

「複雜」是很難定義的，隨便扯好了

問題難以抽象化，比如「生成高質量的像素畫」
問題依賴大量的領域特定知識，比如我寫過一個和晶體結構有關的演算法，不懂晶體學完全無法理解
演算法的執行過程里使用了特殊的、只有本演算法使用的數據結構

複雜網路裡面演算法動不動就是o(N^3)以上的。這樣的複雜度計算機科學一般是不算的。

因為人口基數大，十萬起，百萬千萬也無所謂。在C語言裡面就是建一個超過400W的int數組都是很麻煩的事情。

90年代初計算第九個費馬數是質數還是合數花了很多的精力,當時被認為是數學和計算機的進步。

f(9)=2^(2^9)+1.

計算一個數是質數還是合數是當今以及以後密碼學長期的課題和基石。衍生了無數的演算法，耗費無數數學家、物理學家、密碼學家和計算機學家的精力。

不算回答吧，不存在最複雜的演算法，只有依靠現有計算能力能實現的演算法和不能實現的演算法。不知道有人同意我的觀點嗎？

所謂演算法，個人認為在大多數情況下可以定義為一種策略，也就是說，當我們需要解決某個問題的時候總需要一個可以將其完美（盡量）解決的方案，或者是從一系列可行的方案中選擇一種最為高效所得結果最為合理的策略。

有很多問題是非具象的也就是需要我們自行將其轉換為數學模型以方便設計演算法，這種問題在日常生活中是很多的。例如，如何使用具有限制性（數量有限或者其他）的資源換取儘可能多的必需品，又或者在一張地圖中如何走最少的路到達某地點且沿路可以看到儘可能多的風景，又或者說是電梯停在某一層可以使得電梯中的所有人到達自己要去的樓層所需要走的路之和最少，包括上面有人說的美國反恐時探測潛在恐怖分子的case等等等等。

在善於演算法設計人的眼裡，大部分問題都可以抽象成數學模型使用演算法對其進行解決，但是不同的人針對某一個問題時很可能會設計出多種不同形態或者不同理念的演算法，當然其中也會有效率和結果準確度的高低之分。

個人的一些淺見了……

好像有視頻壓縮用的H.263演算法吧。