小白： 庆哥啊，这个复杂度到底是个啥啊，我在上大学的时候学这块的时候就很懵，不知道是个啥，理解起来很费劲，所以当时也没有好好学习，自己的数据结构与算法这块一直比较薄弱，准备好好再学学数据结构与算法嘞，这一个复杂度都难住我了
庆哥： 的确啊，虽然就三个字，但是理解起来也确实有点费劲，我当时学习的时候也是有点理解不了，感觉看了很多解释，总觉得迷迷糊糊的，还是不知道到底是个啥？
小白： 嗯嗯，是的，我也上网搜了很多的关于复杂度的分析的文章，有些文章觉得越看越迷糊，看着看着就看不下去了，然后我就去看看评论，想着会有人跟我一样觉得看不懂，结果评论都是“写的很好”，顿时觉得自己是不是太笨了。
庆哥： 哈哈，太真实了，那今天咱俩就来好好学习下这个复杂度吧，绝对让你对复杂度有个全新的认识
一起攻克复杂度吧小白： 嗯嗯，那我得好好学习了，复杂度一直困扰着我，还真的是复杂啊，对了，有啥不明白的可是随时提问你的哦，还请庆哥赐教
庆哥： 小事小事，那咱开始吧，首先我们要知道我们学习啥，那必须是复杂度啊，咋一看，三个字“复杂度”，应该是个名词吧，所以嘞，首先我们得知道，它一定有他本身的概念，那好，我们看看复杂度是怎么定义的，怎么看？必须是百科的解释啊，来，一起看看：
“
在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n3 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。
看看，明白不？
小白： 说实话，看到这个真的有点懵啊，时间复杂度？跟复杂度一样吧，什么函数，大O，低阶项，渐进时间，这都是啥跟啥啊，是不是涉及数学啊，我数学可一直都不好啊
庆哥： 别说你，我刚开始看这个的时候也是一脸茫然啊，也许真的是因为咱俩太笨了，怪尴尬，不过我觉得这个解释虽然很正确，但是有点官方，对已经只是到啥是时间复杂度的来说很不错，但是对于新手和那些对复杂度概念有疑惑的人来说，真的不算友好，本身就理解的云里雾里，看这个更迷茫了
小白： 对对对，也许它说的很对，但是这样解释就是觉得好迷茫，不知道到底是个啥，庆哥快给我解释解释吧
复杂度小探
庆哥： 嗯嗯，那接下来，我就把我的理解用大白话给你解释一下吧，首先嘞，针对你上面的一些疑问咱先来说说，你要知道，咱们这里要探讨的复杂度是数据结构与算法里面的概念，为啥要这样说，中华文字，博大精深，一样的字放在不同的场景里，那含义就不同了，所以咱必须先明确，我们这里讲的 ==复杂度是数据结构与算法中的概念==
好了，知道这个之后，我们还要知道，我们这里说复杂度，更为准确的来说是==时间复杂度==（还有空间复杂度嘞），所以后面咱们不说复杂度了（避免有歧义），就说时间复杂度（因为时间复杂度相对来说比较重要），先跟你说一声，这个时间复杂度是针对于算法的，所以再全面点，我们实际应用中会说成==某个算法的时间复杂度==
小白： 是啊，复杂度，哎不对，是时间复杂度，就是跟算法有关的，数据结构与算法是块超级难啃的骨头啊
庆哥： 的确，==数据结构与算法真的很重要==，按时不可否认，真的不容易，很多程序员这块的技能也都不是很强，数据结构与算法这块牛了，那都是大神级别的啊，很多小渣渣早就放弃了，根本学不会啊
小白： 这太扎心了，我好难啊
庆哥： 虽说数据结构与算法有一定难度，但是还没有到了那种难得学不会的地步，需要你==多花时间，多思考多练习==，很多人第一步都不敢迈出去，当然难了
小白： 嗯嗯，确实，很多人听到数据结构与算法，心里不自然的就觉得好难，然后就没有学下去的欲望了，首先就被自己吓到了，我要迈出第一步，跟着庆哥
庆哥： 哈哈，可以可以，我的这块也是比较薄弱，咱们共同共同学习，那咱接着上面的说，经过上面说的，我们现在知道了，我们要搞定的就是时间复杂度，至于什么大O，低阶项的，咱们一步步来。
理解时间复杂度的前提
那时间复杂度到底是个啥呢？我个人觉得啊，要想理解什么是时间复杂度，我们先要知道什么是算法，为啥，因为时间复杂度就是针对算法才有的一个概念，注意啦，我开始慢慢分析什么是时间复杂度了哦
小白： 嗯嗯，我在注意听着嘞
庆哥： 好的，千万别走神，为啥说理解时间复杂度的前提先要搞明白算法是啥呢？举个例子，比如有人要给你介绍对象，你这人嘞比较在意身高，所以你就问“那货多高啊”，别人说差不多一米6左右吧，这个时候你就知道她多高了，这个身高就是衡量一个人的，这个好理解吧，而这个时间复杂度就是用来衡量一个算法的。
你想想，为啥你要问身高，因为你比较在意身高，比如说身高达到一米六就是你的标准，那达到这个标准就是好啊，达不到就是不好，如果人家才一米五，你肯定说，不好，身高不行，所以身高也作为你衡量一个人好不好的指标，那对于算法嘞，一个算法也有好不好的说法，那用啥来衡量一个算法的好坏呢？
小白： 我知道，时间复杂度
庆哥： 嗯嗯，说的非常对，我们就可以用时间复杂度来衡量一个算法的好坏，当然，你衡量一个人的好坏，可以有很多指标，身高只是其中之一而已，同理，对于算法的好坏，也有好多指标，时间复杂度也只不过是其中之一罢了，像空间复杂度也可以来衡量一个算法的好坏，不过嘞我们这里主要探讨的是时间复杂度对算法的影响。
小白： 庆哥啊，不是要说什么是算法吗，这里好像把什么是时间复杂度给讲讲了吧
算法是啥
庆哥： 哈哈，别着急，到了这里，你应该知道了，==时间复杂度是用来衡量算法的一个指标==，那啥是算法嘞？
小白： 说实在的，我对算法也有点迷迷糊糊的，觉得算法就是一种方法吧
庆哥： 其实吧，概念性的东西没有个定性答案，所以，按照你的理解没啥问题，所谓算法，当然咱这里也是针对数据结构与算法这块说的，它就是你解决问题采用的一种方式方法而已，我们这学编程的，终究是要落实到代码中的，在代码里来说，不同的算法，也就是你实现的代码不一样，但是达到的目的是相同的，用我们生活中的例子来说，那就是条条大路通罗马啊
就像这个图一样，我们从起点到终点，可以选择的路线有很多，但是我们直观来看，图中红色的路线是最近的，其实这里拿到编码中来说，每一条路线都可以说成是一个算法，那这里的好坏就是哪个近哪个算法好啊，这应该没啥难理解的吧。
这里的路线的远近就可以看成是时间复杂度，路线近，我们可以说时间复杂度小，算法就好，路线远，时间复杂度就高，算法相对来说就不好。
那为啥又说衡量一个算法的好坏，时间复杂度只是其中一个指标呢？难道这里的红线路线就是最好的吗？比如我们考虑道路问题，看下面的图，红线虽然近，但是路不好走，黑线虽然远点，但是路好走，综合下来，黑线是最佳路线。
所以说，时间复杂度并不能作为一个衡量算法的唯一标准，因为还有其他影响算法的因素，只不过，时间复杂度的影响比较大，我们常规讨论算法的好坏的时候经常使用时间复杂度来苹果。
那么，说到这里，你知道了啥是算法和时间复杂度了吧？
小白： 嗯嗯，对他们的概念比较清晰了，其实算法这个玩意就是一个怎么做比较好的问题吧
庆哥： 是啊，所以算法也涉及到思想层面，上升到这个高度就有难度，值得研究了，因为怎么找一个最佳选择，也就是最好的办法是需要费脑筋的，有的人能想到，有的人就是想不到
小白： 哈哈，是这样啊，这里也知道了时间复杂度是用来衡量算法的一个指标了，也就是清楚概念了，不过不是有什么大O啥的吗？就是它咋用啊
怎么表示时间复杂度嘞
庆哥： 不着急，咱继续，经过上面的讲解，我们大致清楚时间复杂度的概念了，以及它有啥用，那么应该怎样来表示时间复杂度了，我们上面举过身高的例子，那表示身高可以用多少多少cm啊，也就是160cm，那么时间复杂度该怎么表示嘞？
小白： 这个我知道，叫什么大O表示法，经常见表示哪个算法的时间复杂度是O(1)啊，或者O(n)之类的。
庆哥： 对的，就是用这种方式来表示时间复杂度，那你知道啥是大O表示法吗？
小白： 这个就有点迷惑了，只知道这样表示，但是要说啥是大O表示法，就有点懵
庆哥： 那咱来看关于大O表示法的一个概念解释：
“
若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n) 的同数量级函数。记作T(n)=O(f(n))，称为O(f(n))，O为算法的渐进时间复杂度，简称为时间复杂度。因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法。
怎么样，看得懂不
小白： 说实话，懵
庆哥： 别说你懵，我也懵，没办法，咱们数学差啊，当初学数学的时候，有些概念就是理解不了，感觉说的好绕，那啥是大O标识法嘞，我觉得吧，没必要去纠结它的概念性问题，你只需知道大O标识法的形式就是==O(n)==，啥事大O啊，就是大写字母O啊，然后一个括号，括号里面一个数，这个数可以事已知的，比如说1，其实也就只有1，也可以事未知的，比如n，也可以是2n，3n或者是n的平方（n^2）等等，反正未知的就是跟n相关的函数。
大O表示法为啥是n
小白： 有个疑问啊，这里为啥是n呢？
庆哥： 当然，这个n只是表示个未知数，我们之前表示未知数通常是x和y之类的，这里使用n只是个约定俗称的事，也就是习惯成自然，大家之前都这样表示，于是干脆就这样吧，使用n来表示，其实吧，这个也跟我们写代码有关，比如我们写一些循环代码，经常出现n，像这样：
public static int test2(int n) { if(n<=1) return n; int first = 0; int second = 1; for (int i = 1; i < n; i ) { second = first; first = second - first; } return second; }
看到没，这段代码中使用的n，对了，你知道怎么计算时间复杂度的嘛？
小白： 就是如何计算一个算法的时间复杂度嘛？我就不会这个，看了不少文章，好多都是在介绍啥是时间复杂度，可是就是不告诉我时间复杂度该怎么计算
如何计算时间复杂度
庆哥： ，那咱来说说，因为跟你说了这个怎么计算时间复杂度的之后，你就会更明白为啥是n了，首先，你有没有觉得时间复杂度跟时间有关
小白： 必须啊，人家就叫时间复杂度，我之前还以为时间复杂度就是多少多少秒之类的，结果是O(n)什么的，这是咋算出来的啊
庆哥： 你这样理解也正常，那是因为我们对时间这个概念固化了，想着时间那就是时分秒来计算的，这些都是时间单位，是我们熟知的时间单位，但是还有可能时间不是一时分秒来计算，时分秒是确切的，也有可能是抽象的，没什么意思呢？我们弄个代码来看下：
public static int test(int n) { return n ; }
咋样，这段代码简单吧，就是给定一个值，然后加一返回，我们了解过什么是算法了，这段代码其实就是一个算法，只不过超级简单，它是用来计算一个值加一之后的结果的，那么我们来看怎么算它的时间复杂度，该怎么计算呢？
我们先约定好，在方法体内，每执行一次操作，我们记作1，也就是花费了一个时间单位，你看这里并没有说是1秒还是1分，就说是一个时间单位，我们下面来看这段代码。
在这段代码中，就有一行代码，也就是：
return n ;
它就算做一次操作，所以这里花费的是1个时间单位，也就是1，那它的时间复杂度就是O(1)
小白： 为啥啊？
庆哥： 不着急，我们继续看下面的代码：
public static int test(int n) { n= 5; return n ; }
与上面代码不同的地方是这里多了一行代码，把给定的值加上5，我们来看它的时间复杂度，首先是n= 5这行代码被执行一次，花费了1个时间单位，下面那行代码也是执行一次，也是花费了1个时间单位，那么总的就是花费两个时间单位，所以它的时间复杂度就是O(1)，怎么样，有没有发现点什么啊
小白： 无论是1个时间单位，还是2个时间单位，他们的时间复杂度始终是O(1)，这是不是意味着，==只要是这些常数个时间单位，时间复杂度始终都是O(1)== 啊
庆哥： 对，很对，也就是说，只要代码的总执行次数是个常数，那么时间复杂度就是O(1)，我们紧接着来看O(n)的是咋回事，看下面这段代码：
public static int test(int n) { int sum = 0; for (int i=0;i<n;i ) { sum= i; } return sum; }
这里有个for循环，我们看看它的时间复杂度怎么计算，首先第一行代码int sum = 0执行一次，花费1个时间单位，重点在下面的for循环这块，因为这里的n是个不确定的值，经过分析，发现for (int i=0;i<n;i )这行代码会执行n 1次，也就是会花费n 1个时间单位，循环体内的sum= 1这行代码则会执行n次，也就是会花费n个时间单位，然后最后一行代码会执行一次，就是花费1个时间单位，总的来说就是：1 n 1 n 1 = 3 2n，也就是总共花费3 2n个时间单位，那么它的时间复杂度就是O(n)。
你看看，觉得这个是规律是啥
小白： 这里得出的总时间单位就像函数一样，比如f(n)=3 2n，不过我们之前喜欢用x，也就是f(x)=3 2x，只不过这里是n，看这里应该是把常数项去除，然后系数也去除，只保留个n，那么如果是f(n)=3 2n^2的话，时间复杂度是不是就是....
是不是就是O(n^2)啊
庆哥： 很聪明啊，确实是这样，这里有个比较官方的解释，也就是按照下面的规则去计算时间复杂度
- 如果运行时间是常数量级，则用常数1表示
- 只保留时间函数中的最高阶项
- 如果最高阶项存在，则省去最高阶项前面的系数
这个明白吧，举个例子，比如f(n)=3 2n^2 5n，那么3就是常数项，5n就是一阶项。2n^2就是二阶项，在这里也是最高阶项，那么按照规则时间复杂度是哈？
小白： 这还是O(n^2)吧
庆哥： 咋样，现在知道怎么计算时间复杂度了吧，你有没有总结什么规律呢？
总结小白： 经过上面那几个例子，我觉得这计算时间复杂度，主要就是看代码中的每一行代码一共执行了多少次，不确定的就是n，然后按照那三条规则来确定最终的时间复杂度，所以重点就是计算每行代码执行了多少次，是不是这样
庆哥： 是的，就可以这样理解，就像你说的重点就是看每行代码一共执行了多少次，不过有些复杂的代码是不容易算出一共执行多少次的，容易算着算着就迷糊了
小白： 哈哈，我也正在思考这个问题呢？咱这里举的例子比较简单，容易计算每行代码执行多少次，但是代码一旦比较绕，比较复杂那就不容易了吧
庆哥： 确实啊，不过随着我们后续的学习，我们会学习一些经常使用的算法，那么这些算法的时间复杂度会直接给出，我们记着就行了，比如我们看看这个图：
这个就是不同时间复杂度的一个函数图，可以简单理解，越陡的花费时间单位越大，那算法性能也就越差，这个我们只要学过数学，一般都能理解吧
小白： 嗯嗯，是的，这个还是能够明白的，你说有些常用算法的时间复杂度是给出的，有哪些呢？
庆哥： 这个啊，我觉得还是随着我们后续的学习去逐步的了解，比如学到哪个算法，需要分析时间复杂度的时候我们再去说，那样我们记忆的才牢固，不然，这里即使和你说了，也会很快忘掉
小白： 嗯嗯，有道理
庆哥： 对了，知道大O表示为啥是n了吧
小白： 嗯嗯 知道了
感谢阅读作者：庆哥小白
,
来源：公众号“编码之外”
链接：https://url.cn/59A7XYT
