: : 演算法的複雜度有兩種，一種是計算所需時間，一種是程式碼長度。 一般來說，程式碼長度對於複雜度並無影響， 而通常我們比較計較的是程式的time complexity， 白話一點應可說成對於每個不同的input來說，對應的計算時間。 但是程式碼長度實在不是一個很好的評量複雜度的標準， 譬如說，寫了一萬行的某程式A，一萬行全部都是cout<<"aaa";， 跟寫了兩行的程式B，for (i=1;i<10002;i++) cout<<i;， 還有一個程式C，內容是while(1) cout<<"break down";， 這三個程式哪個複雜度較高，(誰執行完程式的時間較久?) 我知道這不是一個解釋複雜度的好例子， 但是我只是想藉此提出程式碼長度並非度量複雜度的好標準的看法。 有錯請不吝訂正。 : : 不過這兩種複雜度通常是相依的，很難完整拆開來討論。 : : 前者我們已經有了基本的認識，每個學生在唸演算法，都會學到 O(x) : : 表示法，更深入一點的會學到 NP-complete 問題。這裡應該有很多人 : : 都學得滿深入的，我就不多說了。 : : 後者比較困難，從 Alan Turing 提出可計算數字 (computable number) : : 以來，後續的發展至今，就我所知，還沒有一個完整的理論出來，因為 : : 我們真的很難確認，怎樣的程式碼才是最短程式碼。目前是有一些成果， : : 但還局限在很特定的問題上。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.109.23.56