赞
踩
数据类型
数据类型是一组性质相同的值的集合, 以及定义于这个集合上的一组运算的总称。
抽象数据类型(ADTs: Abstract Data Types)
抽象数据类型可以用以下的三元组来表示
ADT = (D,S,P)
D:数据对象 S:D上的关系集 P:D上的操作集
ADT常用定义格式
ADT抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作 :<基本操作的定义>
} ADT抽象数据类型名
信息隐蔽和数据封装,使用与实现相分离
抽象数据类型的表示与实现
复数—抽象数据类型的定义
ADT Complex { 数据对象:D={e1,e2|e1,e2∈R,R是实数集} 数据关系:S={<e1,e2>|e1是复数的实部,e2是复数的虚部} 基本操作: Creat(&C,x,y) 操作结果:构造复数c,其实部和虚部分别被赋予参数x和y的值。 GetReal(C) 初始条件:复数c已存在。 操作结果:返回复数c的实部值。 GetImag(C) 初始条件:复数c已存在。 操作结果:返回复数c的虚部值。 Add(C1,C2) 初始条件:C1,C2是复数。 操作结果:返回两个复数C1和C2的和。 Sub(C1,C2) 初始条件:C1,C2是复数。 操作结果:返回两个复数c1和C2的差。 } ADT Complex typedef struct //复数类型 { float Realpart; //实部 float Imagepart; //虚部 }Complex; void Create(&Complex C,float x,float y) {//构造一个复数 C.Realpart=x; C.Imagepart=y; } float GetReal(Complex C) {//取复数C=x+yi的实部 return C.Realpart; } float GetImag(Complex C) {//取复数C=x+yi的虚部 return C.Imagepart; } Complex Add(Complex C1,Complex C2) {//求两个复数C1和C2的和sum Complex sum; sum.Realpart=C1.Realpart+C2.Realpart; sum.Imagepart=C1.Imagepart+C2.Imagepart; return sum; } Complex Sub(Complex C1,Complex C2) {//求两个复数C1和C2的差difference Complex difference; difference.Realpart=C1.Realpart-C2.Realpart; difference.Imagepart=C1.Imagepart-C2.Imagepart; return difference; }
//函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW -2
// Status是函数返回值类型,其值是函数结果状态代码。
typedef int Status;
算法与算法分析
一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列
算法的描述
自然语言、流程图、程序设计语言、伪码
算法的特性
输入 有0个或多个输入
输出 有一个或多个输出(处理结果)
确定性 每步定义都是确切、无歧义的
有穷性 算法应在执行有穷步后结束
有效性 每一条运算应足够基本
算法的评价
正确性、可读性、健壮性、高效性(时间代价、空间代价)
算法的效率的度量
用依据该算法编制的程序在计算机上执行所消耗的时间来度量
事后统计
利用计算机内的计时功能,不同算法的程序可以用一组或多组相同的统计数据区分
缺点
必须先运行依据算法编制的程序
所得时间统计量依赖于硬件、软件等环境因素,掩盖算法本身的优劣
事前分析估计
一个高级语言程序在计算机上运行所消耗的时间取决于:
同一个算法用不同的语言、不同的编译程序、在不同的计算机上运行,效率均不同,——使用绝对时间单位衡量算法效率不合适
时间复杂度的渐进表示法
算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作:T(n)=O(f(n)) 。
表示随着n的增大,算法执行的时间的增长率和f(n)的增长率相同,称渐近时间复杂度。
数学符号“O”的定义为:若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n) = O(f(n))表示存在正的常数C和n0,使得当n≥n0时都满足0≤T(n)≤Cf(n)。
算法中重复执行次数和算法的执行时间成正比的语句对算法运行时间的贡献最大
n越大算法的执行时间越长
- 排序:n为记录数
矩阵:n为矩阵的阶数
多项式:n为多项式的项数
集合:n为元素个数
树:n为树的结点个数
图:n为图的顶点数或边数
n * n阶矩阵加法
for( i = 0; i < n; i++)
for( j = 0; j < n; j++)
c[i][j] = a[i][j] + b[i][j];
语句的频度(Frequency Count ): 重复执行的次数:n*n;
T(n) = O (n2)
即:矩阵加法的运算量和问题的规模n的平方是同一个量级
分析算法时间复杂度的基本方法
找出语句频度最大的那条语句作为基本语句
计算基本语句的频度得到问题规模n的某个函数f(n)
取其数量级用符号“O”表示
x = 0; y = 0;
for ( int k = 0; k < n; k ++ )
x ++;
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < n; j++ )
y ++;
T(n) = O(n2)
f(n)=n2
时间复杂度是由嵌套最深层语句的频度决定的
void exam ( float x[ ][ ], int m, int n ) {
float sum [ ];
for ( int i = 0; i < m; i++ ) {
sum[i] = 0.0;
for ( int j = 0; j < n; j++ )
sum[i] += x[i][j];
}
for ( i = 0; i < m; i++ )
cout << i << “ : ” <<sum [i] << endl;
}
T(n) = O(mn)
f(n)=mn
例1:N×N矩阵相乘
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{c[i][j]=0;
for(k=1;k<=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
T(n) = O(n3)
算法中的基本操作语句为c[i][j]=c[i][j]+a[i][k]*b[k][j];
T ( n ) = ∑ i = 1 n ∑ j = 1 n ∑ k = 1 n 1 = ∑ i = 1 n ∑ j = 1 n n = ∑ i = 1 n n 2 = n 3 = O ( n 3 ) T(n)=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}1=\sum_{i=1}^{n}\sum_{j=1}^{n}n=\sum_{i=1}^{n}n^2=n^3=O(n^3) T(n)=i=1∑nj=1∑nk=1∑n1=i=1∑nj=1∑nn=i=1∑nn2=n3=O(n3)
例2
for( i=1; i<=n; i++)
for (j=1; j<=i; j++)
for (k=1; k<=j; k++)
x=x+1;
定理1.1
若f(n)=amnm+am-1nm-1+…+a1n+a0是m次多项式,则T(n)=O(nm)。
O(nm)忽略所有低次幂项和最高次幂系数,体现出增长率的含义
语句频度 = ∑ i = 1 n ∑ j = 1 i ∑ k = 1 j = ∑ i = 1 n ∑ j = 1 i j = ∑ i = 1 n i ( i + 1 ) 2 = 1 2 ∑ i = 1 n i 2 + ∑ i = 1 n i = 1 2 ( n ( n + 1 ) ( 2 n + 1 ) 6 + n ( n + 1 ) 2 ) = n ( n + 1 ) ( n + 2 ) 6 语句频度=\sum_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}=\sum_{i=1}^{n}\sum_{j=1}^{i}j=\sum_{i=1}^{n}\frac{i(i+1)}{2}=\frac{1}{2}\sum_{i=1}^{n}i^2+\sum_{i=1}^{n}i=\frac{1}{2}\left( \frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\right) =\frac{n(n+1)(n+2)}{6} 语句频度=i=1∑nj=1∑ik=1∑j=i=1∑nj=1∑ij=i=1∑n2i(i+1)=21i=1∑ni2+i=1∑ni=21(6n(n+1)(2n+1)+2n(n+1))=6n(n+1)(n+2)
例3:分析以下程序段的时间复杂度
i=1; //1
while(i<=n)
i=i*2; //2
2f(n)≤n,即f(n)≤log2n,取最大值f(n)=log2n
所以该程序段的时间复杂度T(n) =O(log2n)
有的情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同
例4:顺序查找,在数组a[i]中查找值等于e的元素,返回其所在位置。
for (i=0;i< n;i++)
if (a[i]==e) return i+1;
return 0;
最好情况:1次;最坏情况:n;平均时间复杂度为:O(n)
当n取得很大时,指数时间算法和多项式时间算法在所需时间上非常悬殊
时间复杂度T(n)按数量级递增顺序为:
渐进空间复杂度
空间复杂度;算法所需存储空间的度量,记作: S(n)=O(f(n))
其中n为问题的规模(或大小)
算法要占据的空间;算法本身要占据的空间,输入/输出,指令,常数,变量等;算法要使用的辅助空间
例5:将一维数组a中的n个数逆序存放到原数组中。
【算法1】
for(i=0;i<n/2;i++)
{ t=a[i];
a[i]=a[n-i-1];
a[n-i-1]=t;
}
S(n) = O(1) 原地工作
【算法2】
for(i=0;i<n;i++)
b[i]=a[n-i-1];
for(i=0;i<n;i++)
a[i]=b[i];
S(n) = O(n)
小结
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。