美文网首页
算法设计与分析基础 | 时间复杂度分析

算法设计与分析基础 | 时间复杂度分析

作者: 胖三斤66 | 来源:发表于2018-10-23 19:59 被阅读0次
算法运行时间计算公式

对于大规模的数，效率分析时时常忽略乘法常量，仅关注执行次数的增长次数及其常数倍

符号 O,\Omega,\Theta

O(g(n)) 是增长次数小于等于 g(n) 的函数集合。比如 g(n) = n^2，即 O(n^2)。那么就有

n \in O(n^2),\frac{1} {2}n(n-1) \in O(n^2),100n+5 \in O(n^2) 为真

定义：当 t(n) \in O(g(n)) \wedge n \geq n_0 时，t(n) \leq c*g(n) ，其中 c 是大于 0 的常数

\Omega(g(n)) 是增长次数大于等于 g(n) 的函数集合。比如 g(n) = n^2，即 \Omega(n^2)。那么就有

n^3 \in \Omega(n^2),\frac{1} {2}n(n-1) \in \Omega(n^2),100n+5 \notin O(n^2) 为真

定义：当 t(n) \in \Omega(g(n)) 时，t(n) \geq c*g(n) ，其中 c 是大于 0 的常数

\Theta(g(n)) 是增长次数等于 g(n) 的函数集合。比如 g(n) = n^2，即 \Theta(n^2)。那么就有

\frac{1} {2}n(n-1) \in \Theta(n^2) 为真

如何简单判断 t(n) 属于 O(g(n))~or~\Omega(g(n))

利用极限比较增长次数

递归算法效率分析

反向替换法

齐次二阶线性递推式：斐波那切数列

该算法基本操作是加法，把 A(n) 定义为在计算 F(n) 过程中所做的加法次数，那么就有：

分析斐波那切数列的效率

总结

利用极限判断

递归算法的效率分析方法：

  1. 反向替换法
  2. 齐次二阶线性递推式

相关文章

  • 数据结构与算法

    参考文档《算法图解》《计算机算法设计与分析》 简单查找 时间复杂度 空间复杂度 java Demo 二分查找 时间...

  • 数据结构学习大纲

    第一章 绪论 数据结构基本概念数据结构基本概念算法的基本概念算法的时间复杂度与空间复杂度分析基础时间复杂度分析空间...

  • 数据结构与算法 复杂度分析

    复杂度：时间复杂度和空间复杂度。复杂度的分析是学习数据结构与算法的基础！ 极简概述 复杂度的分析已经有很多很好...

  • 算法设计与分析基础 | 时间复杂度分析

    对于大规模的数，效率分析时时常忽略乘法常量，仅关注执行次数的增长次数及其常数倍 符号 O, 是增长次数小于等于 g...

  • 数据结构与算法-复杂度分析

    时间、空间复杂度：衡量算法执行小路的指标，数据结构与算法离不开时间、空间复杂度分析，复杂度分析是算法的精髓。 为什...

  • 如何学习数据结构与算法

    算法学习经验 推荐： 入门： 数据结构启蒙：《数据结构与算法分析——C 语言描述》 算法启蒙：《算法设计与分析基础...

  • 给我巨大影响的技术书籍

    算法《算法概论》《算法设计与分析基础》 Anany Levitin《算法引论》Udi Manber《算法导论》《什...

  • 递归树——借助树来求解递归算法的时间复杂度

    递归代码的时间复杂度分析起来非常麻烦，今天我们尝试来借助递归树分析递归算法的时间复杂度。 1. 递归树与时间复杂度...

  • 阶段02#大三·下

    A 书籍 C程序设计语言 Java学习指南 C++语言基础教程 数据结构与算法分析 算法设计与分析基础 计算机网络...

  • 第14章 深度优先搜索

    1、中国象棋 算法分析 bfs 时间复杂度 Java代码 2、踏青 算法分析 flood fill 算法 时间复杂...

网友评论

      本文标题：算法设计与分析基础 | 时间复杂度分析

      本文链接：https://www.haomeiwen.com/subject/fmxkzftx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|算法设计与分析基础 | 时间复杂度分析|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！