Re: [問題] 複雜度的問題
※ 引述《bigmoun (123)》之銘言：
: ※ 引述《reader (讀者)》之銘言：
: : 演算法的複雜度有兩種，一種是計算所需時間，一種是程式碼長度。
: ?????
: 這是指程式執行期間所需的空間大小嗎？
: 一般探討的不是time complexity 和 space complexity?
: program length倒是還沒看過耶！
對喔，忘記講 space complexity... 不過這可以合併起來稱為
computational complexity (計算複雜度)
algorithmic comlexity (演算複雜度) 是真的少見，但確實是
重要的複雜度議題，或者可以說，這才是對演算法的複雜度的
研究。
這部分最有名的就數 computable number (可數數) 問題了，
例如以下的可數數:
0.12345678910111213141516...
這叫 Champernowne's Constant (以 10 為底，記為 C10).
它是無理數卻是可數數，只需要一個廻圈就能完成。
另外像是數列問題，如以下的著名智力測驗問題：
1
11
21
1211
111221
312211
13112221
....
這個數列用程式很容易做，卻不能用單一多項式函數完成。
通常這算是數學領域，電腦科學比較少談，大部分都是指用 Turing
Machine 計算和輸出時，需要多少步驟才能完成。
另外有不同領域但其實差不多的 program analysis 和 logical depth.
其中 program analysis 就真的是研究最短的程式碼長度了。由於它
比較不會陷入函數分析或 Turing Machine 中，看起來比較像電腦科學
領域的東西。
至於 logical depth 好像是硬體領域的東西，我不太了解，它主要是
用資訊理論來分析的，用在處理一個物理系統的複雜度，但也可以和
演算法對應。我是硬體白痴，如果說錯就請其他人補充。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.222.173.26
討論串 (同標題文章)
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
