计算的分析

计算就是写程序，也就是说，怎么用程序判断一个人程序写得好不好？递归了属于是。

芯片中的石英晶体通电后产生震荡，会产生频率稳定的脉冲信号，再转化成驱动芯片工作的时钟信号。每次脉冲，都让芯片的状态发生一次变化，最终存储器中的指令被一行行执行。指令被执行，就是数据被计算，这就是计算能量。~~数字逻辑避不开了，痛，太痛了 😭~~ 哦吼，这就是这门课叫作数字逻辑的原因了！

摩尔定律

~~当价格不变时，集成电路中可容纳的晶体管数目约每隔 18 ～ 24 个月就会增加一倍，性能也将提升一倍。~~ 当工资不变时，前端工程师要学习的内容每 18 个月就翻一倍，工作量也将提升一倍。

什么是可计算的，做饭是吗？我们现在知道计算可以用来导航、游戏...但是我们也知道，世界上还有大量不可被计算的问题。

可计算理论：哪些问题可以被计算，哪些不可以被计算。

阿兰·图灵发现如果一个问题是可计算的，那么它的解决方案就必须可以被具化成一条条的指令，也就是可以使用图灵机处理。因此，不能使用图灵机处理的问题，都是不可计算的问题。

素数是不是有无穷多个？
停机问题

计算就是枚举，这样的枚举是 ∞ 的，也就是不可计算。

计算是需要开销的，时间，空间。

时间复杂度衡量计算的规模：

$访问数组的元素 O (1)$

$求数组中的最大值 O (N^{2})$

$求一个 n * n 矩阵的和 O (N^{2})$

$更多问题 O (N^{3}) O (N^{4}) O (N^{n})$

能被计算的问题称为多项式问题（Polynomial time），另外一些问题本身的复杂度是 $O (2^{N})$ ，与数据规模对应，这类问题就被称为 NP 问题。

有些问题可以通过一些手段优化成 P 问题，典型的如斐波那契数列可以通过记忆化搜索、动态规划优化成 $O (N)$ 的时间复杂度。

或者限定情况，如 AlphaGo 就是围棋这个领域的 AI，它围棋也许比李世石厉害，但象棋一定不比在座的各位强。