第十章 某些算法的分析
一、线性结构相关时间复杂度分析
1、顺序表
访问O(1)、顺序查找O(n)、折半查找O(log2n)插入删除：O(n)
2、链表
访问O(n)、顺序查找O(n)、插入删除(事先直到插入删除的位置）：O(1)
二、非线性结构相关的时间复杂度分析
1、树
遍历O(n)
2、图
（1）邻接矩阵：遍历O(n2) Prim O(n2)
（2）邻接表：遍历O(n+e)
（3）Kruskal O(eloge)
（4）Dijkstra O(n2) Floyd O(n3)
三、汉诺塔问题（递归、分治）
void hanoi(int n,char a,char b,char c)
{
if(n==1)
std::cout<<a<<"->"<<c<<std::endl;
else
{
hanoi(n-1,a,c,b);
std::cout<<a<<"->"<<c<<std::endl;
hanoi(n-1,b,a,c);
}
} 复杂度分析：写递归函数！T(n)=2T(n-1)+c=T(2n) 四、排序算法的性能分析
希尔排序：增量每次都除以二并向下取整，O(n2)。增量取2k+1
