美文网首页算法
算法入门——大O表示法、时间、空间复杂度

算法入门——大O表示法、时间、空间复杂度

作者: 白巧克力LIN | 来源:发表于2022-05-13 23:45 被阅读0次

算法

算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令。简单来说算法是一个计算过程,解决问题的方法。

任何代码片段都可视为算法,我们使用算法一般都是为了最大限度地减少运行时间或占用空间。

大O表示法来指出算法的速度,通过时间复杂度和空间复杂度来衡量算法的好坏。

大O表示法

大O表示法是一种特殊的算法,其作用是指出算法的速度,大O表示法表示方式如下:


其中:

  • O:是大写字母O;

  • n:表示操作数,操作数,它指出了算法的运行时间的增速。

从快到慢的顺序列出我们经常会遇到算法的5种运行时间:

  • O(log n):对数时间,该时间的算法包括二分查找法;

  • O(n):线性时间,该时间的算法包括顺序查找;

  • O(n * log n ):该时间的算法包括快速排序;

  • O(n ² ):该时间的算法包括选择排序;

  • O(n!):该时间的算法包括旅行商问题。

注意:

  • 算法的速度指的并非时间,而是操作数的增速;

  • 算法运行时间并不以秒为单位。

时间复杂度

时间复杂度是用来评估算法运行效率的式子。

在下面的几组代码中,假设每执行一行代码的时间为t,那么哪组代码运行时间最短呢,用大O表示法该如何表示。

# 第一组
print('Hello,World')                    

# 第二组
for i in range(n):                  
    print('Hello,World')

# 第三组
for i in range(n):                  
    for j in range(n):
        print('Hello,World')

# 第四组
for i in range(n):                  
    for j in range(n):
        for k in range(n):
            print('Hello,World')

在第一组代码中,因为只有一行代码,所以它的运行时间为O(t);

第二组代码中,有个for循环,执行了n次,所以它的运行时间为O(n×t);

第三组代码中,在for循环中嵌套了for循环,执行了n²次,所以它的运行时间为O(n²×t);

第四组代码中,在for循环中嵌套了for循环又嵌套了for循环,执行了n³次,所以它的运行时间为O(n³×t)

所以第一组代码运行时间最短。

再看下面两组代码:

# 第一组
print('Hello,World')
print('Hello,Python')
print('Hello,Java')

# 第二组
for i in range(n):
    print('Hello,World')
    for j in range(n):
        print('Hello,World')

在第一组代码中,有三行代码,共执行了3次,所以它的运行时间为O(3×t);

第二组代码中,第一个for循环中执行了print,所以执行时间为n×t,在嵌套的for循环中,执行了n次,所以运行时间为n²×t,所以第二组代码运行时间为O((n+n²)×t)。

答案是不是这样呢?答案是错误的,例如:烧一壶水需要多长时间,没有人会回答5分35秒的。也就是说没有会说个很具体的时间,都是说模糊的时间,例如烧一壶水需要几分钟。时间复杂度也是同样的道理。

所以我们需要把具体是时间模糊化,也就是把具体的时间复杂度表达式简化,所以第一组代码的运行时间为O(t),第二组代码的运行时间为O(n²),因为n² 的数据规模远大于 n。

空间复杂度

空间复杂度是用来评估算法内存占用大小的式子。空间复杂度的表示方式与时间复杂度完全一样。示例代码如下:

# 第一组
a='11'                  #变量
b='22'
c='33'

# 第二组
a=[1,2,3,,...,n]            # 一维数组

# 第三组
a[m][n]=9               # 二维数组

在第一组代码中,有a、b、c三个变量,所以其空间复杂度为O(1);

第二组代码中,a是一维数组,长度为n,所以其空间复杂度为O(n);

第三组代码中,a是二维数组,长度mn,所以其空间复杂度为O(mn);

注意:一般情况下,时间复杂度的优先级比空间复杂度优先级高,也就是优先选择时间复杂度低的算法。
好了,关于算法入门——大O表示法、时间、空间复杂度就学到这里,下篇文章我们学习算法入门——顺序查找、二分查找。
公众号:白巧克力LIN

该公众号发布Python、数据库、Linux、Flask、自动化测试、Git、算法等相关文章!

相关文章

  • 简单的时间复杂度计算法则

    简单算法时间复杂度计算 大O表示法 像前面用O( )来体现算法时间复杂度的记法,我们称之为大O表示法。 算法复杂度...

  • 【python】二分法和选择排序法的实现

    一、大O表示法 学算法就绕不开大O表示法,大O法可以告诉我们算法的时间和空间复杂度。 我们先聊点简单的,请你从1数...

  • 排序算法

    复杂度 常用大O表示法展示算法的时间复杂度和空间复杂度。大O时间复杂度表示代码执行时间随数据规模变化的趋势。下面是...

  • 复杂度

    算法优劣 时间复杂度估算程序指令的的执行次数(执行时间) 空间复杂度估算所需占用的空间 大O表示法(Big O) ...

  • 算法界的小学生--打好基础(数据结构和算法)

    一, 算法的大O表示法 我们在平时看到算法的时候,总会连带看到时间复杂度,空间复杂度之类的概念,对于O(n),O(...

  • 2022-09-23

    算法过程描述 动图演示 复杂度 用大O表示法,忽略常量、低阶和常数系数。 时间复杂度为:O(n²)空间复杂度为:并...

  • 算法复杂度

    一、大O表示法 算法的时间复杂度通常用大O符号表述 大O表示法 : ,n为算法所需要执行的操作数 该表示法的操作数...

  • ### 数据结构基础篇

    数据结构与算法 入门篇复杂度分析时间复杂度大O时间复杂度表示法,表示代码执行时间随数据规模增长的变化趋势,也叫渐进...

  • 复杂度分析

    1. 大 O 复杂度表示法 时间复杂度就是算法的执行效率,也就是算法代码执行的时间; 大 O 时间复杂度实际上并不...

  • 时间复杂度 BigO

    时间复杂度 BigO [大O表示法] 算法的渐进时间复杂度 T(n) = O(f(n)) T(n) -- 时间的渐...

网友评论

    本文标题:算法入门——大O表示法、时间、空间复杂度

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