一算法概念与数学基础 一算法概念与数学基础 定义：输入-》算法->输出 可计算问题[computational problem]:对输入输出要求的说明 问题的实例[instance]:某个求解需要的具体输入 (排序算法中，粉入数组、输出排好的数组是问题，而一个具体的乱序数组则是实例) 正确性：要求对任何输入能正确给出输出（随机算法可能一定程度违反） 学习算法的意义：确定解决方式的正确性、选择容易实现的算法，比较时空复杂度 *算法效率比电脑速度更重要 51.1算法简介与分析 伪代码书写：注重表达清楚，不关注语言细节 约定：缩进表示块结构、循环结构与C类似解释、/代表注释、变量如无特殊说明表示局部变量 举例：插入排序（就地[in-place]排序，需要的额外空间为O(1),即常量） def INTERSECTION-SORT(A): for (j<-2)to length(A) key <-A[j] 1-j-1 while (i>0 and A[i]key) A[i+1]<-A[i] 1父-1-1 A[i+1]<-key *如何证明正确性？ 可选方法：循环不变式[loop1 nvariant],保证初始化、选代时均为真（类似归纳），循环终止时能提 供有用性质（局限性：只能用于判断循环，无法判断分支等） 插入排序中不变式：A[1.j-1]在循环后有序 ◆现实：理论证明几乎无法做到，通过大量测试假定正确 幸*关于正确性[correctness]:正确性指算法在程序规范下被认定为正确的判定，其中功能[functi- conal】正确针对输入输出的行为，一般分为部分[partial】正确与完全[total】正确，前者指输出 结果时结果正确，后者还额外要求必须能输出结果。 算法分析 含义：预测算法需要的资源，通常关心时间[computational time]与内存空间[memory,偶尔会涉 及通信带宽、硬件使用等 为了统一评价，需要使用统一、简洁的计算模型 *对串行算法一般使用RAM模型[Random-access machine],并行则为PRAM模型[Parallel RAM] RAM模型特点： 1.指令一条条执行（不存在并发） 一 算法概念与数学基础 2 一 算法概念与数学基础 定义：输入‐> 算法‐> 输出 可计算问题 [computational problem]：对输入输出要求的说明 问题的实例 [instance]：某个求解需要的具体输入 (排序算法中，输入数组、输出排好的数组是问题，而一个具体的乱序数组则是实例) 正确性：要求对任何输入能正确给出输出 (随机算法可能一定程度违反) 学习算法的意义：确定解决方式的正确性、选择容易实现的算法，比较时空复杂度 *算法效率比电脑速度更重要 §1.1 算法简介与分析 伪代码书写：注重表达清楚，不关注语言细节 约定：缩进表示块结构、循环结构与 C 类似解释、//代表注释、变量如无特殊说明表示局部变量 举例：插入排序 (就地 [in‐place] 排序，需要的额外空间为 O(1)，即常量) def INTERSECTION‐SORT(A): for (j <‐ 2) to length(A) key <‐ A[j] i <‐ j‐1 while (i > 0 and A[i] > key) A[i+1] <‐ A[i] i <‐ i ‐ 1 A[i+1] <‐ key *如何证明正确性？ 可选方法：循环不变式 [loop invariant]，保证初始化、迭代时均为真 (类似归纳)，循环终止时能提 供有用性质 (局限性：只能用于判断循环，无法判断分支等) 插入排序中不变式：A[1..j‐1] 在循环后有序 *现实：理论证明几乎无法做到，通过大量测试假定正确 **关于正确性 [correctness]：正确性指算法在程序规范下被认定为正确的判定，其中功能 [functi‐ conal] 正确针对输入输出的行为，一般分为部分 [partial] 正确与完全 [total] 正确，前者指输出 结果时结果正确，后者还额外要求必须能输出结果。 算法分析 含义：预测算法需要的资源，通常关心时间 [computational time] 与内存空间 [memory]，偶尔会涉 及通信带宽、硬件使用等 为了统一评价，需要使用统一、简洁的计算模型 *对串行算法一般使用 RAM 模型 [Random‐access machine]，并行则为 PRAM 模型 [Parallel RAM] RAM 模型特点： 1. 指令一条条执行 (不存在并发)