美文网首页
数据结构和算法 1-3 时间复杂度和空间复杂度

数据结构和算法 1-3 时间复杂度和空间复杂度

作者: Bc_wh1te_Le1 | 来源:发表于2019-06-23 00:14 被阅读0次

算法的效率一般指算法的运行时间。

算法效率的度量方法。

  • 算法采用的策略、方案
  • 编译产生的代码质量
  • 问题的输入规模
  • 机器执行指令的速度

函数的渐近增长

给定两个函数 f(n) 和 g(n),如果存在一个整数N,使得对于所有的n>N, f(n) 中总是比 g(n) 大,那么,我们说 f(n) 的增长渐近快于 g(n)


image.png image.png

算法可以忽略一些加法常数


image.png image.png

与最高次项相乘的常数并不重要


image.png image.png

最高次项指数大的,函数随着n的增长,结果也会变得增长特别快


image.png
image.png
image.png

判断一个算法的效率时,函数中的常数项和其他次要项常常可以忽略,二更应该关注主项(最高项)的阶数。

空间复杂度 时间复杂度

image.png

推导大O阶方法

  • 用常数1取代运行次数函数中的所有加法常数
  • 在修改后的运行次数函数中,只保留最高阶项
  • 如果最高项存在且不是1,则去除与这个项相乘的常数
image.png

线性阶
一般含有非嵌套循环涉及线性阶,线性阶就是随着问题规模 n 的扩大,对应计算次数呈直线增长。

平方阶
n^2
对数阶

image.png image.png image.png image.png image.png

最坏情况与平均情况

image.png

通常除非特别指定,我们提到的运行时间都是最坏情况的运行时间。

算法的控件复杂度

image.png

相关文章

  • 数据结构(一)时间复杂度

    简介:如果想对数据结构和算法有基本的了解和认识,那么算法复杂度是前提,算法复杂度包含时间复杂度和空间复杂度,具体概...

  • 算法复杂度

    数据结构: 数组、链表、栈、队列、二叉树、hash表、图。 空间复杂度和时间复杂度的算法 空间复杂度和时间复杂度 ...

  • Python-100天(二)-Python语言进阶

    数据结构和算法 算法:解决问题的方法和步骤 评价算法的好坏:渐近时间复杂度和渐近空间复杂度。 渐近时间复杂度的大O...

  • Python语言进阶

    Python语言进阶 数据结构和算法 算法:解决问题的方法和步骤 评价算法的好坏:渐近时间复杂度和渐近空间复杂度。...

  • 【Python 100天从新手到大师】Python语言进阶

    Python语言进阶 数据结构和算法算法:解决问题的方法和步骤评价算法的好坏:渐近时间复杂度和渐近空间复杂度。渐近...

  • 数据结构和算法

    01_数据结构和算法绪论.mp4 02_谈谈算法.mp4 03_时间复杂度和空间复杂度.mp4 04_时间复杂度和...

  • 数据结构与算法之线性表

    前言 上一篇《数据结构和算法之时间复杂度和空间复杂度》中介绍了时间复杂度的概念和常见的时间复杂度,并分别举例子进行...

  • 排序算法

    数据结构8种排序时间和空间复杂度对比七大查找算法学了这么多年算法,你还不知道时间复杂度和空间复杂度如何计算吗?排序...

  • 算法复杂度分析

    复杂度分析: 数据结构和算法解决的两大问题:快和省。运行快,储存省。 复杂度分析是算法学习的精髓:时间复杂度,空间...

  • 时间复杂度和空间复杂度笔记

    复杂度分析笔记 复杂度主要分为时间和空间复杂度 时间复杂度:算法(程序)执行的时间变化趋势 空间复杂度:算法(程序...

网友评论

      本文标题:数据结构和算法 1-3 时间复杂度和空间复杂度

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