数据结构和算法课件 2算法和复杂度.ppt

1 4 1 6算法和复杂度 算法和复杂度 2 22 算法 是对特定问题求解步骤的一种描述 它是指令的有限序列 其中每一条指令表示一个或多个操作 一个算法通常具有五个重要特性 有穷性有穷步结束 确定性唯一执行路径 可行性可以通过基本运算实现 输入零个或多个输入 输出一个或多个输出 非数学有穷性 算法和算法复杂度 算法和复杂度 3 22 算法和数据结构是两个不可分割的统一体 程序 数据结构 算法 数据结构通过算法实现操作 算法根据数据结构设计程序 算法和复杂度 4 22 算法设计的要求 正确性正确反映需求 通过测试 可读性有助于理解 调试和维护 健壮性完备的异常和出错处理 高效率与低存储的需求时间 空间的要求 算法和复杂度 5 22 算法效率的衡量方法1 事后统计利用计算机内记时功能 缺点 必须先运行依据算法编制的程序 所得时间统计量依赖于硬件 软件等环境因素 掩盖算法本身的优劣 算法和复杂度 6 22 算法效率的衡量方法2 事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于 依据的算法选用何种策略 问题的规模 程序语言 编译程序产生机器代码质量 机器执行指令速度时间复杂度和空间复杂度 算法和复杂度 7 22 算法的时间度量 从算法中选取一种对于研究的问题来说是基本操作的原操作 以该基本操作重复执行的次数作为算法执行的时间度量 基本操作重复执行的次数分别为1 n n2 算法和复杂度 8 22 算法复杂度 问题的规模 n 或大小 如 矩阵的阶数 图的结点个数 被分类序列的正整数个数 时间复杂度 算法的所需的时间和问题规模的函数 记为T n 当n 时的时间复杂性 被称之为渐进时间复杂度 空间复杂度 算法的所需的空间和问题规模的函数 记为S n 当n 时的时间复杂性 被称之为渐进空间复杂度 算法和复杂度 9 22 给定两个正值函数f和g 考虑以下定义 定义1 如果存在正数c和N 对于所有的n N 有f n cg n 则f n O g n 上述定义表明 如果对于足够大的n 或大于某自然数N的n 存在正数c 使f不大于cg 则f是g的大O符号 大O符号 算法和复杂度 10 22 例如 f n 2n2 3n 1 O n2 在这里 g n n2 c和N的可选值如表所示 表对于函数f n 2n2 3n 1 O n2 根据大O定义计算得到的c和N的不同值 大O符号 算法和复杂度 11 22 算法分析中常见的复杂度O 1 O lgn O n O nlgn O n2 O n3 O 2n O n O nn 常数对数多项式指数 复杂度举例 算法和复杂度 12 22 复杂度举例 算法的重要性 计算机不是万能的 并非所有的算法 计算机都能够计算出有用的结果 差的算法不一定有实际意义 举一个例子加以说明 假定时间复杂性函数的时间单位为us 函数n 20n 50n 100n 5001000n 02s 05s 15s 5s1000nlogn 09s 3s 6s4 5s100n2 04s 25s1s25s10n3 02s1s10s21分nlogn 4s1 1小时220天5 108世纪2n 3 0001s0 1s2 7小时5 108世纪2n1s35年3 104世纪3n58分2 109世纪 易性算法 顽性算法 算法和复杂度 14 22 在大多数的情况下 我们只对时间复杂度感兴趣 它通常计算程序执行过程中赋值和比较操作的次数 例1 for i sum 0 i n i Sum a i 赋值2 2n次 渐近复杂度O n 确定渐近复杂度 算法和复杂度 15 22 确定渐近复杂度 例2 for i 0 i n i for j 1 sum a 0 j i j sum a j cout sumforsubarray0through i is sum endl 算法和复杂度 16 22 符号 符号如果存在正数c1 c2及N 对于所有的n N 有c1g n f n c2g n 则f n g n 算法和复杂度 17 22 最好 平均和最坏情况 有时 算法中基本操作重复执行的次数随问题的输入不同而不同 例 顺序查找算法 比较次数的复杂度是多少 returnFALSE 算法和复杂度 18 22 最好 平均和最坏情况 最好情况 算法需要的最少步骤最坏情况 算法需要的最多步骤平均复杂度 将处理每个输入所执行的步骤数与该输入出现的概率相乘 然后将所有相乘的结果相加 算法和复杂度 19 22 最好 平均和最坏情况 有时 算法中基本操作重复执行的次数随问题的输入不同而不同 例 顺序查找算法 最好1次比较 最坏n次比较 平均 n 1 2次比较 returnFALSE 算法和复杂度 20 22 数据结构的选择 分析问题在算法设计之前初步设计数据结构注意可扩展性比较时空开销的优劣 算法和复杂度 21 22 小结和后续内容 算法特性算法复杂度分析渐进复杂度最好 最坏 平均时间复杂度后续内容