计算机问题求解一论题2-02 -算法的效率 2018年03月14日
计算机问题求解 – 论题2-02 - 算法的效率 2018年03月14日
问题1:你如何理解这里的“优化”?算 法级?程序级? (2)for from I to N do: (2.1)L(I)←-L(I)×100/MAX (1)compute the maximum score in MAX: (2)FACTOR←-100/MAX: (3)for from 1 to N do: (3.1)L(I)←-L(I)×FACTOR
问题1:你如何理解这里的“优化”?算 法级?程序级?
问题2:以下两个程序,在执行效率上有什么 区别? ■对一个二维数组A[m,n进行遍历: ■程序1: for /from 1 to M do for Jfrom 1 to N do A[1,1]A1,2]A1,3JA1,4A1,5]A1,6jA1,7] do something with A[l,J] A2,1]A2,21A2,3]A2,4]A25]A2,6]A2,7刀… ■程序2: for Jfrom 1 to N do ■for/from1 to M do do something with A[l,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 1: Input:A sequence of n numbers (a1,a2.....an). Output:A permutation (reordering)(a.a2.....a of the input sequence such that a≤a2≤…≤an
一个插入排序方法
插入法: 在“插入每张 牌前,手上的 % 牌都是已经排 10 品 好序的” 品 必
插入法: 在“插入每张 牌前,手上的 牌都是已经排 好序的
范例 总是已经排好序的片段 123456 123456 1 23145 6 (a) 524613 (b) 254613 (c) 245613 总是已经排好序的片段 123456 123456 123456 (d) 245613 (e) 2 4 563 (f) 123456
范例 总是已经排好序的片段 总是已经排好序的片段
伪代码 提请注意:你应 INSERTION-SORT(A) 该会证明这个算 1 for j=2 to A.length 法的正确性! 2 key =A[j] 3 /Insert A[j]into the sorted sequence A[1..j-1]. 4 i=j-1 5 while i >0 and A[i]>key 6 A[i+1]=A[] 7 i=i-1 8 Ali 1]key
伪代码 提请注意:你应 该会证明这个算 法的正确性!
算法的性能度量模型 算法性能涉及 口空间性能(空间复杂度) ■算法在给定合法输入的情况下,要消耗多少“临时”存储空间 口局部变量、过程调用的堆栈空间等 ■特定场合中较为关注 口时间性能(时间复杂度) ■算法在给定合法输入的情况下,需要执行多少时间 ■重点关注内容! ·算法的时间复杂度模型 口执行指令条数的统计模型:数数字!
算法的性能度量模型 ◼ 算法性能涉及 ❑ 空间性能(空间复杂度) ◼ 算法在给定合法输入的情况下,要消耗多少“临时”存储空间 ❑ 局部变量、过程调用的堆栈空间等 ◼ 特定场合中较为关注 ❑ 时间性能(时间复杂度) ◼ 算法在给定合法输入的情况下,需要执行多少时间 ◼ 重点关注内容! ◼ 算法的时间复杂度模型 ❑ 执行指令条数的统计模型:数数字!