计算机问题求解一论题2-02 -算法的效率 2022年03月02日
计算机问题求解 – 论题2-02 - 算法的效率 2022年03月02日
问题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： 算法分析”主要是干什么？ 优化一个算法： 首先要完成算法“性能”的度量，依此判定算法的优劣； 度量一个算法的性能，首先要给出描述算法性能的模型 算法的渐进时间复杂度模型
优化一个算法： 首先要完成算法“性能”的度量，依此判定算法的优劣； 度量一个算法的性能，首先要给出描述算法性能的模型 算法的渐进时间复杂度模型