Theory Of Computation

计算理论（暂时没时间继续维护）

1. 再开个讨论, 时间复杂度的表示 你觉得是否正确

   相信每个计算机同学都有接触过时间复杂度的概念 O(n) 大O符号表示法, 是计算理论中 计算复杂性理论 的衡量工具.

   有关它的计算有两个特性, 我想具体讨论下:

   1. 忽视常数项, 常数项视为 O(1)

   2. 忽视底次幂, 由最高次幂定

   这真的合理吗?

   我的质疑点有二:

   1. N 没有量化, 常数项没有量化, 为什么 哈希表的存取为 O(1), 这就是限制了常数项的缪论.

   2. 理论没有与工程联系起来, 计算机的各种cache,并行,传输开销等, 是理论不涉及的, 它真的实用吗?

   所以说 我在想 时间复杂度 可能只是一种很理论层面上的衡量复杂度的工具.

   我之所以说这么多, 就是我上学的时候 为它花了时间, 现在想想可笑.

   还有一点也随便发泄出来吧, 就是软件工程课程.

   一群不知道哪来的人造出来的概念, 或者根据已有的概念包装下, 竟然成了国内计算机大学的必修课.

   我从来没有从国内教育中获益过.

   到此为止了, 不说这点了.

   因为我眼界有限 并且 接触到的教育资源有限, 我吐槽的教育 只代表我经历过的.

   让我想起了之前看 软件随想录中的一句话:

   不论从什么角度看，这两种文化的差别大致上就是阳春白雪与下里巴 人之间的差别。 事实上，它很精确地反映在全国各个计算机系的课程设置 上。 在常春藤联盟 的院校中，只教授 UNIX 、函数式编程、状态机理论。 当你顺着排名的顺序往下看到那些越来越少人问津的学校，你就会看到 Java 语言开始在课程中出现了。 你再往下看，大概就会看到有一些课程起了这样的名字 ： Microsoft Visual Studio 2005的101 课程，3个学分。 等到你看到2年制学院的部分，会发现有些课程的名字，同 “21天 SQLServer书课程”差不多，简直如同周末有线电视中的广告 一样。 想找好工作吗？现在正是你最好的时机开始学习（另一个声音出来说 ） Java Enterprise Beans !

2. 分享篇文章:

   计算的极限（一）：所有机器的机器，与无法计算的问题 https://fwjmath.wordpress.com/2012/11/21/the-limit-of-computation-1/

   文章涉及了 计算理论 中的一些概念, 有关可计算性理论可以讨论下.

3. 计算理论与计算模型 - 晓强DL的文章 - 知乎 https://zhuanlan.zhihu.com/p/158121402