这周的算法学习可以说有了更加明确的目标。学习起来也更有动力和积极性。现在调整了自己的学习方法，首先大概浏览每章的主要内容，知道大概的实现方法，等第二轮在进行实践提高。
这周学的主要内容：第一章的4节，第二章的2、3、4节和第三章的第一节
第一章第四节：算法分析
主要从两个方面来研究算法的性能，时间复杂度与空间复杂度。时间复杂度主要由cost model 来近似，研究流程如下:1、确定输入模型（输入如何影响输出的），包括如何定义问题的规模。2、识别内循环（总循环次数最多的）。3、对内循环里的每条运算符定义它们对应的cost model。3、对于给定输入，确定相应的指令执行的频率。
一种实用的分析时间复杂度增长指数的方法：
简化模型的一些不足：1、较小次幂项前大系数的忽略误差。2、内循环并没有在时间复杂度模型中起主导作用（样本的数量不够多，或者忽视了真正的内循环）。3、指令集的时间长短不是固定的（cache在处理内存过程中，在处理数组中相距较远的元素时，指令会消耗更多的时间）。4、系统造成的误差，使得系统的影响可以忽略或者在可控的范围内。5、对输入的变化不敏感。（输出3-SUM的数量，和判断是否存在3-SUM）。6、多重输入变量的影响（算法内部的数据结构中包含的变量，区别于输入值）。
消除输入变量对于输入的依赖性，除了更好地建模以外，我们还要提供最坏情况下的分析。以保证再输入最不理想的情况下达到我们的实验要求。
空间分析主要考虑一些内存的占用情况。包括一些程序语言对于内存调用情况的分析。《疯狂JAVA讲义》里面提到的一些初始化的内存调用情况分析，常见数据类型的占用内存大小。基本初始化和函数调用内存的情况的分析。栈内存与堆内存，对象调用数据类型时是通过栈内的引用变量，调用堆内存储的数据。和基本初始化赋值时“值传递”的基本设计思想。“object overhead”内存情况要根据具体虚拟机的机制来解释。
第二章第二节 归并算法
归并算法，其实就是利用二分原则，不断调用本身，先产生最小长度的数组，利用merge method,进行合并。不断的二分排序，最后合并成一个数组的过程，合并的两个数组一定是排好序的数组。mergesort的时间复杂度分析，是通过确定比较次数来规定的（less指令）。最后的时间复杂度降到linearithmic.归并算法的另一种归并方向是通过由底向上，利用For循环来代替调用自身的指令。
第二章第三节 快速排序
快排相较于归并，优势在于当两个个数组排好序的同时，整个数组也完成排序。节省了很多空间上的占用。
（未完待续）
网友评论