Re: [問題] 複雜度的問題
: : 演算法的複雜度有兩種，一種是計算所需時間，一種是程式碼長度。
一般來說，程式碼長度對於複雜度並無影響，
而通常我們比較計較的是程式的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
討論串 (同標題文章)
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
