方案1内层循环超过100万次，在某机器上运行了50分钟；方案2的if语句执行525次，运行了2秒钟，相差1500倍。
5.算法分析举例
（1）常量阶：时间复杂度为O(1)
++x;
s=0;
语句频度为1，时间复杂度为O(1)。
for(j=1;j<=10000;++j)
{++x; s+=x;}
语句频度为10000，时间复杂度为O(1)。
教学重点与难点：
教 学 内 容
备 注
教案（末页）
复习思考题：
推荐阅读书目：
数据结构与算法设计课程教案（续页）
授课时间
第周
授课方式
（请打√）
□讲授 □上机 □实验/训 □其它
课时
安排
授课题目（章节或单位课时）：
教学目的与要求（分了解、熟悉、掌握三个层次）：
教学重点与难点：
教 学 内 容
备 注
教案（末页）
printf(“i=%d，j=%d，k=%d”,i,j,k)
方案2：
for( i = 0; i < =20; i++)
for( j = 0; j < =34-i; j++)
if(3*i+2*j+(100-i-j) *0.5==100)
printf(“i=%d,j=%d,k=%d”,i,j, 100-i-j);
s=0;
for(j=1;j<=n;j*=2)
for(k=1;k<=n;++k)
s++;
时间复杂度为O(nlogn)
（5）平方阶：时间复杂度为O(logn)
s=0;
for(j=1;j<=n;++j)
for(k=1;k<=n;++k)
s++;
语句频度为n2，所以时间复杂度为O(n2)。
s=0;
for(j=1; j<=n; j++)
教案（末页）
复习思考题：
推荐阅读书目：
数据结构与算法设计课程教案（续页）
授课时间
第周
授课方式
（请打√）
□讲授 □上机 □实验/训 □其它
课时
安排
授课题目（章节或单位课时）：
教学目的与要求（分了解、熟悉、掌握三个层次）：
教学重点与难点：
教 学 内 容
备 注
教案（末页）
复习思考题：
推荐阅读书目：
数据结构与算法设计课程教案（续页）
4.从“百钱买百鸡”(“一百元钱买一百支笔”)的算法例子说明选择算法的重要性：
方案1：
for( i = 0; i < =100; i++)
for( j = 0; j < =100; j++)
for( k= 0; k< =100; k++)
if(i+j+k==100 &&3*i+2*j+0.5*k==100)
备 注
1.从后序课（数据库、操作系统、编译原理、人工智能）的需要和考研两方面介绍数据结构课程的重要性。
2.通过三个例子讲解数据结构研究的内容。
3.介绍基本概念：数据的三个层次，数据结构的三个要素，数据结构的分类，四种存储结构，抽象数据类型，算法，算法的五个特性，对算法设计的要求，算法描述和算法分析，时间复杂度和空间复杂度。
（2）对数阶：时间复杂度为O(logn)
s=0;
for(j=1; j<=n; j*=2)
s++;
语句频度为logn，所以时间复杂度为O(logn)。
（3）线性阶：时间复杂度为O(logn)
S=0;
for(j=1;j<=n;++j)
s++;
语句频度为n，所以时间复杂度为O(n)。
（4）时间复杂度为O(nlogn)
复习思考题：
推荐阅读书目：
数据结构与算法设计课程教案（续页）
授课时间
第周
授课方式
（请打√）
□讲授 □上机 □实验/训 □其它
课时
安排
授课题目（章节或单位课时）：
教学目的与要求（分了解、熟悉、掌握三个层次）：
for( k= 0; k< n; j++) // n2(n+1)
c[i][j] = c[i][j]+a[i][k]* b[k][j]; // n3
}
说明：各语句行后的数字是该语句重复执行的次数;
本算法时间复杂度为O (n3)
6.空间复杂度
算法原地（就地）工作：
若所用额外存储空间相对于输入数据量来说是常数，则称此算法为原地（就地）工作。
for(k=1;k<=j;++k)
s++;
语句频度为n(n+1)/2，所以时间复杂度仍为O(n2)。
（6）立方阶：时间复杂度为O(n3)
例：矩阵乘法：n x n
for( i = 0; i < n; i++) //(n+1)
for( j = 0; j < n; j++) //n(n+1)
{ c[i][j] = 0；//n2
授课时间
第周
授课方式
（请打√）
□讲授 □上机 □实验/训 □其它
课时
安排
授课题目（章节或单位课时）：
教学目的与要求（分了解、熟悉、掌握三个层次）：
教学重点与难点：
教 学 内 容
备 注
教案（末页）
复习思考题：
推荐阅读书目：
数据结构与算法设计课程教案（续页）
授课时间
第周
授课方式
（请打√）
□讲授 □上机 □实验/训 □其它
福 州 理 工 学 院
教案
课 程 名 称
数据结构与算法设计
系 （部）
信息工程系
教 研 室
计算机
授 课 教 师
黄取治
职 称
讲师
附件2：
教 案（首页）
课程名称
数据结构与算法设计
学分
总计 ：学时
讲授：学时
上机：学时
实验/训： 学时
其它： 学时
类 别
（请打√）
□公共课□公共选修课□专业基础课□专业必修课□专业方向选修课□实验实训课（仅限本科）
课时
安排
授课题目（章节或单位课时）：
教学目的与要求（分了解、熟悉、掌握三个层次）：
教学重点与难点：
教 学 内 容
备 注
教案（末页）
复习思考题：
推荐阅读书目：
数据结构与算法设计课程教案（续页）
授课时间
第周
授课方式
（请打√）
□讲授 □上机 □实验/训 □其它
课时
安排
授课题目（章节或单位课时）：
教学目的与要求（分了解、熟悉、掌握三个层次）：
□公共课□公共选修课□专业基础课□专业必修课□专业选修课□实验实训课（仅限高职）
授课对象（请打√）
□本科 □高职 □其他
使用教材
参考资料
（注明书名、主编、出版社、出版时间）
教学方法教学手段
考核方式
学生创新精神与实践能力的培养方法
数据结构与算法设计课ห้องสมุดไป่ตู้教案（续页）
授课时间
第 1周
授课方式
（请打√）
□讲授 □上机 □实验/训 □其它
课时
安排
授课题目（章节或单位课时）：
第一章 绪论
教学目的与要求（分了解、熟悉、掌握三个层次）：
1.了解数据结构课程的重要性和课程的基本要求，以及本课程涵盖的内容；
2.掌握数据结构的基本概念；
3.理解算法描述和简单的算法分析。
教学重点与难点：
1.重点是数据结构的基本概念
2.难点是时间复杂度分析
教 学 内 容