算法设计技巧与分析算法基本概念之算法复杂度概要PPT课件.ppt

算法设计技巧与分析AlgorithmsDesignTechniquesandAnalysis 南方医科大学医工学院信息技术系 2019年12月29日 1 第1章算法分析基本概念 2019年12月29日 2 Content 算法与程序简单的算法实例计算复杂性时间复杂性空间复杂性分析计算方法 Bme SMU 12 3 算法的复杂性分为 设计算法追求的目标选用算法的准则 时间复杂性需要的时间资源的量空间复杂性需要的空间资源的量 设计出复杂性尽可能低的算法 选择已有算法中复杂性最低者 不是所有能计算的都有价值 不是所有有价值的都能被计算 阿尔伯特 爱因斯坦 AlgorithmComplexity Bme SMU 12 4 TimeComplexity 1估计算法运行的时间范围 2估算随着输入的增长 运算时间的增长率 Bme SMU 12 5 AsymptoticRunTime 令算法的输入为n 若算法的运行时间f n 为n的m阶函数 则称f n 是m阶的 一旦去除了表示算法运行时间的函数中的低阶项和首项常数 就称我们是在度量算法的渐进运行时间 分析算法的复杂性的目的 比较求解同一问题的两个不同算法的效率 而当要比较的两个算法的渐进复杂性的阶不相同时 只要能确定出各自的阶就可以判定哪一个算法的效率高 Bme SMU 12 6 Figure1 5 Bme SMU 12 7 Mark O 运行时间的上界 在运行时间的一个常数因子内提供一个下界 算法的精确阶 说明两个函数属于不同的复杂性类 Bme SMU 12 8 SymbolO 定义1 2令f n 和g n 是从自然数集到非负实数集的两个函数 如果存在一个自然数n0和一个常数c 0 使得 对于所有的n n0 有f n cg n 则称f n 为O g n 记作 f n O g n Bme SMU 12 9 UltimateForm 如果存在 那么 蕴含着 Bme SMU 12 10 Symbol 定义1 3令f n 和g n 是从自然数集到非负实数集的两个函数 如果存在一个自然数n0和一个常数c 0 使得 对于所有的n n0 有f n cg n 则称f n 为 g n 记作 f n g n Bme SMU 12 11 UltimateForm 如果存在 那么 蕴含着 推论 f n 是 g n 当且仅当g n 是O f n Bme SMU 12 12 Symbol 定义1 4令f n 和g n 是从自然数集到非负实数集的两个函数 如果存在一个自然数n0和两个正常数c1和c2 使得 对于所有的n n0 有c1g n f n c2g n 则称f n 为 g n 记作 f n g n Bme SMU 12 13 UltimateForm 如果存在 那么 蕴含着 推论 f n 是 g n 当且仅当f n O g n 并且f n g n Bme SMU 12 14 Figure Bme SMU 12 16 Example1 5 设 由于对 因此有 由于对 因此有 此外 由于对 因此有 极限方式 由于 因此有和 Bme SMU 12 17 Example1 12 考虑级数 显然 又 同理得到 Bme SMU 12 18 算法1 7BRUTE FORCEPRIMALITYTEST 输入 正整数n 2 输出 如果n是素数则输出为真 否则为假 1 s 2 forj 2tos 3 ifj划分nthenreturnfalse 4 endfor 5 returntrue Bme SMU 12 19 Analysis 假定 可以在O 1 时间内计算出来 对任意的素数n 循环执行次数为 1 则算法是O 考察对象1 算法中循环的执行次数 对任意的n值 如n为偶数 循环执行次数为1 则算法是 1 推论 蛮力算法既不是 也不是 1 Bme SMU 12 20 ComplexityTypes 令R为复杂性函数集合上由下列条件定义的关系 fRg当且仅当f n g n 由这个关系导出的等价类称为复杂性类 例如 所有的二次多项式属于同一个复杂性类n2 问题 如何区分属于不同复杂性类的两个函数 Bme SMU 12 21 定义1 5令f n 和g n 是从自然数集到非负实数集的两个函数 如果对每一个常数c 0 存在一个正整数n0 使得 对于所有的n n0 都有f n cg n 则称f n 是o g n 的 即f n o g n 记作 f n g n Symbol Bme SMU 12 22 UltimateForm 如果存在 那么 蕴含着 推论 f n o g n 当且仅当f n O g n 并且g n O f n Bme SMU 12 23 ComplexityTypesRelation Bme SMU 12 24 SpaceComplexity 1 多用户系统中运行时 需指明分配给该程序的内存大小 2 想提前知道是否有足够可用的内存来运行该程序 3 一个问题可能有若干个内存需求各不相同的解决方案 从中择取 1估算一个程序所能解决的问题的最大规模 Bme SMU 12 25 SpaceUsed 算法使用的空间 为了求解问题的实例而执行的计算步骤所需要的内存空间数目 不包括分配用来存储输入的空间 写入每一个内存空间都至少需要一定的时间 推论 令T n 和S n 分别代表算法的时间复杂性和空间复杂性 则有S n O T n Bme SMU 12 26 Example1 171 181 19 考虑 算法SELECTIONSORT和INSERTIONSORT的空间复杂性 Bme SMU 12 27 Tradeoff 许多问题需要在时间与空间之间权衡 迄今为止讨论过的大多数算法中 增加空间并没有导致明显的速度加快 相反却往往