美文网首页
算法——复杂度

算法——复杂度

作者: YQY_苑 | 来源:发表于2018-05-21 22:27 被阅读0次

1. 算法复杂度

  • 时间复杂度: 执行算法所需要的计算工作量
  • 空间复杂度: 执行算法所需要的内存空间

举一个例子:

  • 求:从数组中查找一个数
  1. 如果数组有 10 个元素?
  2. 如果数组有 1000 个元素?
  3. 如果数组有 100000 个元素?

以上三种情况,若用for循环查找,则最优解都为第一个元素就找得到,那么就都只需要循环1次即可。

但若需要查找的元素在最后一个那么需要循环的次数就为数组的长度n。

2. 时间复杂度

  • 在计算机科学中,算法的时间复杂度是一个函数,它定量描述了
    该算法的运行时间。
  • 以算法输入值规模 n 为自变量的函数:


    image.png

其中:

  • 大 O 符号 O < (Big O) 【小于某一临界值】
  • 大 Ω 符号 Ω > (Big Omega (Ω )) 【大于某一临界值】
  • 大 Θ 符号 Θ = (Big Theta (Θ))【介于某一临界值】

大 O 符号 Example:

image.png
  1. n = 1 时 4*n^2 项是 2n 项的 2 倍大
  2. n = 500 时 4*n^2 项是 2n 项的 1000 倍大
  • 因此,当n非常之大的时候,2n项的怎么也大不过n^2,故2n 项对表达式值的影响可忽略不计
结论: image.png

快速排序

  • Best case:数组内各元素均相等,故 T(n)=O(1)

  • Worst case: T(n)=O(n^2)

  • Expected Case: T(n)=O(nlogn)

一般情况下,Expected Case == Worst case ,快速排序除外

3. 时间复杂度比较

越小越好!!!!
O(1)永远是最优解!!!

image.png

计算时间复杂度 一般问题 –

  • 基本操作的时间复杂度
    • 丢弃常数项
    • 丢弃次要项


      image.png
  • 基本操作被执行了多少次( For / While 循环)
  • 复合操作:加还是乘


    image.png

相关文章

  • 算法相关

    算法复杂度相关概念:漫画:什么是时间复杂度?算法的时间复杂度和空间复杂度详解算法题库:力扣 一、排序算法 排序算法...

  • 算法基础知识

    算法的复杂度 算法的复杂度: 算法的时间复杂度和空间复杂度合称为算法的复杂度,一般不特别说明,讨论的时间复杂度均是...

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

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

  • 算法

    重拾算法:算法效率分析(一)(空间复杂度和时间复杂度) 详解算法的各种复杂度的差别有多大(带图) 算法复杂度 选择...

  • 算法复杂度

    算法的复杂度是以什么来度量的? 算法的复杂度是以时间复杂度和空间复杂度来计算的。 ①算法的时间复杂度 ...

  • 算法复杂度

    算法复杂度 算法复杂度的目的:分析代码执行的时间成本。我们从五个方面来介绍算法复杂度:时间复杂度、时间复杂度分类、...

  • 全网最好的数据结构学习文章合集系列之空间复杂度

    二、空间复杂度 算法概念 及 复杂度 简单的LRU Cache设计与实现 js算法初窥07(算法复杂度) 算法的时...

  • 数据结构-0-时间复杂度和空间复杂度

    1. 算法的复杂度: 算法的复杂度分为时间复杂度和空间复杂度。时间复杂度,是衡量算法执行时间的长度;空间复杂度,是...

  • 时间和空间复杂度

    算法复杂度 算法复杂度分为和。 时间复杂度是指执行算法所需要的计算工作量。 空间复杂度是指执行这个算法所需要的内存...

  • 算法的复杂度

    算法复杂度分为时间复杂度和空间复杂度。时间复杂度是指执行算法所需要的计算工作量,而空间复杂度是指执行这个算法所需要...

网友评论

      本文标题:算法——复杂度

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