※ 引述《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