Re: [問題] 複雜度的問題
: 對喔，忘記講 space complexity... 不過這可以合併起來稱為
: computational complexity (計算複雜度)
: algorithmic comlexity (演算複雜度) 是真的少見，但確實是
: 重要的複雜度議題，或者可以說，這才是對演算法的複雜度的
: 研究。
: 這部分最有名的就數 computable number (可數數) 問題了，
: 例如以下的可數數:
: 0.12345678910111213141516...
: 這叫 Champernowne's Constant (以 10 為底，記為 C10).
: 它是無理數卻是可數數，只需要一個廻圈就能完成。
: 另外像是數列問題，如以下的著名智力測驗問題：
: 1
: 11
: 21
: 1211
: 111221
: 312211
: 13112221
: ....
: 這個數列用程式很容易做，卻不能用單一多項式函數完成。
: 通常這算是數學領域，電腦科學比較少談，大部分都是指用 Turing
: Machine 計算和輸出時，需要多少步驟才能完成。
抱歉，實在不太清楚你想表達的是什麼，
而且，algorithmic complexity這個名稱好像也不多見，
還是你是想說Kolmogorov complexity?
綜觀下來，不知道你想說明的是什麼呢?
: 另外有不同領域但其實差不多的 program analysis 和 logical depth.
: 其中 program analysis 就真的是研究最短的程式碼長度了。由於它
: 比較不會陷入函數分析或 Turing Machine 中，看起來比較像電腦科學
: 領域的東西。
請問你文中的"program analysis"跟"函數分析"是一樣的東西嗎?
又，如果是一樣的，有這名詞的定義嗎?
我想，可能需要更精確的了解名詞後再討論。
: 至於 logical depth 好像是硬體領域的東西，我不太了解，它主要是
: 用資訊理論來分析的，用在處理一個物理系統的複雜度，但也可以和
: 演算法對應。我是硬體白痴，如果說錯就請其他人補充。
亂入一下， XD
logical depth是不是在討論計算機組織的時候的data path的長度呀?
這我也完全不懂，哈哈
以上有錯請訂正。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.23.56
討論串 (同標題文章)
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
