天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 2 ALGORITHM ANALYSIS

数据结构 Data structures 主讲人:李晓红
数据结构 Data Structures 主讲人: 李晓红

口教材( Text Book) 数据结构与算法分析 晋言描述 Data structures and Algorithm Analysis in C (2nd Edition) Mark allen weiss
教材 (Text Book) Data Structures and Algorithm Analysis in C (2nd Edition) Mark Allen Weiss

口参考书目( Reference) 《数据结构》(C语言版)严蔚敏等编著,清华大学出版社 《数据结构》(用面向对象方法与C++描迷) 殷人昆等编著,清华大学出版社
参考书目 (Reference) «数据结构 »(C语言版)严蔚敏等编著,清华大学出版社 «数据结构 »(用面向对象方法与C++描述) 殷人昆等编著,清华大学出版社

课程评分方法 Grading Policies ■圜 a Lecture Grade(80)=Final Exam(80) Laboratory grade(15)=∑Lab(i)×015 B Other Grade(5)=Attendance Homework
课程评分方法 (Grading Policies) Lecture Grade (80) = Final Exam (80) Laboratory Grade (15) = 0.15 5 1 = 5 i 1 Lab ( i ) Other Grade(5)=Attendance + Homework

作业&出勤 ◆布置作业的下周( Tuesday)交,迟交不交 扣分。做则有分,不计对错,一周后公布 参考答案。 ◆必须按照软件学院规范做作业,否则不计 分,13作业未交者不能参加期末考试。 ◆点名三次不到者不能参加期末考试
作业&出勤 ◆ 布置作业的下周(Tuesday)交,迟交不交 扣分。做则有分,不计对错, 一周后公布 参考答案。 ◆ 必须按照软件学院规范做作业,否则不计 分,1/3作业未交者不能参加期末考试。 ◆ 点名三次不到者不能参加期末考试

实验 Laboratory projects 共5次;迟交罚扣为10%/day;抄袭者0分 罔3人一组,各组自行分工(例如:按功能模块、按开 发过程等),各自工作量应相当,试验报告中必须写 明各自工作量 A通过e-mai提交,请在邮件标题写明班级学号及试验 I,并在文档末尾写明分工 @助教( Teaching assistant): e丁刚刚( dinggang330@163c0m) 李旭(lixugoldenfield@yahoo.com.cn)
实验 (Laboratory Projects) 共 5 次;迟交罚扣为 10% /day;抄袭者0分; 3人一组,各组自行分工(例如:按功能模块、按开 发过程等),各自工作量应相当,试验报告中必须写 明各自工作量; 通过e-mail提交,请在邮件标题写明班级学号及试验 ID,并在文档末尾写明分工。 助教(Teaching Assistant): ☺ 丁刚刚(dinggang330@163.com) ☺ 李旭 ( lixugoldenfield@yahoo.com.cn )

CHAPTER 2 ALGORITHM ANALYSIS Definition) An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria (1)Input There are zero or more quantities that are externally supplied. (2)Output At least one quantity is produced. (3)Definiteness Each instruction is clear and unambiguous. (4)Finiteness If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after finite number of steps. (5) Effectiveness Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. It is not enough that each operation be definite as in (3); it also must be feasible
CHAPTER 2 ALGORITHM ANALYSIS 【Definition】An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria: (1) Input There are zero or more quantities that are externally supplied. (2) Output At least one quantity is produced. (3) Definiteness Each instruction is clear and unambiguous. (4) Finiteness If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after finite number of steps. (5) Effectiveness Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. It is not enough that each operation be definite as in(3); it also must be feasible

Note: A program is written in some programming language, and does not have to be finite(e.g. an operation system). An algorithm can be described by human languages, flow charts, some programming languages, or pseudo code I Example] Selection Sort: Sort a set of n> 1 integers in increasing order. From those integers that are currently unsorted, find the smallest and place it next in the sorted list. for (i=0; i<n; i++)t Examine list[i to list[n-1]and suppose that the smallest integer is at list[min]; Interchange list[ and list(min]; Sort= Find the smallest integer Interchange it with list[i
Note: A program is written in some programming language, and does not have to be finite (e.g. an operation system). An algorithm can be described by human languages, flow charts, some programming languages, or pseudocode. 〖Example〗 Selection Sort: Sort a set of n 1 integers in increasing order. From those integers that are currently unsorted, find the smallest and place it next in the sorted list. for ( i = 0; i < n; i++) { Examine list[i] to list[n−1] and suppose that the smallest integer is at list[min]; Interchange list[i] and list[min]; } Sort = Find the smallest integer + Interchange it with list[i]

81 What to Analyze Machine compiler-dependent run times Time space complexities machine compiler independent ° Assumptions: O instructions are executed sequentially 2 each instruction is simple, and takes exactly one time unit 3 integer size is fixed and we have infinite memory Typically the following two functions are analyzed: Tavo(n& TworstN--the average and worst case time complexities, respectively, as functions ofinput size N
§1 What to Analyze ➢ Machine & compiler-dependent run times. ➢ Time & space complexities : machine & compilerindependent. • Assumptions: instructions are executed sequentially each instruction is simple, and takes exactly one time unit integer size is fixed and we have infinite memory • Typically the following two functions are analyzed: Tavg(N) & Tworst(N) -- the average and worst case time complexities, respectively, as functions of input size N

[Example] Matrix addition void add (int all[ MAX SIze, int b][ MAX SIzE1, int CLI[ MAX SIZE, int rows, int cols for(i=0; i< rows; i++)/*rows+1*/ for(j=0; j< cols; j++)/*rows(cols+1)*/ c[i]j]=a[i[j]+bi]j]; /*rows. cols * T(rows, cols )=2 rows cols rows+ 1
〖Example〗 Matrix addition void add ( int a[ ][ MAX_SIZE ], int b[ ][ MAX_SIZE ], int c[ ][ MAX_SIZE ], int rows, int cols ) { int i, j ; for ( i = 0; i < rows; i++ ) for ( j = 0; j < cols; j++ ) c[ i ][ j ] = a[ i ][ j ] + b[ i ][ j ]; } /* rows + 1 */ /* rows(cols+1) */ /* rows cols */ T(rows, cols ) = 2 rows cols + 2rows + 1
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 8 THE DISJOINT SET ADT.ppt
- 华中师范大学计算机科学系:《数据结构》第6章 二叉树和树.ppt
- 华中师范大学计算机科学系:《数据结构》第2章 线性表.ppt
- 华中师范大学计算机科学系:《数据结构》第8章 查找表.ppt
- 华中师范大学计算机科学系:《数据结构》第7章 图和广义表.ppt
- 华中师范大学计算机科学系:《数据结构》第5章 串和数组.ppt
- 华中师范大学计算机科学系:《数据结构》第4章 栈与队列.ppt
- 华中师范大学计算机科学系:《数据结构》第3章 排序.ppt
- 华中师范大学计算机科学系:《数据结构》第1章 绪论(王敬华).ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)实验一.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第四章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第六章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第二章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第三章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)三元组表示的稀疏矩阵加法.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第四章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第六章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter3 Lists.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter4 Stacks Queues.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter5 trees.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter6 Graph Algorithms.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter7 Search.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter8 Sorting.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter9 String.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验二.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)二叉树试验三.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验一.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验四.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验模板.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验五.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)复习2007级.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)2004级计算机B卷.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第九章 排序.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第1章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第2章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第3章 栈和队列.ppt