简单的算法复杂度分析.ppt

第1讲简单的算法复杂性分析 算法复杂性 算法复杂性 度 是算法运行所需要的计算机资源的量 需要时间资源的量称为时间复杂性 需要的空间资源的量称为空间复杂性 算法分析的目的 设计算法 设计出复杂性尽可能低的算法选择算法 在多种算法中选择其中复杂性最低者 算法分析 AlgorithmAnalysis 对算法所需要的两种计算机资源 时间和空间进行估算时间复杂性 TimeComplexity 空间复杂性 SpaceComplexity 算法效率的衡量方法 先写程序 直接观察结果同一算法 程序不同 运行时间不同写代码太费事 如果写出来才发现很慢 不写程序 直接分析算法不写程序 怎么知道运行时间 用 基本操作 数来衡量表达式很复杂怎么办 渐进表示 算法 1 分析 sum 0 fori 1tondoforj 1tondosum sum a i j 基本操作 加法忽略循环变量i和j的改变时间共n2次基本操作时间复杂度为n2 算法 2 分析 sum 0 fori 1tondobeginfact 1 forj 1toidofact fact i sum sum fact end第i次循环执行了i个操作总时间复杂度为1 2 3 n n n 1 2如果式子再长一点 怎么办 比较两个算法 算法 1 执行了f n n2次基本操作算法 2 执行了g n n2 2次基本操作那个算法好呢 算法 2 好 因为g n f n 增长情况呢 n扩大10倍 f n 扩大100倍 g n 也扩大100倍两个算法的增长情况一样 渐进时间复杂度一样 渐进时间复杂度 f n n2和g n n2 2增长情况一样如何表示 增长情况 把f n 和g n 变成 渐进 形式 然后直接比较如何变成 渐进 形式 只保留最 大 项忽略系数例1 3n4 8n2 n 2 n4例2 2n 1 n100 5 2n 为什么n 1变成了n 复杂度分析不是万能的 回忆刚才的变换方法变换前后的增长情况一致需要先写出完整的式子至少知道最大项可是很多情况下无法知道最大项 不信 一个数n 如果它是奇数则变换到3n 1 否则变换到n 2给一个数n 不停的变换下去 经过几步变成1 你知道它的运行时间吗 复杂度分析不是万能的 渐进符号 计算算法的时间复杂度时 往往不需要算出精确的结果 对于足够大的输入规模来说 我们只需要关心运行时间的增长量级 也就是研究算法的渐进效率 渐近意义下的记号 O o 设f n 和g n 是定义在正数集上的正函数 O的定义O g n f n n0 c 0 s t n n0 0 f n cg n O记号表示的是一个渐进上界 有时也被非正式地用来描述渐进上确界 记为 f n O g n 表示f n 的阶不高于g n 的阶 根据O的定义 容易证明它有如下运算规则 1 O f O g O max f g 2 O f O g O f g 3 O f O g O fg 4 如果g n O f n 则O f O g O f 5 O Cf n O f n 其中C是一个正的常数 6 f O f o的定义o g n f n c 0 n0 0 s t n n0 0 f n cg n o记号表示的是一个非渐进的上界 记为 f n o g n 表示当n充分大时 函数f n 的阶比g n 低 的定义 g n f n n0 c 0 s t n n0 0 cg n f n 记号表示的是函数的渐进下界 记为 f n g n 表示f n 的阶不低于g n 的阶 的定义 g n f n c 0 n0 0 s t n n0 0 cg n f n 记号表示的是一个非渐进的下界 记为 f n g n 表示当n充分大时 函数f n 的阶比g n 高 的定义 g n f n n0 c1 c2 0 s t n n0 0 c1g n f n c2g n 记号表示的是函数的渐进上界和下界 记为 f n g n 表示f n 与g n 同阶 f n g n 当且仅当f n O g n 且f n g n 算法 渐进 时间复杂度 一般均表示为以下几种数量级的形式 n为问题的规模 c为一常量 1 称为常数级 logn 称为对数级 n 称为线性级 nc 称为多项式级 cn 称为指数级 n 称为阶乘级 P复杂度NP复杂度NPC复杂度 算法复杂性分类 简单算法的复杂性分析 对较复杂的算法计算算法的运行时间 经常从算法中选取一种对于所研究的问题来说是基本 或者说是主要 的原操作 以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则 这个原操作 多数情况下是最深层次循环体内的语句中的原操作 例如 for i 1 i n i for j 1 j n j c i j 0 for k 0 k n k c i j c i j a i k b k j 最大连续和 给一串整数a 1 n 求出它和最大的子序列 即找出1 i j n 使a i a i 1 a j 最大介绍四个算法并分析时间复杂度枚举优化的枚举分治贪心 算法一 枚举 思想 枚举所有的i和j 计算a i a j 选择最大的 程序如下 max a 1 fori 1tondoforj itondobeginsum 0 fork itojdosum sum a k ifsum maxthenmax sum end 时间复杂度如何分析 算法一分析 当i和j一定的时候 内层循环执行j i 1次总次数为应该如何计算 方法一 直接计算先计算里层求和号 得再加起来 好复杂 自己做一做吧 得利用公式12 n2 O n3 一般地 有1k nk O nk 1 总次数为 完全的计算太麻烦能不能不动笔就知道渐进时间复杂度呢 何必非要计算出详细的公式再化简呢 里层求和计算出的结果是O n i 2 12 22 n2 O n3 每步都化简 但是要保留外层需要的变量结论 算法一时间复杂度为O n3 经验 一般只能支持n 200 算法二 优化的枚举 思路枚举i和j后 能否快速算出a i a j 呢 预处理 记s i a 1 a 2 a i 规定s 0 0则可以在O n 的时间内计算出s 1 s n s 0 0 fori 1tondos i s i 1 a i 有了s i 怎么快速求a i a j 呢 a i a j a 1 a j a 1 a i 1 s j s i 1 而s i 经过预处理以后可以直接读出 程序如下 max a 1 fori 1tondoforj itondoifs j s i 1 maxthenmax s j s i 1 时间复杂度 预处理 主程序 O n n2 O n2 n 3000 算法三 分治 用一种完全不同的思路最大子序列的位置有三种可能完全处于序列的左半 即j n 2跨越序列中间 即i n 2 j用递归的思路解决 设max i j 为序列a i j 的最大子序列那么 用递归的思路解决 设max i j 为序列a i j 的最大子序列设mid i j 2 即区间a i j 的中点最大的第一种序列为max i mid 最大的第二种序列为max mid 1 j 问题 最大的第三种序列为 既然跨越中点 把序列a i j 划分为两部分a i mid 最大序列用扫描法在n 2时间内找到一共只有mid 1 n 2种可能的序列 一一比较即可a mid 1 j 同理一共花费时间为j i 1 算法三分析 如何分析时间复杂度呢 我们没有得到具体的T n 的式子只有一个递推式子T n 2T n 2 n设时间复杂度的精确式子是T n 第一 二种序列的计算时间是T n 2 因为序列长度缩小了一半第三种序列的计算时间是n计算出T n 就得到了时间复杂度怎样计算T n 呢 递归树分析 一般情形 T n aT n b f n a b为常数 f n 为给定函数由递归树得结果为T n f n af n b a2f n b2 aLf n bL 其中最后一项为递归边界 即n bL 1 因此L logbn n bL 1因此bL n记L logbn 称L为以b为底的n的对数对数的公式 logan logam loganmklogan logank换底公式 logan logbn logba对数是一种增长很慢的函数log21000约为10log21000000约为20时间复杂度O nlogn 和O n2 相比是很大的提高 和O n 在实际中相差并不是非常大 一般情形 T n aT n b f n a b为常数 f n 为给定函数递归树得到的结果 T n f n af n b a2f n b2 aLf n bL 其中L logbn算法三的递推式 T n 2T