算法导论第一章


		算法导论中，算法的定义：定义良好的计算过程，它取一个活一族值作为输入，并产生出一个活一族值作为输出。
习题：
1.1-1：给出一个真实世界的例子，其中包含着下列的某种计算问题：排序，确定多矩阵相乘的最佳顺序，或者找出凸壳
排序：每年世界500强公司收入排序
确定多矩阵相乘的最佳顺序：使用结合律 A*B*C=A*（B*C）
找出凸壳：给定平面上n个点，希望找出这些点的凸壳，即包含这些点的最小凸多边形。从直观上看，可以将每一个点看成由一块板上突起的一个钉子表示。因此，包围这些点的凸壳可以看成是一根包围了所有这些钉子的紧绷的橡皮绳。每一个令橡皮绳发生方向变化的钉子都是该凸壳的一个顶点。这些点的2n个子集中的任何一个都可能是凸壳的顶点。知道哪些是该凸壳的顶点还不够，还需要知道他们出现的顺序，因此，该凸壳的顶点构成有多重选择。
1.1-2除了运行速度以为，在真实世界问题背景中，还可以使用哪些效率指标。
公司的投入产出比；
1.1-3选择你原来见过的某种数据结构，讨论一下其长处和局限性。
数组：方便直接索引，但是对于插入的操作可能需要移动位置。
链表：方便插入操作，但是在查询的时候，不能直接索引需要遍历。
1.1-4上文中给出的最短路径问题和旅行商人问题有哪些相似之处？有哪些不同之处？
相似之处：这两个问题都是求最短的路径
不同之处：最短路径问题其实是给定了情景并且不需要遍历所有的点，而旅行商人问题则需要遍历所有的点并求得最短的路程，问题的复杂度不一样。亦可以找到一个最短的路径，但是你无法找到一个选择一条送货车行驶距离最短的送货顺序。其实是一个NP完全问题。
1.1-5举出一个现实世界问题的例子，他只能用最佳的解决方案来解决。再举出另一个例子，在其中“近似”最优解决也足以解决问题。
1)有一个固定大小的纸箱子，怎样将不同大小的东西更多的放入纸箱中储藏；
2)解一元二次方程的时候使用逼近法来获得在范围之内的解。
 
1.2-1给出一个实际应用的例子，他在引用这一层次上要求有算法性的内容。讨论其中所设计的算法功能。
例如我们玩儿的3D游戏，它其中的成像技术需要使用到计算机图形学的算法；
1.2-2假设我们要比较在同一台计算机上插入排序和合并排序的实现。对于规模为n的输入，插入排序要运行8n*n步，而合并排序需要运行64n*logn步。当n取怎样的值时，插入排序的性能要优于合并排序？
n=2时， 8n*n < 64n*logn即8*2*2=32<64*2*1
n=2^6=64时8*64*64<64*64*6
大概得出n的范围为[2,64]都是的插入排序小于合并排序。
1.2-3对于一个运行时间为100n*n的算法，要使其在同一台机器上，在比一个运行时间为2^n的算法运行的很快，n的最小值是多少？
n>15的时候，（注：解法拿计算器实验出来的~~~）
 
1-1思考题
计算方法是f(n)=t就求解除n的规模了，注意时间单位。

补充：综合编程 , 其他综合 ,