以下六种计算算法时间的多项式是最常 用的。其关系为 O(1<O(ogn)<O(n<o(nlogn) <O(n2)<O(n3) 指数时间的关系为 O(2)<O(n!)<O(n2) 当n取得很大时,指数时间算法和多项 式时间算法在所需时间上非常悬殊。因 此,只要有人能将现有指数时间算法中 的任何一个算法化简为多项式时间算法, 那就取得了一个伟大的成就
⚫ 以下六种计算算法时间的多项式是最常 用的。其关系为： ⚫ O(1)<O(logn)<O(n)<O(nlogn) ⚫ <O(n2)<O(n3) ⚫ 指数时间的关系为： ⚫ O(2n )<O(n!)<O(nn ) ⚫ 当n取得很大时，指数时间算法和多项 式时间算法在所需时间上非常悬殊。因 此，只要有人能将现有指数时间算法中 的任何一个算法化简为多项式时间算法， 那就取得了一个伟大的成就
。有的情况下,算法中基本操作重复执行的次数 还随问题的输入数据集不同而不同。例如: Void bubble-sort(int all, int n) for(In-1; change-TURE, I>I & change; - -D) change=false for(=0 j<I; ++ if(ai>a[计+1]){ ←→a[+1] change=TUREJ 最好情况:0次
⚫ 有的情况下，算法中基本操作重复执行的次数 还随问题的输入数据集不同而不同。例如： ⚫ Void bubble-sort(int a[]，int n) ⚫ for(I=n-1;change=TURE;I>1 && change;--I) ⚫ { ⚫ change=false; ⚫ for(j=0;j<I;++j) ⚫ if (a[j]>a[j+1]) { ⚫ a[j] ←→a[j+1]; ⚫ change=TURE} ⚫ } ⚫ 最好情况：0次 ⚫
最坏情况:1+2+3+.+n-1 =n(n-1)/2 平均时间复杂度为O(n2) 1.44算法的存储空间需求 空间复杂度:算法所需存储空间的度量, 记作 S(n=o(f(n)) 其中n为问题的规模(或大小)
⚫ 最坏情况：1+2+3+…+n-1 ⚫ =n(n-1)/2 ⚫ 平均时间复杂度为:O(n2) ⚫ 1.4.4算法的存储空间需求 ⚫ 空间复杂度:算法所需存储空间的度量， 记作: ⚫ S(n)=O(f(n)) ⚫ 其中n为问题的规模(或大小)
第二章线性表 2.1线性表的类型定义 22线性表的顺序表示和实现 23线性表的链式表示和实现 2.3.1线性链表 2.3.2循环链表 2.33双向链表 24一元多项式的表示及相加
第二章 线性表 ⚫ 2.1 线性表的类型定义 ⚫ 2.2 线性表的顺序表示和实现 ⚫ 2.3 线性表的链式表示和实现 ⚫ 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加
。线性表( Linear List):由n(n≡)个数据元素(结 点a1,a2,an组成的有限序列。其中数据元 素的个数n定义为表的长度。当n=0时称为空表 常常将非空的线性表(m>0)记作: (a1,a 。这里的数据元素a(1sin)只是一个抽象的符 其具体含义在不同的情况下可以不同 例1、26个英文字母组成的字母表 (A, B, C 例2、某校从1978年到1983年各种型号的计算 机拥有量的变化情况。 (6,17,28,50,92,188)
⚫ 2.1 线性表的逻辑结构 ⚫ 线性表(Linear List) ：由n(n≧)个数据元素(结 点)a1，a2， …an组成的有限序列。其中数据元 素的个数n定义为表的长度。当n=0时称为空表， 常常将非空的线性表(n>0)记作： ⚫ (a1，a2，…an ) ⚫ 这里的数据元素ai (1≦i≦n)只是一个抽象的符 号，其具体含义在不同的情况下可以不同。 ⚫ 例1、26个英文字母组成的字母表 ⚫ （A，B，C、…、Z） ⚫ 例2、某校从1978年到1983年各种型号的计算 机拥有量的变化情况。 ⚫ （6，17，28，50，92，188）