1.数学模型
①4个重要的定义：如果存在正常数c和n使得N>=n时
，记作
，记作
当且仅当且有
如果且有
②
：f（N）是 T（N）的上界
：f（N）是T（N）的下界
③ 我们需要掌握的重要结论：
法则1：如果且
(a)
(b)
法则2：如果T（N）是一个k次多项式，
法则3：对任意常数k，。它告诉我们对数增长得非常缓慢
2.要分析的问题
影响着程序的运行时间的主要因素：所使用的算法以及对该算法的输入
①输入的大小
：最坏情况下的运行时间（通常情况，以这个为判别算法好坏的标准）
：平均运行时间
②最大的子序列和问题：
给定整数，·····，（可能有负数），求的最大值。
3.运行时间的计算
①一般法则：从内向外展开（基本策略）
for循环：一次for循环的时间至多是该for循环内语句的运行时间乘以迭代的次数
嵌套的for循环：从里向外分析这些循环，运行时间为该语句的运行时间乘以改组所有for循环的大小的乘积
顺序语句：各语句的运行时间求和
if/else语句：不超过判断再加上if中的语句和else中语句中运行时间最长者的总的运行时间
②一个例子：
long int Fib(int N){if(N<=1)return 1;elseretrun Fib(n-1)+Fib(n-2);}
的运行时间公式：
可见这个程序的运行时间以指数的速度增长：注意在调用Fib（n-1）实际上计算了Fib（n-2）。这个信息被抛弃在第二次调用时又重新计算了一遍。
“计算任何事情不要超过一次”
③最大子序列和问题的解
算法1：穷举地尝试所有的可能
int MaxSequenceSum(const int A[],int N){int ThisSum,MaxSum,i,j,k;MaxSum=0;for(i=0;i<N;i++)for(j=i;j<N;j++){ ThisSum=0;for(k=i;k<=j;k++)ThisSum+=A[k];if(ThisSum>MaxSum)MaxSum=ThisSum;}return MaxSum;}
算法2：撤销一个for循环避免立方运行时间
int MaxSequenceSum(const int A[],int N){int ThisSum,MaxSum,i,j;MaxSum=0;for(i=0;i<N;i++){ThisSum=0;for(j=i;j<N;j++){ThisSum+=A[j];if(ThisSum>MaxSum)MaxSum=ThisSum;}}return MaxSum;}
算法3：“分治”的策略。把问题分成两个大致相等的子问题，然后递归地对它们求解。这是“分”的部分。“治”阶段将两个子问题的解合并在一起并可能地做少量的附加地工作
说明:递归过程的调用的一般形式是传递输入的数组以及左边界和有边界，它们界定了数组要处理的部分。
不难得到前半部分最大子序列和为6，后半部分最大子序列和为8，横跨两部分的中间部分的最大子序列和则为11。
static int MaxSubSum(const int A[],int Left,int Right){int MaxLeftSum,MaxRightSum;int MaxLeftBorderSum,MaxRightBorderSum;int LeftBorderSum,RightBorderSum;int Center,i;/* Base Case */if(Left==Right){if(A[Left]>0)return A[left];else return 0;}Center=(Left+Right)/2;MaxLefeSum=MaxSubSum(A,Left,Center);MaxRightSum=MaxSubSum(A,Center,Right);MaxLeftBorderSum=0;LeftBorderSum=0;for(i=Center;i>=Left;i--){LeftBorderSum+=A[i];if(LeftBorderSum>MaxLeftBorderSum)MaxLeftBorderSum=LeftBorderSum;}MaxRightBorderSum=0;RightBorderSum=0;for(i=Center+1;i<=Right;i++){RightBorderSum+=A[i];if(RightBorderSum>MaxRightBorderSum)MaxRightBorderSum=RightBorderSum;}return Max3(MaxLeftSum,MaxRightSum,LeftBorderSum+RightBorderSum);/*Max3返回三者中的最大数 */}int MaxSequenceSum(const int A[],int N){return MaxSubSum(A,0,N-1);}
得到运行时间的方程组：
解得
算法4：只对数据进行一次扫描，一旦A[i]读入并被处理，它就不再需要被记忆
int MaxSequenceMax(const int A[],int N){int ThisSum,MaxSum,j;ThisSum=MaxSum=0;for(j=0;j<N;j++){ThisSum+=A[j];if(ThisSum>MaxSum)MaxSum=ThisSum;else if(ThisSum<0)ThisSum=0;}return MaxSum;}
④运行时间中的对数
将对数最常出现的规律归纳为下列一般法则：
如果一个算法常用常数时间将问题的大小消减为其一部分，那么该算法就是
如果使用常数时间把问题减少一个常数，那么该算法就是
对分查找：
循环在High-Low=N-1开始，在High-Low>=-1时结束。每次循环后High-Low的值至少将该次循环前的值折半。于是循环的次数最多是
int BinarySearch(const ElementType A[],ElementType X,int N){int Low,Hight,Mid;Low=0;Hight=N-1;while(Low<=High){Mid=(Low+High)/2;if(A[Mid]<X)Low=Mid+1;else if([Mid]>X)High=Mid-1;else return Mid;}return NotFound;}
欧几里得算法：计算最大公因子
我们可以证明，在两次迭代后，余数最多是原始值的一半。
unsigned ind Gcd(unsigned int M,unsigned int N){unsigned int Rem;while(N>0){ Rem=M%N;M=N;N=Rem;}return M;}
定理2：
如果M>N，则M mod N < M/2;
幂运算：
计算最常见的方法就是使用N-1次乘法自乘。
long int Pow(long int X,unsigned int N){if(N==0)return 1;if(N==1)return X;if(IsEven(X)) return Pow(X*X,N/2);else return Pow(X*X，N/2)*X;}
⑤ 检验你的分析
⑥分析结果的准确性
