当前位置: 首页 / 技术干货 / 正文
好程序员Java培训分享之算法入门到精通-算法复杂度(二)

2020-06-18

好程序员 Java培训 算法

  好程序员Java培训分享之算法入门到精通-算法复杂度(二),一、概述:上一篇我们讲解的是时间复杂度,更多的内容是让大家理解大O符号、以及时间复杂度是如何计算的。本章节将会带大家认识一下常见的时间复杂度。

Java2

  二、常见时间复杂度

  2.1、O(1)

  O(1)是zuihao的算法时间复杂度,也就是说同比效率最高的算法。其中的1表示的不是1次,之前有个同学问我,如果是消耗2个单位时间的时间复杂度是不是记为O(2)呢?不是。不论算法消耗几个单位时间,只要是这个时间不随着n的渐进性变化而变化,也就是这个单位时间永远都是2个、或者永远都是10个。这样的时间复杂度都记作O(1)。

  是不是所有O(1)时间复杂度的算法的执行时间都相等呢?不是,上面说了O(1)可能是2个单位时间,也可能是10个单位时间;再者,电脑的硬件不同、环境不同,哪怕同一个算法在不同机器上执行所消耗的时间都是不一样的,但是他们的时间复杂度都是O(1)。所以时间复杂度都是O(1)的,所消耗的时间是不相等的。如下图,增长是一条水平的直线。

  2.2、O(n)

  O(n)是线性增量的时间复杂度,也成为线性时间复杂度。因为其时间变化是线性增长的。

  在此,先要说清楚什么是线性增长,线性增长也可以称为等速增长。比如2n+2这个函数就是线性增长,因为当n为1的时候2n+2=4,当n=2的时候为6,当n=3的时候为8,每次都是增量都是2,等量增长,也是等速增长。这样的增长成为线性增长。

  2.3、O(n^2)

  O(n^2)这种时间复杂度的算法,随着n的增大其计算速度也是越来越慢,慢下来的速度是非常快。也就是相比O(n)而言,时间复杂度是O(n^2)的算法执行时间相对来说所花费的时间更长。比如冒泡排序就是这种时间复杂度

  2.4、O(logn)

  O(logn)是一种对数类型的时间复杂度。

  对数的概念先给大家复习一下,比如2^x=n,转换对数就是以2为底数n的对数,记作log2 n(此处的2应该放到log下角,并且写小一点,但是计算机打不出来我用空格以示区分)。比如以2为底8的对数是3,记作log2 8=3.

  所以,当n非常大的时候,时间复杂度的增长反而比较小。因为n=256的时候,log2 256=8。也就是n为256但是O(logn)时间复杂度反而只是8。因此O(logn)复杂度的算法也是相对来说比较优秀的算法。

  2.5、O(nlogn)

  O(nlogn)时间复杂度的概念在了解了O(logn)之后应该会有一个粗略的推测了。比如log2 256=8,那么nlog就是256(log2 256)=256*8,这种增速比O(n)要大,但是比O(n^2)要小

  总结

  时间复杂度上O(1)<O(logn)<O(n)<O(nlogn)<O(n^2),在实际开发中,我们对算法的优化尽量往O(logn)方向靠拢,就会更节省时间。

  本节将一些常见的时间复杂度列出来,目的有两个,一是让大家能更深入一点了解时间复杂度;二是对后面可能出现的一些数学公式做一些复习。以便后面的内容能直接引用。

  算法的时间复杂度还有很多其他的复杂度表示函数,这个取决于算法的复杂性,上面列举的时间复杂度基本是我们常见的了。本节知识作为了解的内容,后面我们在讲解到具体算法的时候,会结合具体例子讲解对应的时间复杂性。同时也欢迎大家留言点评讨论,一起成长进步。

好程序员开班动态

More+
  • HTML5大前端 <高端班>

    开班时间:2020-02-17(北京)

    开班盛况

    开班时间:2020-03-02(深圳)

    开班盛况
  • 大数据+人工智能 <好程序员严选班>

    开班时间:2019-12-23(北京)

    开班盛况
  • 大数据+人工智能 <好程序员班>

    开班时间:2020-02-24(杭州)

    开班盛况

    开班时间:2020-02-17(北京)

    开班盛况
  • JavaEE分布式开发 <高端班>

    开班时间:2020-03-09(北京)

    开班盛况
  • Python全栈+人工智能 <高端班>

    开班时间:2019-07-22(北京)

    开班盛况
  • 云计算开发 <高端班>

    开班时间:2020-02-24(北京)

    开班盛况
在线咨询
免费试听
入学教程
立即报名

Copyright 2011-2020 北京千锋互联科技有限公司 .All Right 京ICP备12003911号-5 京公安网11010802011455号