01算法分析与设计.ppt

1、、算法分析和设计、重庆市邮件和通信大学电脑学院多春QQ:407535048，课程要求，不需要笔记，课件可以复制什么。您可以请求退出教室。铃声真的响了，上课不要接电话，只有紧急情况才能推迟考试，需要推迟考试的学生必须在最后一节课前通知我。工作要求必须在指定日期之前提交，迟交的工作被拒绝，晚一天按平时成绩扣除10%。如果抄写发现工作有相同的副本和版本，所有相关学生这次的成绩都是0。参考网站：http:/OCW . MIT . edu/courses/electrical-engineering-and-computer-science/6 index . htm，审查方法

2、，审查方法教材及参考书，教材：电脑算法基础第三板块女商船，崔菊花，秋澄/2006(课程)考曼(Cormen，T.H)等板金耳等翻译/2006年09月/机械工业出版社，课程简介，简介目标：了解电脑算法分析基本方法和一般算法设计方法教育逻辑思维使用一般算法设计方法软件开发实际问题解决课程：离散数学、数据结构、高级编程语言。9，对算法分析计算机程序性能和资源使用的理论研究比性能更重要的是什么？modularity(模块化)correctness(准确性)maintainability(可维护性)functionality(功能性)robustness(坚固/坚固)USS、一般处理器和随机内存作为计算

3、模型命令一次执行一个，同时操作的命令不作为原子操作执行。指令包括算术操作、逻辑操作、数据移动和控制操作指令。RAM容量必须足够大。在随机存储模型下，3360计算基本任务数，估计算法分析-算法需求的资源，L1.4研究算法和性能的原因，算法帮助我们理解可扩展性。一般使用性能来划分可行性和不可行性之间的界限。计算数学提供了描述节目行为的语言，性能是计算领域的流通货币(currency)。降低节目性能可以获得更多计算资源。，速度总是很有趣(Speed is fun！)、RAM model (RAM模型)、RAM模型上的算法分析所需：Combinatorics组合Probability theory概率

4、Algebra代数the ability to identify the most significant terrs(重新排列)示例： input : 8 2 4 9 3 6 output : 2 3 4 6 8 9，l 1.6，插入排序，a1.N，insertion-sortion N)for j2to N do key a j，I J1 while i0 and ai key do ai 1 ai i1 ai 1=key，“伪代码”，插入排序，insertion sortion.N，insertion N) for j2to n do key a j，I J1 while i0 and

5、ai key do ai 1 ai I i1 ai 1=key，“伪代码”，sorted，I，j，key 2 8 4、4 4 8、9 9 9、3 3 3、6 6 6、example of insertion sort、8 2 2 6、example of insertion sort 8 2 2 2 2 2 2，2，2 8 4 3，4 4 8 4，9 9 9 8，9 9 9 8 6，影响运行时时间的主要因素，输入大小(Numbers of inputs)输入组件，某些算法(但不是全部)对于长度相同的徐璐其他输入队列具有不同的运行时间。 一般来说，运行时间是影响输入的函数、运行时间的主要因素，有

6、时运行时间是算法采用的数据结构，一般我们采取运行时间上限。因为每个人都喜欢有保障的工作。、输入大小(Input size)、输入大小依赖关系研究问题与很多计算问题、输入大小是输入项目数(例如排序和计算傅里叶变换(DFT)、输入数组中的元素数N是输入大小(Input size)与其他问题(例如，两个整数相乘、输入数组中的数N)的关系执行时间(运行时)，执行时间是执行的基本操作数(步骤数)。默认操作假定每一行代码所用的时间是常量Ci，与特定机器无关。但是，每一行代码的时间可能不同。运行时间(Worst-case :(usually)-t(n)=maximum time of algorithm o

7、n any input of size n .最差运行时，size给定的所有输入averithm平均运行时间(size给定时间)Best-case :(bogus)-cheat with a slow algorithm that works fast on size input最差情况是上限。在TJ :第5行上，while循环中的测试次数，CostTimes，C1，N，C2，N-1，0，N-1，C4，N-1，C5 Insertion-sortion此时，假定TJ=1，-运行时间为数组长度N的线性函数，插入排序算法分析，最差情况下，数组为逆序tj=j，最差情况下，运行时间为数组长度N的二次函数

8、，插入排序所有数据的发生概率相同，则tj=(j 1)/2，运行时间为数组长度N的二次函数，增长率but also the abstract costs Ci(using the constants a、b、and c是Ci的函数)、运行时增长率(运行时表达式中的最高计数项(例如an2)和忽略第一项的系数(例如，符号，符号，数学：(g(n)=f(n): there exist positive constants C1，C2，and n0 such that 0c1g(n iin，渐进分析是组织思想的有用工具。渐进式分析n牙齿如果足够大，则可以比n1 N2)算法牙齿(n3)算法优秀，而且不能忽略渐进式算法子部分。归并排序，合并两个已排序的表，两个数组A1q，Bq 1r牙齿已排序，因此可以设置为升序下的算法例外：如果两个数组的大小数为Floor(n/2)和Ceiling(n/2)，则需要比较的次数为Floor(n/2)，2020/8/11，2020/8/11，基本思路，3个阵列Apq、Aq 1r、Bpr 3指针：s、t、k s初始化时每个Aq 1 k初始化时每个Bp比较As、At 91合并两个已排序的阵列20 12