: 对喔，忘记讲 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