渐进上界：得到一个问题规模充分大时一个算法的时间复杂度的上界
。
相同定义 渐进下界
渐进精确界：既是渐进上界，又是渐进下界
最优算法：算法A所在的算法类中的其他算法，在最坏（或平均）情况下，执行基本操作的次数不比A更少。
第一章：排序问题
排序：n个数据元素按照key递增或者递减排序
n个元素的序列有n！种不同排列，每种排列用”Π“标记
一、直接插入排列
特点：每次比较后发生一次移动或者不发生移动
额外空间：o(1)
时间：
1.最好情况：待排序序列已经有序，需要n-1次比较，0次移动
2.最坏情况：待排序序列逆序，需要次比较，
次移动。
3.平均情况A(n)：求解所有情况的时间不现实，所以选则求解插入第i个元素时的平均比较次数，再求和
对直接插入排序的分析：直接插入排序每次比较操作最多移动一次数据，每次比较最多消灭一个逆序对，直接插入排序中有多少逆序对就要至少比较几次
最坏情况：待排序序列完全逆序，个逆序对，则其时间复杂度最少为
,且无法改进。
平均情况：技巧：两个相反情况的逆序共有个，每个占一半为平均情况
note：这两种情况均无法再进行改进。
二、冒泡排序
将待排序的按照元素的key顺序两两比较，若逆序则交换，将最大的key元素换到了当前待排序序列的最后，若某趟冒泡没发生元素交换，那么排序结束
特点：最多需要n-1次冒泡，每次比较最多消灭一个逆序对
void bubblesort(Element E[], int n)
{
int numpairs;
int didswitch;
int j;
numpairs = n-1;//numpairs 记录当前趟比较的次数
didswitch = 1;
while(didswitch)//didswitch 记录当前趟冒泡是否交换过数据，没交换过则结束循环
{
didswitch = 0;//将didswitch置零
for(j = 0; j<numpairs; j++)
{
if(E[j]>E[j+1])
{
E[j]<->E[j+1];
didswitch = 1;
}
}
numpairs--;//每趟使得需要比较的数-1
}
} 证明冒泡排序的正确性：（数学归纳法）
时间复杂度：
B(n):最好情况：待排序序列已经有序，n-1次比较，0次移动 复杂度大小O(n)
W(n):最坏情况：待排序序列逆序，次比较，
次移动
A(n):假设每种情况出现的概率是相同的，可证
改进方法：每趟冒泡排序都跟踪第一次，最后一次交换的位置
void bubblesort(Element E[], int n)
{
int numpairs;
int firstchange,lastchange;//每趟冒泡排序第一次 ，最后一次发生交换的位置
int didswitch;
int j;
numpairs = n-1;//numpairs 记录当前趟比较的次数
didswitch = 1;
firstchange = 1;
while(didswitch)//didswitch 记录当前趟冒泡是否交换过数据，没交换过则结束循环
{
didswitch = 0;//将didswitch置零
for(j = firstchange - 1; j<lastchange; j++)
{
if(E[j]>E[j+1])
{
E[j]<->E[j+1];
if(!didswitch)
{
firstchange = j;//记录第一次交换时的位置
}
didswitch = 1;
numspairs = j;
}
}
lastchange = numpairs;
if(firstchange<1) firstchange = 1;
}
//通过及记录第一次交换时的位置，当前面排好序的时候，可以减少时间
} 三、分治策略
大规模问题分解为多个规模较小的问题——解决并合并为原问题的解
流程：划分->解决->合并
