第一讲 基本概念
1.1 什么是数据结构
例1:如何在书架上摆放图书
解决问题方法的效率,跟数据的组织方式有关
例2:实现一个函数PrinN,使得传入一个正整数为N的参数后,能顺序打印从1到N的全部正整数
方法1:循环实现
方法2:递归实现
递归对空间的占用花销很大,以至于计算机内存有限无法拥有足够的空间运行该程序
1
2
3
4
5
6
7
8
9void PrintN(int n)
{
if(n)
{
PrintN(n-1);
printf("%d\n",N);
}
return ;
}解决问题方法的效率,跟空间的利用效率有关
例3 : 写程序给定多项式在给定点x处的值
$f(x)=a0+a_1x+….+a{n-1}x^{n-1}+a_nx^n$
$f(x)=a0+x(a_1+x(…(a{n-1}+xa_n)…))$
1
2
3
4
5
6
7
8double f(int n,double a[],double x)
{
int i;
double p=a[n];
//for(i=1;i<=n;i++) p+=(a[i]*pow(x,i));
//for(i=n;i>0;i--) p=a[i-1]+x*p;
return p;
}计时函数模板:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
clock_t start,stop;
double duration;
int main()
{
start = clock();
MyFunction();
stop = clock();
duratio= ((double)(stop-start))/CLK_TCK;
return 0;
}解决方法的效率与算法的方法有关
例4:”矩阵”的抽象数据类型定义
总结
抽象数据类型(Abstract Data Type)
1.2 什么是算法
定义
例1:选择排序算法的伪代码描述
算法优劣判断指标
例2:递归函数的空间复杂度
- 例3:循环函数的时间复杂度
复杂度的渐进表示法
常用函数复杂度:
复杂度常用分析:
1.3 应用实例:最大子列的问题
算法1&2:复杂度(N^2,N^3)
循环嵌套
算法3:复杂度(NlogN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44int Max3(int a,int b,int c)
{
return a>b?a>c?a:c:b>c?b:c;
}
int DivideAndConquer(int list[],int left,int right)
{
int RightBoderSum,LeftBoderSum;
int MaxRightBoderSum,MaxLeftBoderSum;
int MaxleftSum,MaxRightSum;
int center,i;
if(left==right)
{
if(list[left]>0) return list[left];
else return 0;
}
center=(left+right)/2;
MaxleftSum=DivideAndConquer(list,left,center);
MaxRightSum=DivideAndConquer(list,center+1,right);
MaxRightBoderSum=0;RightBoderSum=0;
for(i=center+1;i<=right;i++)
{
RightBoderSum+=list[i];
if(RightBoderSum>MaxRightBoderSum)
{
MaxRightBoderSum=RightBoderSum;
}
}
LeftBoderSum=0;MaxLeftBoderSum=0;
for(i=center;i>=left;i--)
{
LeftBoderSum+=list[i];
if(LeftBoderSum>MaxLeftBoderSum)
{
MaxLeftBoderSum=LeftBoderSum;
}
}
return Max3(MaxleftSum,MaxRightSum,MaxLeftBoderSum+MaxRightBoderSum);
}
算法4:复杂度(N)
作业
二分法
1 | Position BinarySearch( List L, ElementType X ) |
Maximum Subsequence Sum
1 |
|