討論串(共11篇) - [問題] 複雜度的問題 - 看板CSSE

看板 [ CSSE ]

討論串[問題] 複雜度的問題

共 11 篇文章

排序：最舊先 | 最新先 | 留言數 | 推文總分

內容預覽：開啟 | 關閉 | 只限未讀

首頁

尾頁

Re: [問題] 複雜度的問題

推噓0(0推 )留言0則，0人參與作者jeunder (笨soga笨肥一家笨)時間20年前 (2005/01/26 11:49)資訊

內容預覽:

如果定義好所有可用的基礎運算. 那麼問題就來了.... 一個演算法要如何實作才能使運算步驟最為簡潔?. 又如何保證這一定是最簡潔的?. 是否有理論上的 lower bound? (就好比資訊理論中的 entropy). 我想這是板主想表達的吧?!. --. ※ 發信站: 批踢踢實業坊(ptt.cc)

Re: [問題] 複雜度的問題

推噓0(0推 )留言0則，0人參與作者klain (klain)時間20年前 (2005/01/26 12:05)資訊

內容預覽:

演算法的確是有lower bound，. (當然，並非每個演算法都已經有人證明出lower bound). 但是這個lower bound與程式的簡潔性並無相關吧。. 有錯請訂正。. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 140.109.23.56.

Re: [問題] 複雜度的問題

推噓0(0推 )留言0則，0人參與作者klain (klain)時間20年前 (2005/01/26 12:31)資訊

內容預覽:

抱歉，實在不太清楚你想表達的是什麼，. 而且，algorithmic complexity這個名稱好像也不多見，. 還是你是想說Kolmogorov complexity?. 綜觀下來，不知道你想說明的是什麼呢?. 請問你文中的"program analysis"跟"函數分析"是一樣的東西嗎?. 又

(還有16個字)

Re: [問題] 複雜度的問題

推噓0(0推 )留言0則，0人參與作者reader (讀者)時間20年前 (2005/01/26 12:46)資訊

內容預覽:

用 Turing machine 來計算的複雜度稱作 Turing machine complexity.. 另外還有 Bit Complexity 之類的。. Kolmogorov complexity 則算是 algorithmic complexity 當中最主要的. 一支吧，當然我並不熟悉。

(還有422個字)

#10

Re: [問題] 複雜度的問題

推噓2(2推 )留言2則，0人參與作者reader (讀者)時間20年前 (2005/01/26 13:38)資訊

內容預覽:

原來現在變成了 Algorithmic Information Theory 了，. http://en.wikipedia.org/wiki/Algorithmic_information_theory. 這樣定義就比較清楚了。. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From

首頁

尾頁