南大软院 数据结构.ppt

文档介绍：数据结构
算法的时间复杂性
估算一个程序或者函数的时间复杂性就是首先选择一种或多种操作(如加、乘和比较等等),然后确定这种操作分别执行了多少次。
取决于识别关键操作的能力,这些关键操作对时间复杂性的影响最大。
渐近符号(O)
f(n)表示一个时间或者空间复杂性,是实例特征n的函数。显然,f(n)>=0,同时n>=0。渐近符号允许我们对于足够大的n值,给出f的上限值或下限值。
渐近符号O给出了函数f的一个上限。
f(n)=O(g(n))当且仅当存在正的常数c和n0,使得对所有的n>= n0,有f(n)<=cg(n)
f(n)=3n+2, f(n)=O(n); f(n)=10n2,f(n)=O(n2)
f(n) = 10n2+ 3n+2, f(n)=O(?)
直接插入排序算法
一个元素的数组是一个有序的数组
从第一个元素开始,通过把第二个元素插入到这个单元数组中,就可以得到一个大小为2的有序数组。
依次类推,插入第三个元素可以得到一个大小为3的有序数组,……
该算法称为直接插入排序。
算法实现(JAVA)
void InsertionSort (int a[], int n)
{
for (int i =1;i<n; i++)
{
int temp = a[i];
int j =0;
for (j=i-1;j>=0&&temp<a[j]; j--)
{
a[j+1]=a[j];
}
a[j+1] = temp;
}
}
该算法复杂度
比较次数,f(n)>=n-1,f(n)<=(n-1)n/2
所以f(n) = O(n*n)或则O(n2)
快速排序
任取待排序序列中的某个元素作为基准(一般取第一个元素),通过一趟排序,将待排元素分为左右两个子序列,左子序列元素的排序码均小于或等于基准元素的排序码,右子序列的排序码则大于基准元素的排序码,然后分别对两个子序列继续进行排序,直至整个序列有序。
exercise
给出上述快速排序理论上的最佳划分序列
抽象数据类型
表ADT
栈ADT
队列ADT