? 算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
? 1、有穷性（Finiteness）：算法必须能在执行有限个步骤后终止。
? 2、确定性（Definiteness）：算法的每一步骤必须有确切的含义。
? 3、输入项（Input）：一个算法有零个或多个输入，这些输入取自某个特定的对象集合。
? 4、输出项（Output）：一个算法有一个或多个输出，以反映对输入数据加工后的结果。
? 5、可行性（Effectiveness）：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
? 1、自然语言
? 2、流程图
? 3、程序设计语言
? 4、伪代码
? 常用的算法设计策略有：分治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等。
? 算法分析技术的主要内容：正确性、可靠性、简单性、易理解性、时间复杂度和空间复杂度等。
分治法的基本思想：将一个难以直接解决的大问题，分解成一些规模较小的子问题，这些子问题相互独立且与原问题相同，然后各个击破，分而治之。
分治法常常与递归结合使用：通过反复应用分治，可以使子问题与原问题类型一致而规模不断缩小，最终使子问题缩小到很容易求出其解，由此自然导致递归算法。
人们从大量实践中发现，在使用分治法时，最好均匀划分。这种使子问题规模大致相等的做法源自一种平衡子问题的思想，它几乎总是比使子问题规模不等的做法好。
一般来说，分治算法在每一层递归上都有3个步骤。
(1) 分解。将原问题分解成一系列子问题。
(2) 求解。递归地求解各子问题。若子问题足够小，则直接求解。
(3) 合并。将子问题的解合并成原问题的解。
归并排序算法是成功应用分治法的一个完美的例子，其基本思想是将待排序元素分成大小大致相同的两个子序列，分别对这两个子序列进行排序，最终将排好序的子序列合并为所要求的序列。
归并排序算法完全依照上述分治算法的3个步骤进行。
(1) 分解。将n个元素分成各含n2个元素的子序列。
(2) 求解。用归并排序对两个子序列递归地排序。
(3) 合并。合并两个已经排好序的子序列以得到排序结果。
归并排序算法的C代码如下：
// 其中，A是数组，p、q和r是下标，满足p≤q<r。
void MergeSort(int A[], int p, intr){
int q;
if(p <r){
q=(p+r) / 2;
MergeSort(A, p, q);
MergeSort(A, q+1, r);
Merge(A, p, q, r);
}
}
void Merge(int A[], int p, int q, int r){
int nl=q-p+1, n2=r-q, i, j, k;
int L[50],R[50];
for(i=0;i< nl;i++)
L[i] = A[p+i];
for(j=0;j<n2;j++)
R[j] = A[q+j+1];
L[n1] = INT_MAX;
R[n2] = INT_MAX;
i=0;
j=0;
for(k=p; k<r+1; k++){
if(L[i] < R[j]){
A[k]=L[i];
i++;
}
else{
A[k]=R[j];
j++;
}
}
}
Merge 显然可在O(n)时间内完成，因此合并排序算法对n个元素进行排序所需的计算时间T(n)满足：
T ( n ) = { O ( n ) , n ≤ 1 2 T ( n / 2 ) + O ( n ) , n > 1 T(n)=\begin{cases}O(n),&n≤1\\2T(n/2)+O(n),&n>1\end{cases} T(n)={O(n),2T(n/2)+O(n),?n≤1n>1?
解此递归式可知T(n)=O(n log n)。
给定由n个整数(可能有负整数)组成的序列 a1，a2，… ,an，求该序列形如 ∑ k = i j a k \sum_{k=i}^{j}{a_k} ∑k=ij?ak?的子段和的最大值。当序列中所有整数均为负整数时，其最大子段和为0。依此定义，所求的最大值为 m a x { 0 , m a x 1 ≤ i ≤ j ≤ n ∑ k = i j a k } max\{0,max_{1≤i≤j≤n}\sum_{k=i}^{j}{a_k}\} max{0,max1≤i≤j≤n?∑k=ij?ak?} 。例如，当(a1，a2，a3，a4，a5，a6) = -1,11,-4,13,-7,-3)时，最大子段和为 ∑ k = 2 4 a k = 20 \sum_{k=2}^{4}{a_k}=20 ∑k=24?ak?=20。
最大子段和问题的分治策略如下：
(1) 分解。如果将所给的序列A[1…n]分为长度相等的两段A[1…n/2]和A[n/2+1…n]，分别求出这两段的最大子段和，则A[1…n]的最大子段和有3种情形。
① A[1…n]的最大子段和与A[1…n/2]的最大子段和相同。
② A[1…n]的最大子段和与A[n/2+1…n]的最大子段和相同。
③ A[1…n]的最大子段和为
∑
k
=
i
j
a
k
\sum_{k=i}^{j}{a_k}
∑k=ij?ak?，且1≤i≤n/2，n/2+1≤j≤n。
(2) 求解。①和②这两种情形可递归求得。对于情形③，容易看出，A[n/2]与A[n/2+1]在最优子序列中。因此可以在A[1…n/2]中计算出s1=
m
a
x
1
≤
i
≤
n
/
2
∑
k
=
i
n
/
2
a
k
max_{1≤i≤n/2}\sum_{k=i}^{n/2}{a_k}
max1≤i≤n/2?∑k=in/2?a
