: : 演算法的复杂度有两种，一种是计算所需时间，一种是程式码长度。 一般来说，程式码长度对於复杂度并无影响， 而通常我们比较计较的是程式的time complexity， 白话一点应可说成对於每个不同的input来说，对应的计算时间。 但是程式码长度实在不是一个很好的评量复杂度的标准， 譬如说，写了一万行的某程式A，一万行全部都是cout<<"aaa";， 跟写了两行的程式B，for (i=1;i<10002;i++) cout<<i;， 还有一个程式C，内容是while(1) cout<<"break down";， 这三个程式哪个复杂度较高，(谁执行完程式的时间较久?) 我知道这不是一个解释复杂度的好例子， 但是我只是想藉此提出程式码长度并非度量复杂度的好标准的看法。 有错请不吝订正。 : : 不过这两种复杂度通常是相依的，很难完整拆开来讨论。 : : 前者我们已经有了基本的认识，每个学生在念演算法，都会学到 O(x) : : 表示法，更深入一点的会学到 NP-complete 问题。这里应该有很多人 : : 都学得满深入的，我就不多说了。 : : 後者比较困难，从 Alan Turing 提出可计算数字 (computable number) : : 以来，後续的发展至今，就我所知，还没有一个完整的理论出来，因为 : : 我们真的很难确认，怎样的程式码才是最短程式码。目前是有一些成果， : : 但还局限在很特定的问题上。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.109.23.56