可计算问题理论笔记

计算机可以求解哪些问题？
求解计算问题的思路
衡量求解计算问题的算法优劣--复杂度分析
复杂度分析的尺度
复杂度分析的方法
实例分析

计算机可以求解哪些问题？

结论：可用限步骤计算出来的数学问题，即有明确解的数学问题

答案的贡献者：英国计算机科学家-图灵，前苏联数学家马季亚谢维奇

图灵.png

马季亚谢维奇.png

基本事实：

世界上有很多问题，其中只有一小部分是数学问题；
在数学问题中，只有一小部分是有解的；
在有解的问题中，只有一部分是理想状态的图灵机可以解决的；
在后一类的问题中，又只有一部分是今天实际的计算机可以解决的；

人工智能的边界.png

求解计算问题的思路

两种思路

减而治之

减而治之.png
分而治之

分而治之.png

正确性：由不变性(原问题和规模减小后的问题类似)+单调性(问题规模递减)保证；

衡量求解计算问题的算法优劣

本质就是对算法进行分析
思路：
首先，选择算法的运行时间和使用空间作为尺度进行衡量；
接着，重点进行运行时间分析，将运行时间分析归结为基本操作的总执行次数分析，即将各个算法的比较归结为有关问题规模n的函数比较；

时间复杂度分析-归结.png

进一步，比较函数在n接近无穷大情形的增长阶，即进行复杂度分析
理由：

高德纳的思想主要包括这三个部分：

在比较算法的快慢时，需要考虑数据量特别特别大，大到近乎无穷大时的情况。为什么要比大数的情况，而不比小数的情况呢？因为计算机的发明就是为了处理大量数据的，而且数据越处理越多。比如我和同学们做砸了的那件事，就是没有考虑数据量会迅速剧增。

决定算法快慢的因素虽然可能很多，但是所有的因素都可以被分为两类。第一类是不随数据量变化的因素，第二类是随着数量变化的。
比如说，有一种大小排序的算法，它的运算次数是10倍的N平方，其中N是要排序的数字的数量。前面的那个10倍是个常数，和N的大小显然没有关系，10个数排序是如此，一亿个数排序时也是如此。而后面的N平方自然和N有关系了。高德纳讲，我们在研究算法时，不必考虑前面那个不变的常数，它是10倍，还是1倍，或者是100倍，只需要看后面那个变化的因素即可。
因为N这个数趋近于无穷大时，前面那个不变的常数的影响是微乎其微的，算法的速度主要由后面一个因素决定。比如，当N＝10的时候，N平方就是100；N＝100，N平方就是1万；N＝1万，N平方就是一亿……总之，N平方这个因子的变化非常快。更广泛地讲，任何随着N变化的因素，通常会造成量级的差异。关于量级，我们在第005封来信里讲了。量级就如同芝麻和西瓜的差异，西瓜和地球的差异。100个芝麻是无法和一个西瓜去对比的。

如果两种算法在量级上相当，在计算机科学里，就认为它们是一样好的，也就是计算机科学家并不关心三五倍的差别，这就好比1粒芝麻和5粒芝麻都是芝麻量级的东西，大家就不要比了。只有当科学家们不关心几倍的差异后，才可能集中精力考虑量级的差异。

这里提供一种算法分析框架