美文网首页
数据结构与算法:基础篇(三):算法比较及复杂度计算

数据结构与算法:基础篇(三):算法比较及复杂度计算

作者: 溪浣双鲤 | 来源:发表于2020-06-16 23:47 被阅读0次

一、算法定义

算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每个指令表示一个或者多个操作。

二、算法特性

  1. 输入输出 - 算法是为了解决问题而存在的,必须有输入和输出
  2. 有穷性 - 有限次执行下得到结果
  3. 确定性 - 不同的输入都有其对应确定的结果
  4. 可行性

三、算法设计要求

  1. 正确性
  2. 可读性
  3. 健壮性
  4. 时间效率高和存储量低

设计一个算法必须先保证正确,可读以及健壮性,然后再考虑时间效率以及存储量

四、时间复杂度

程序时间计算因素:

  1. 算法输入时间
  2. 编译可执行代码
  3. 执行指令
  4. 执行重复的指令

一个算法的时间复杂度定性描述该算法的运行时间,并且一个算法花费的时间与算法中语句执行次数成正比。

四、大O表示法

时间复杂度常用大O符号表述;大O符号表述的规则:

  1. 用常数1取代运行时间中所有常数 3->1 O(1)
  2. 在修改运行次数函数中,只保留最高阶项 n3+2n2+5 -> O(n^3)
  3. 如果再最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3

五、时间复杂度常用术语

  1. 常数阶 -> O(1)
  2. 线性阶 -> O(n)
  3. 平方阶 -> O(n^2)
  4. 对数阶 -> O(logn)
  5. 立方阶 -> O(n^3)
  6. nLog阶 -> O(nlogn)
  7. 指数阶(不考虑) -> O(2^n)或者O(n!) 除非n非常小,否则会造成噩梦般的时间消耗,不切实际,一般不考虑

示例:

阶.png

六、空间复杂度

程序空间计算因素:

  1. 寄存本身的指令
  2. 常数
  3. 变量
  4. 输入
  5. 对数据进行操作所需要的辅助空间

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度计算公式记做:

S(n) = n(f(n)), 其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。

在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间

空间复杂度同样用大O表示法。

溪浣双鲤的技术摸爬滚打之路

相关文章

  • 一位算法工程师的自我修养

    数据结构与算法 基本算法思想动态规划贪心算法回溯算法分治算法枚举算法 算法基础 时间复杂度 空间复杂度 最大复杂度...

  • 数据结构与算法:基础篇(三):算法比较及复杂度计算

    一、算法定义 算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每个指令表示一个或者多个操作...

  • 数据结构与算法 - 查找

    数据结构与算法系列文章数据结构与算法 - 时间复杂度数据结构与算法 - 线性表数据结构与算法 - 树形结构数据结构...

  • 数据结构与算法 - 树形结构

    数据结构与算法系列文章数据结构与算法 - 时间复杂度数据结构与算法 - 线性表数据结构与算法 - 树形结构 目录 ...

  • 算法与数据结构

    数据结构 数据结构与算法分析_Java语言描述(第2版) 算法 计算机算法基础算法导论编程之法_面试和算法心得 c...

  • #算法与数据结构书籍

    数据结构 数据结构与算法分析_Java语言描述(第2版) 算法 计算机算法基础算法导论编程之法_面试和算法心得 c...

  • 数据结构学习大纲

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

  • 数据结构与算法

    数据结构与算法之美 数据结构与算法之美1--如何学数据结构与算法之美2--复杂度分析(上)数据结构与算法之美3--...

  • 数据结构, 算法, 设计模式资料

    资料 实践, 阅读, 思考并行 资料数据结构, 算法设计模式 数据结构, 算法 计算机科学的基础 零基础学算法 大...

  • 算法 & 数据结构

    概述 程序 = 算法 + 数据结构算法是计算机科学的本质,是计算机世界的基石 算法的复杂度 定性描述算法的运行时间...

网友评论

      本文标题:数据结构与算法:基础篇(三):算法比较及复杂度计算

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