So easy 10分钟搞懂时间复杂度和空间复杂度！

📔 一、前言

• 大家好，我是小诚，国庆放假后跟一些小伙伴聊天时发现，大家潜意识里都知道想要进入大厂算法是必须过关的，所以很多人在学校就开始去刷题了，题目虽然刷了许多，但是对于学习算法的初衷和衡量一个算法的指标却是模糊的，所以，博主想写一篇关于学习算法的初衷和算法的指标，帮助准备学习算法或者初学算法的小伙伴将基础巩固。

• 本篇文章重点介绍：算法相关知识的介绍，和衡量算法的指标(时间复杂度和空间复杂度)

• 如果文章对你有帮助，可以帮忙一键三连和专栏订阅哦！

📕 二、专栏推荐

  温馨提醒： 本文适用于所有开发者人群、无论你是小白、初学者还是已经工作的"社会人"。

📗 三、了解算法

3.1、学习算法的必要性

  说明： 必要性就从实际用途方面介绍(至于那些：算法是进入大厂必备的技能这种原因就跳过了)。

  看过我之前博客的小伙伴应该知道，我在很多博文中都有提到一句话，“一个概念或者技术的出现必然是为了解决存在的某个问题”，那算法出现的必要性是因为什么呢，在开发者的世界中有一种说法：能够使用硬件解决的问题就不需要软件解决，这个说法是否正确?，下面来举个例子，让大家有更直观的感受。

  大家都了解计算机中主要的计算组件就是CPU，假设某个问题可以通过两种算法(简称为算法1、算法2)解决，它们的时间复杂度分为O(n)和O(n²)(时间复杂度不懂的没关系，后面会介绍)，假设现在某型号CPU的运算速度提升了100倍，我们分别配置稍微低一点的CPU去跑时间复杂度为O(n)的算法，和使用提升了100倍的CPU去跑时间时间复杂度为O(n²)的算法，我们会发现一个结果：使用配置低的硬件运行的效率要比配置高的硬件效率更好，这是为什么？

  原因就在于算法的复杂度，算法2的复杂度为O(n²)，虽然使用了提升了100倍运算速率的CPU去执行它，但是相对于运行让它运行复杂度的O(n)的算法，它提升的速率实际上仅为10倍。 搭配了提升100倍运算速率CPU的计算机就好好比生活中的小车，搭配了硬件配置较低的计算机就好比生活中的单车，如果单车的速度都比小车快(单单考虑速度方面)，你还会考虑购买小车？毕竟小车的价格是单车的几倍？

  通过上面简单的例子，我们会发现：硬件的速度提升并不是我们不去考虑开发出更高效率应用的借口，作为一名开发者，至少对自己开发的应用要有所标准！所以，开发一个程序时使用更好性能的算法是一名合格程序员应该考虑的因素。

🔵 3.2、何为算法

  上面一小节，我们通过具体的例子解释了学习算法的必要性，那么接下来我们就来认识下什么是算法。

  一、算法：

  并不是什么高深的词汇，可以理解为它就是解决特定问题的办法，在计算机中表现为有限的指令序列，同一个问题有多种解决办法，所以某一个问题的算法并不是唯一的，就好像我们想去旅游，可以乘坐高铁动车、也可以坐飞机。

  同一个问题，不同的算法虽然得到的是相同的结果，但是它们耗费的时间和资源是存在差异的，所以在解决特定问题的时候，我们在多种算法中选出最好的一种。 就好比如果旅游的目的地比较近，可以乘坐高铁，这样可以节省花费，如果比较远，可以考虑乘坐飞机，可以直达，避免中间换乘等时间和金钱的花费。

  那如何才能从多种算法中选择最好的最好的一种呢？想要实现这个目的，那我们需要先了解衡量一个算法好坏的指标是那些，然后再根据这些指标去进行选择。

🟣 3.4、算法的特征

  一、何为真正的算法：

  上一节中提到：算法就是解决某个或者某类问题的办法，但是，这只是对算法的一个笼统的描述。一个真正的算法，包含以下5大特性：输入、输出、有穷性、确定性、可行性。

• 输入输出： 算法具有零个或者多个输入，至少一个或者多个输出。输入可以为零，但是必须存在输出，输出的形式可有为确定的返回值或者日志的的打印等，如果没有输出，那算法的意思在哪里呢？

• 有穷性： 指算法在执行有限的步骤后可以自动结束，不会出现无限的循环，且每个步骤在可以接受的时间完成。注意：这里的有穷性并不是单纯数学上的概念，它指的是一个可以接收的“边界”，如存在某种算法运行几年后可以得出结果，理论上也是符合有穷性。

• 确定性： 算法的每一个步骤都是具有确定的意义，不会出现歧义，相同的输入必须得到相同的输出。

• 可行性： 算法中每一步都可以转换成程序在计算机上运行，它意味着算法中的设计是可行的，但是并不意味着一定得到正确的结果。

  二、好算法有哪些评判标准：

  上一节我们介绍了一个算法具有的哪些特征，但是算法也分好坏，好的算法效率高，就好比“移山”，如果在古代可能只能用人力去挖，现代的话可以使用各种炸药、自动化设备去处理，不仅效率更高，安全性也更好，那么，衡量一个算法好坏有哪些标准呢？下面具体来看看吧！

  2.1、正确性：

  正确性：要求算法应该有输入、输出和执行无歧义，能够正确反映问题的具体需求，通过算法能够得到解决问题的正确答案。

  2.1.1、“正确性”算法的四个层次

  （1）算法程序没有语法错误

  （2）算法程序对合法的输入能够得到满足要求的输出

  （3）算法程序对非法的输入能够得到满足规格的输出

  （4）算法程序对故意刁难的测试数据能够得到满足要求的输出

  对于算法的第4层次，基本不可能实现将所有的输入逐一验证，所以算法的正确性一般只要满足到第3层次即可。

  2.2、可读性：

  一个好的算法设计，应该是方便大家阅读、理解和交流的，如果为了追求某些方面的特性，导致算法不易于人们理解，那这样的算法不能称为好的算法，因为人们无法轻易读懂它，导致难以修改和调试，即使算法中存在问题也不能轻易发现，最后可能算法的设计者在时间久远后也很难理解它。

  2.3、健壮性：

  好的算法应该对不合理的输入做到适当的处理(提示等)，而不是产生让使用者也无法理解的异常或者莫名其妙的结果。

  健壮性定义： 算法的输入数据不合法时，算法能够做出相应的适当处理，而不是产生难以理解的异常或者莫名其妙的结果。

  2.4、时间效率高和存储量低：

  算法也是来源生活，生活中我们都希望花最少的钱办最多的事，算法也是一样，能够占用最小的空间，最快的得到结果那就是一个好的算法。

  时间效率高： 指的是通过算法设计的程序执行的时间短，一个问题存在着多种算法可以解决，使用时间最短的那个时间效率最高。

  存储量低： 存储量是指实现算法的存储在运行时占用最大的存储空间，程序运行占用的空间越小，证明运行程序需求的资源越小，算法就越好(存储空间一般是指：内存或者硬盘等设备的存储空间)。

🟡 3.4、算法和程序的区别

  有些小伙伴可能会将算法和程序两者的概念混淆，其实它们两者是不同的概念。算法表示的是解决某个或某类问题的思路、想法。程序是根据某一个特定算法编写出来可以被计算机运行的代码。

  就比如我需要输出1到100范围内的所有数值，我们会考虑到使用循环语句输出，使用循环语句输出这个思路就可以说是算法，然后实际上根据这个思路编写出来的代码就可以称为程序。

📘 四、算法效率的度量方法

  通过上文的介绍，大家已经对算法有了初步的了解，但是，实际情况如何衡量一个算法的好坏呢，相信现在大家心里都还是存在着这个疑惑的，下面就来看看有哪些度量方法吧！

🔶 4.1、事后统计方法

  定义：不同的算法设计出不同的测试程序进行测试，然后统计计算机计时器在不同测试程序运行的时间进行比较，从而确定算法效率的高低。

  1.1、事后统计方法存在的问题

  1、某个问题或某类问题可以存在多种算法解决，如果每种算法都编写测试程序需要花费大量的时间和精力。

  2、运行效率依赖于计算硬件和软件等环境因素，不同的硬件和软件有可能会掩盖了算法存在的问题，导致测试出来的结果不准确。

  3、测试数据设计准备困难，程序的运行效率往往和测试数据的规模有关，如果测试数据太小，以现在CPU的运算速度，根本看不出差异，选择多大的测试数据规模，测试多少次才能够得到比较准确的结果等，这些问题都是很难进行判断的。

  1.2、事后统计方法结论

  基于事后统计方式存在的缺陷，这种算法效率的度量方式是不推荐使用的。

🔷 4.2、事前统计方法

  定义：在进行算法程序编写前，依据统计方法对算法进行估算，得到算法程序运行的预估值。 计算机的前辈们经过分析发现，通过高级程序语言编写的程序在计算机运行时消耗的时间取决于下面的几个因素：

  通过上面的图片可以发现，因素2取决于软件的支持，因素4取决于运行程序的硬件，抛开软件、硬件有关的因素，一个程序的运行效率，依赖于算法的好坏和问题的输入规模(即输入量的多少)。

  下面我们通过求和的两种算法来实际分析与程序的运行时间相关的具体因素：

  算法一：累加求和


java
int i,sum=0,n=100; // 执行1次
for(i=1;i<n;i++){
sum = sum + i; // 执行n次
}
System.out.println(“sum=”+sum); // 执行1次

  算法二：高斯算法

java
int i,sum=0,n=100; // 执行1次
sum = (1 + n) * n / 2; // 执行1次
System.out.println(“sum=”+sum); // 执行1次

  通过上面求和的两个算法我们会发现，如果将头尾变量定义和循环判断等开销忽略，实际上两种算法就是运行n次和1次的区别，随着n的数值越大，它们之间运行的次数差距也越大，程序花费的时间差距也越大，因此，我们可以得出一下的一个结论：

  测定运行时间最可靠的方法，就是计算对运行时间有消耗的基本操作的执行次数，运行时间和这个计数成正比。

  结论：

  对于输入规模为n，第一种求和算法中，求和操作 sum = sum+ i 代码需要被运行n次，我们可以说这个问题的输入规模n使得程序的操作数量是：f(n) = n

  对于输入规模为n，第二种算法中求和代码：sum = (1 + n) * n / 2 始终只需要执行一次，那么我们可以说这个问题的输入规模为n使得程序的执行数量是：f(n) = 1

  因此，在进行分析一个算法的运行时间时，我们需要将输入规模和程序的基本操作数量进行关联起来即将基本操作数量表示成输入规模的函数，如下图所示：

📙 五、时间复杂度和空间复杂度

🟧 5.1、时间复杂度

  在数据结构中，使用时间复杂度来衡量程序运行时间的多少。每条语句执行的次数称为该语句的频度，整段代码的总执行次数则称为整段代码的频度。

  定义：在算法估算时，语句的执行次数T(n)是关于问题规模n的函数，从而分析T(n)随着n的变化的关系。算法的时间复杂度也称为算法的时间量度，记作T(n) = O(f(n))，它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度，其中f(n)是问题规模n的某个函数。

  刚开始看上面的定义多少有些迷惑，但是多读几次结合上文的知识串起来后，你会其实并没有这么复杂，时间复杂度其实可以理解为随着问题规模n的增大，程序语句执行频度的增长率。

  在定义中我们使用到O()的方式来体现算法时间复杂度的记法，这种方式又称为大O记法。一般情况下，随着问题规模n的增大，T(n)即语句执行次数增长最慢的算法为最优算法，讲简单点，就是无论你输入规模如何变化，只要执行的语句次数增长最小，那这种算法就是最优的。

  了解算法时间复杂度的定义，那么如何分析一个算法的时间复杂度呢(即如何推到大O阶呢)?没错，经过前辈们的经验，这个也是有相应的推导公式的，在推导的时候我们应该采用无限大的思想来简化大O表达式，具体如下：

• 用常数1代替运行时间中的所有加法的常数，如：某个算法的执行函数为f(n) = 10，则替换成大O阶方法的话则为：O(1)，无论这个常数为10，还是100，还是1000都使用1替换，因为执行函数和问题规模n的大小无关，它是执行时间恒定的，像时间复杂度为O(1)的又被称作常数阶。

• 如果表达式有多项含有无限大变量的式子，只保留一个拥有指数最高的变量的式子。例如 2n²+2n 简化为 2n²；

• 如果最高阶项存在且系数不为1，则去除掉与这个项相乘的系数，例如 2n² 系数为 2，直接简化为 n² ；

  经过上面三个步骤推到出来的结果就是算法对应的大O阶。

  对算法的时间量度，存在两种方式。 一种是计算所有情况的平均值，这种时间复杂度的计算方法称为平均时间复杂度。另一种情况则为计算最坏情况下的时间复杂度，这种也称为最坏时间复杂度，一般没有特殊说明的情况下，指的都是最坏时间复杂度。

🟨 5.2、常见的时间复杂度例子

  一、常数阶

java
int i,sum=0,n=100; // 执行1次
sum = (1 + n) * n / 2; // 执行1次
System.out.println(“sum=”+sum); // 执行1次

  这个算法就是上面我们举例到的高斯算法，程序的执行次数函数为f(n) = 3，根据大O阶方法的推导方式，则得到的时间复杂度为：O(1)，而不是O(3)，注意：因为执行函数并不会随着n的变化而变化，它是恒定的，像复杂度为O(1)，又被称作常数阶。

  二、线性阶

java
int i,sum=0,n=100; // 执行1次
for(i=1;i<n;i++){
sum = sum + i; // 执行n次
}
System.out.println(“sum=”+sum); // 执行1次

  根据上面的代码，我们可以发现执行次数函数为f(n) = n，根据大O阶方法的推导方式得到它的时间复杂度表示为：O(n)。 像这种线性阶，我们主要分析的是循环结构中的一个运行情况，从而得到它的时间复杂度。

  三、对数阶

java
int condition = 1;
while(condition < n){
condition = condition * 2;
}

  根据上面的代码，我们会发现循环语句的条件会在每次condition乘以2后更加接近跳出条件，既满足多少个与2的乘积后将会退出循环，因此我们可以得到执行次数的函数为：f(n) => 2^x^ = n ===> x = log~2~n，根据大O阶方法的推导方式得到它的时间复杂度表示O(logn)。

  四、平方阶

java
for(int i=o;i<n;i++){
for(int j=o;j<n;i++){
…
}
}

  根据代码分析，我们可以得到执行次数的函数为: f(n) = n^2^，根据大O阶方法的推导方式得到它的时间复杂度表示O(n^2^)。

  五、常见的时间复杂度耗费时间比较

  O(1) < O(logn) < O(n) < O(nlogn) < O(n^2^) < O(n^3^) < O(2^n^ ) < O(n!) < O(n^n^)

🟦 5.3、空间复杂度

  在数据结构中，用空间复杂度来衡量程序运行所需内存空间的大小，跟时间复杂度类似，它也可以使用大O记法来表示。

  算法的空间复杂度是通过计算算法所需的存储空间实现的，计算公式为：S(n) = O(f(n))，其中n为问题的规模，f(n)则为语句关于问题规模n所占存储空间的函数，随着n的变动，f(n)的增长率越小越好。

  一个算法程序从编译到运行有多个部分涉及存储空间的分配，具体情况如下：

• 程序代码本身需要占用一部分存储空间，用于存储编译后提供执行的代码，这部分的存储空间主要取决于程序的代码量，因此，为了减少这部分占用的空间，在保证算法的合理性情况下，应该尽量减少代码量。

• 程序中的输入输出，也需要占用一部分存储空间，这部分的占用的空间主要取决于不同算法的实现逻辑，但是大体上它们的大小都是相差不大的。

• 程序在运行时，不同情况下需要申请的临时空间，这部分占用的空间是对空间复杂度影响最大的，因为不同的算法实现细节可能存在较大的差异，会申请的空间也会存在比较大的不同。

  一、常见的空间复杂度可以归类为以下的几种情况：

• 如果算法执行时所需要的空间和算法的输入值无关，对于输入数据量来说是一个常数的话，则称该算法为 原地工作 空间复杂度为O(1)。

• 如果随着输入数据量 n 的增大，程序申请的临时空间成线性增长，则程序的空间复杂度用 O(n) 表示。

• 如果随着输入数据量 n 的增大，程序申请的临时空间成 n^2^ 关系增长，则程序的空间复杂度用 O(n2) 表示。

• 如果随着输入数据量 n 的增大，程序申请的临时空间成 n^3^ 关系增长，则程序的空间复杂度用 O(n3) 表示。

• 等等(和时间复杂度的推送逻辑类似)

  坚持阅读到此处的小伙伴，恭喜你，在算法方面已经初步入门了，接下来就是需要多次阅读，将文章中没有理解清楚的概念搞清楚，然后再结合具体的算法(leetcode网站)进行实战，有了理论知识的支撑，相信你实战的脚本会更加快捷。

📜 六、参考资料

  《大话数据结构》

  说明： CSDN中，该书籍仅供会员在线阅读，无法下载，所以博主正在找电子版同步到【技术圈子】中，有需要的小伙伴关注【IT学习日记】进入【技术圈子】。

🚀 七、写在最后

  也许大家看完文章后会还是存在些许疑惑，这个是非常正常的，解决办法就是将不理解的概念整理出来，多看几遍，你会有不同的领悟，算法的学习对每一位有自我要求的开发者来说应该都是必须的，如果读完后还是存在疑惑，欢迎私信博主或者进入【技术圈子】提问。

  推荐一下： 【技术圈子】目的是为了搭建共享资源平台，因为很多人寻找资源路径有限，但是人多力量大，将它们整理起来寻找资源的方式就多了，也更容易了。

  如果文章对你有帮助，请帮忙点击"一键三连" 和 “专栏订阅”，感谢您的支持！期待下一篇文章继续看到你的身影！