计算机问题求解（PPT讲稿）算法在计算机科学中的地位（算法的效率）

计算机问题求解-论题22 算法的效率 2018年03月14日

计算机问题求解 – 论题2-02 - 算法的效率 2018年03月14日

问题1:你如何理解这里的“优化”?算 法级?程序级? (2)for I from I to n do (2)L(1)←L(1)×10MAX ( compute the maximum score in MAX (2) FACTOR←100MAX (3)for I from I to n do (3.1)L(1)←L(1)×FACT0R

问题1：你如何理解这里的“优化”？算 法级？程序级？

问题2:以下两个程序,在执行效率上有什么 区别? 对一个二维数组Am:进行遍历 n程序1: a for from 1 to m do for j from 1 to n do A[1,12403]A14A1,5A1,6A17| a do something with Al,J] A[2 1 A(2.2)(2.3.4 A(2.5)A2.6)(2. 7 n程序2: n for j from 1 to n do for from 1 to m do a do something with A[, J

问题2：以下两个程序，在执行效率上有什么 区别？ ◼ 对一个二维数组A[m,n]进行遍历： ◼ 程序1： ❑ for I from 1 to M do ◼ for J from 1 to N do ❑ do something with A[I,J] ◼ 程序2： ❑ for J from 1 to N do ◼ for I from 1 to M do ❑ do something with A[I,J] A[1,1] A[1,2] A[1,3] A[1,4] A[1,5] A[1,6] A[1,7] … A[2,1] A[2,2] A[2,3] A[2,4] A[2,5] A[2,6] A[2,7] … …

问题3: 你能说岀如何用 Linear Search算法搜索一个未排序 的序列吗?书中给昌的优化方法是什么?这种优化 是量上的优化还是厥上的优化?? 给定一个算法,什么样的优 化算是质上的优化?

给定一个算法，什么样的优 化算是质上的优化？

问题4 “算法分析”主要是干什么? 优化一个算法: 首先要完成算法“性能”的度量,依此判定算法的优劣; 度量一个算法的性能,首先要给出描述算法性能的模型 算法的渐进时间复杂度模型

优化一个算法： 首先要完成算法“性能”的度量，依此判定算法的优劣； 度量一个算法的性能，首先要给出描述算法性能的模型 算法的渐进时间复杂度模型

个插入排序方法 Our first algorithm, insertion sort, solves the sorting problem introduced in Chap- ter l Input: A sequence of n numbers (a1, a2,..., an) Output: A permutation (reordering)(a'.d,,..., a" )of the input sequence such that a 1<

一个插入排序方法

插入法: 在“插入每张 牌前,手上的 牌都是已经排 好序的

插入法： 在“插入每张 牌前，手上的 牌都是已经排 好序的

范例 总是已绎排好序的片段 国b 总是已经排好序的片段

范例 总是已经排好序的片段 总是已经排好序的片段

伪代码 提请注意:你应 Ⅰ NSERTION-SORT(4) 该会证明这个算 I for j= 2 to A length 法的正确性! //Insert A[i into the sorted sequence A[..j-1 5 while i>0 and Ai> key Ali+1=Ai 8A1+1]=key

伪代码 提请注意：你应 该会证明这个算 法的正确性！

算法的性能度量模型 算法性能涉及 口空间性能(空间复杂度) ■算法在给定合法输入的情况下,要消耗多少“临时”存储空间 口局部变量、过程调用的堆栈空间等 ■特定场合中较为关注 口时间性能(时间复杂度) ■算法在给定合法输入的情况下,需要执行多少时间 重点关注内容! 算法的时间复杂度模型 口执行指令条数的统计模型:数数字!

算法的性能度量模型 ◼ 算法性能涉及 ❑ 空间性能（空间复杂度） ◼ 算法在给定合法输入的情况下，要消耗多少“临时”存储空间 ❑ 局部变量、过程调用的堆栈空间等 ◼ 特定场合中较为关注 ❑ 时间性能（时间复杂度） ◼ 算法在给定合法输入的情况下，需要执行多少时间 ◼ 重点关注内容！ ◼ 算法的时间复杂度模型 ❑ 执行指令条数的统计模型：数数字！