算法导论（一）

Introduction to Algorithms (third edition)

第一章：The Role of Algorithms in Computing

概述：算法就是对将输入转化为输出的计算过程的描述，能解决很多现实问题，对同一个问题，不同的算法有不同的效率，我们的终极目标就是为所有问题找到最有效、最优的算法。

第二章：Getting Started

由插入排序问题引入算法的正确性分析，主要分为三步：初始化、执行、结束，算法的正确性分析就是要从这三方面着手。通过分析算法的运行时间，引入O表示。通过引入归并排序，介绍算法设计中分治（divide-and-conquer）思想，并分析归并排序的时间复杂度。

Q2.3-7: 将S排序，头尾各放一指针，比较头尾指针所指的两数之和与x的大小，移动指针，直至找到所求或者遍历完S。排序复杂度O(nlgn)，遍历复杂度O(n)，总复杂度O(nlgn)。

第三章：Growth of Functions

详细介绍O、o等复杂度记法，简要介绍一些基本的数学知识，主要是理论知识介绍，不涉及算法。

第四章：Divide-and-Conqur

专门用一章来讲分治算法，可见分治思想在算法设计中的重要性。其实不仅是在算法中，在现实生活中，分治思想也是很重要的：当碰到一个难题时，不妨想想能不能将难题化小，通过解决一个个的小问题逐渐将难题解决。用最大子段和、矩阵相乘做例子，其实个人感觉用最大子段和做例子不太恰当，因为练习中也提到了存在O(n)的算法解决这个问题，所以如果用平面上的最近点对问题来做例子是不是更恰当点呢？至于矩阵相乘，这个算法确实很有想象力，但是太复杂了，不用参考书应该没几个人能推导出来那么复杂的计算方式吧？最后，给出了master定理，对T(n) = aT(n/b) + f(n)的复杂度分析给出了一般性的结论，并证明了master定理，如果不是搞算法研究的话证明这些细节就不用去看了。

4.1-1 return the largest negative value of course

4.1-5 dp[i] = max {dp[i-1] + a[i], a[i] }, O(n)

4.2-7 let X = ac, Y = bd, Z = (a+b)(c+d), then ac-bd = X - Y, ad+bc = Z - X - Y

4.3-1 T(n) = T(n-1) + n = T(n-2) + n-1 + n = ... = 1 + 2 + ... + n = n*(n+1)/2 = O(n^2)