5-1 数据结构与算法效率 课件-2021-2022学年浙教版（2019）高中信息技术选修1

第五章 数据结构与算法 选修1《数据与数据结构》 5.1 数据结构与算法效率 学习目标 算法效率 算法效率 数据结构对算法效率的影响 算法效率 算法是解决某一特定类型问题的有限求解步骤。描述一个算法可以采用某一计算机语言，也可以才用自然语言和流程图等 ·算法的概念 ·算法的特征 有穷性 确定性 可行性 有0个或多个输入 有1个或多个输出 算法效率 算法效率 评价一个算法一般从4个方面进行：正确性、简单性、运行时间和占用空间。其中最主要的是算法的运行时间和占用空间。 ·算法的评价标准 ·时间复杂度 反映了算法执行所需要的时间 ·空间复杂度 反映了算法执行所需要占用的存储空间 ·算法效率 抽算法效率的高低可由算法复杂度来度量。 算法效率 算法效率 指令空间：存储经过编译之后的程序指令。指令有操作数和操作码构成。 数据空间：存储所有常量和所有变量值所需的空间。 环境栈空间：保存函数调用返回时恢复运行所需要的信息。 ·空间复杂度 所以一个程序所需要的空间可分为两部分： 固定部分：独立于实例特征，主要包括指令空间、简单变量以及定长复合变量占用的空间、常量占用的空间。 可变部分：主要包括复合变量所需空间、 动态分配的空间、递归栈所需要的空间。 复合变量所需的空间依赖于所解决的具体问题。 动态分配的空间和递归栈所需要的空间依赖于实例特征 注意：经过半个多世纪的发展，计算机的速度和存储容量都已经提升了好几个数量级。现在空间效率已经不是我们关注的重点。 算法效率 算法效率 一般将算法中语句的执行次数作为时间复杂度的度量标准。我们在分析时间复杂度的时候也只关注执行次数的增长次数及其常数倍。 语句总的执行次数T(n)是关于问题规模n的函数。 时间复杂度常用符号O()表示。 ·时间复杂度 算法效率 在分析算法的时间复杂度时，我们需要知道三个方面： ·输入规模 不管使用什么算法，输入规模越大，运行效率肯定会更长。 ·算法的平均效率、最差效率和最优效率 在输入最优情况