南京大学：《计算机问题求解》课程教学资源（课件讲稿）算法的效率

计算机问题求解一论题2-03 ·算法的效率 2016年03月09日

计算机问题求解 – 论题2-03 - 算法的效率 2016年03月09日

问题1：你如何理解这里的“优化”？算 法级？程序级？ (2)for from I to N do: (2.1)L()←-L()×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 do something with A[l,J] ·程序2： for Jfrom 1 to N do ■for from1 to M do do something with A[l,]

问题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]

间题3： 你能说出如何用Linear Search算法艘索一个未排序 的序列吗？书申给出的优化方法是什么？这种优化 是量上的优化还是质上的优化？？ 给定一个算法，什么样的优 化算是质上的优化？

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

问题3： “算法分析”主要是干什么？

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

一个插入排序方法

插入法： 在“插入每张 牌前，手上的 % 牌都是已经排 4 10 品 好序的” 云 品 坐

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

范例 总是已经排好序的片段 123 456 123456 1 23145 6 (a) 524613 (b) 254613 (c) 245613 总是已经排好序的片段 123456 123 456 12 3456 (d) 245 6 1 3 (e) 12 4 563 (f) 12 3456

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

伪代码 提请注意：你应 INSERTION-SORT(A) 该会证明这个算 1 for j=2 to A.length 法的正确性！ 2 key =Alj] 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

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

用哪些数值来标定算法的性能？ ■时间性能（时间复杂度） 口算法在给定一个输入的情况下，要执行多少条指令 没错，数数字！

用哪些数值来标定算法的性能？  时间性能（时间复杂度）  算法在给定一个输入的情况下，要执行多少条指令 没错，数数字！