算法（Algorithm）是指用来操作数据、解决程序问题的一组方法。算法是大厂、外企面试的必备项，也是每个高级程序员的必备技能。针对同一问题，可以有很多种算法来解决，但不同的算法在效率和占用存储空间上的区别可能会很大。
那么，通过什么指标来衡量算法的优劣呢？其中，上面提到的效率可以用算法的时间复杂度来描述，而所占用的存储空间可以用算法的空间复杂度来描述。
- 时间复杂度：用于评估执行程序所消耗的时间，可以估算出程序对处理器的使用程度。
- 空间复杂度：用于评估执行程序所占用的内存空间，可以估算出程序对计算机内存的使用程度。
在实践中或面试中，我们不仅要能够写出具体的算法来，还要了解算法的时间复杂度和空间复杂度，这样才能够评估出算法的优劣。当时间复杂度和空间复杂度无法同时满足时，还需要从中选取一个平衡点。
一个算法通常存在最好、平均、最坏三种情况，我们一般关注的是最坏情况。最坏情况是算法运行时间的上界，对于某些算法来说，最坏情况出现的比较频繁，也意味着平均情况和最坏情况一样差。
通常，时间复杂度要比空间复杂度更容易出问题，更多研究的是时间复杂度，面试中如果没有特殊说明，讲的也是时间复杂度。
时间复杂度
要获得算法的时间复杂度，最直观的想法是把算法程序运行一遍，自然可以获得。但实践中往往受限于测试环境、数据规模等因素，直接测试算法要么难以实现，要么误差较大，而且理论上也没必要对每个算法都进行一遍测试，只需要找到一种评估指标，获得算法执行所消耗时间的基本趋势即可。
时间频度
通常，一个算法所花费的时间与代码语句执行的次数成正比，算法执行语句越多，消耗的时间也就越多。我们把一个算法中的语句执行次数称为时间频度，记作T(n)。
渐进时间复杂度
在时间频度T(n)中，n代表着问题的规模，当n不断变化时，T(n)也会不断地随之变化。那么，如果我们想知道T(n)随着n变化时会呈现出什么样的规律，那么就需要引入时间复杂度的概念。
一般情况下，算法基本操作的重复执行次数为问题规模n的某个函数，也就是用时间频度T(n)表示。如果存在某个函数f(n)，使得当n趋于无穷大时，T(n)/f(n)的极限值是不为零的常数，那么f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称为时间复杂度。
渐进时间复杂度用大写O表示，所以也称作大O表示法。算法的时间复杂度函数为：T(n)=O(f(n))；
T(n)=O(f(n))表示存在一个常数C，使得在当n趋于正无穷时总有 T(n) ≤ C * f(n)。简单来说，就是T(n)在n趋于正无穷时最大也就跟f(n)差不多大。也就是说当n趋于正无穷时T(n)的上界是C * f(n)。其虽然对f(n)没有规定，但是一般都是取尽可能简单的函数。
常见的时间复杂度有：O(1)常数型；O(log n)对数型，O(n)线性型，O(nlog n)线性对数型，O(n2)平方型，O(n3)立方型，O(nk)k次方型，O(2n)指数型。
上图为不同类型的函数的增长趋势图，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log n)＜Ο(n)＜Ο(nlog n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2^n)＜Ο(n!)。
值得留意的是，算法复杂度只是描述算法的增长趋势，并不能说一个算法一定比另外一个算法高效。这要添加上问题规模n的范围，在一定问题规范范围之前某一算法比另外一算法高效，而过了一个阈值之后，情况可能就相反了，通过上图我们可以明显看到这一点。这也就是为什么我们在实践的过程中得出的结论可能上面算法的排序相反的原因。
如何推导时间复杂度
上面我们了解了时间复杂度的基本概念及表达式，那么实践中我们怎么样才能通过代码获得对应的表达式呢？这就涉及到求解算法复杂度。
求解算法复杂度一般分以下几个步骤：
- 找出算法中的基本语句：算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体。
- 计算基本语句的执行次数的数量级：只需计算基本语句执行次数的数量级，即只要保证函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，使注意力集中在最重要的一点上：增长率。
- 用大Ο表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。
其中用大O表示法通常有三种规则：
- 用常数1取代运行时间中的所有加法常数；
- 只保留时间函数中的最高阶项；
- 如果最高阶项存在，则省去最高阶项前面的系数；
下面通过具体的实例来说明以上的推断步骤和规则。
时间复杂度实例
常数阶O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：
int i = 1;
int j = 2;
int k = 1 + 2;上述代码执行时，单个语句的频度均为1，不会随着问题规模n的变化而变化。因此，算法时间复杂度为常数阶，记作T(n)=O(1)。这里我们需要注意的是，即便上述代码有成千上万行，只要执行算法的时间不会随着问题规模n的增长而增长，那么执行时间只不过是一个比较大的常数而已。此类算法的时间复杂度均为O(1)。
对数阶O(log n)
先来看对应的示例代码：
int i = 1; // ①
while (i <= n) {
i = i * 2; // ②
}在上述代码中，语句①的频度为1，可以忽略不计。
语句②我们可以看到它是以2的倍数来逼近n，每次都乘以2。如果用公式表示就是122*2…*2 <=n，也就是说2的x次方小于等于n时会执行循环体，记作2^x <= n，于是得出x<=logn。也就是说上述循环在执行logn次之后，便结束了，因此上述代码的时间复杂度为O(log n)。
其实上面代码的时间复杂度公式如果精确的来讲应该是：T(n) = 1 + O(log n)，但我们上面已经讲到对应的原则，“只保留时间函数中的最高阶项”，因此记作O(log n)。
线性阶O(n)
示例代码：
int j = 0; // ①
for (int i = 0; i < n; i++) { // ②
j = i; // ③
j++; // ④
}上述代码中，语句①的频度为1，②的频度为n，③的频度为n-1，④的频度为n-1，因此整个算法可以用公式T(n)=1+n+(n-1)+(n-1)来表示。进而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1，即O(n)=3n-1，去掉低次幂和系数即O(n)=n，因此T(n)=O(n)。
在上述代码中for循环中的代码会执行n遍，因此它消耗的时间是随着n的变化而成线性变化的，因此这类算法都可以用O(n)来表示时间复杂度。
线性对数阶O(nlogN)
示例代码：
for (int m = 1; m < n; m++) {
int i = 1; // ①
while (i <= n) {
i = i * 2; // ②
}
}线性对数阶要对照对数阶 O(log n)来进行理解。上述代码中for循环内部的代码便是上面讲到对数阶，只不过在对数阶的外面套了一个n次的循环，当然，它的时间复杂度就是n*O(log n)了，于是记作O(nlog n)。
平方阶O(n²)
示例代码：
int k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
k++;
}
}平方阶可对照线性阶来进行理解，我们知道线性阶是一层for循环，记作O(n)，此时等于又嵌套了一层for循环，那么便是n * O(n)，也就是O(n * n)，即O(n^2)。
如果将外层循环中的n改为m，即：
int k = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
k++;
}
}那么，对应的时间复杂度便为：O(m * n)。
同理，立方阶O(n³)、K次方阶O(n^k)，只不过是嵌套了3层循环、k层循环而已。
排序算法对比
上面介绍了各种示例算法的时间复杂度推理过程，对照上面的时间复杂度以及算法效率的大小，来看一下我们常见的针对排序的几种算法的时间复杂度对比。
空间复杂度
最后，我们再了解一下空间复杂度。空间复杂度主要指执行算法所需内存的大小，用于对程序运行过程中所需要的临时存储空间的度量，这里的空间复杂度同样是预估的。
程序执行除了需要存储空间、指令、常数、变量和输入数据外，还包括对数据进行操作的工作单元和存储计算所需信息的辅助空间。存储空间通常包括：指令空间（即代码空间）、数据空间（常量、简单变量）等所占的固定部分和动态分配、递归栈所需的可变空间。其中可变空间与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))其中n为问题的规模，S(n)表示空间复杂度。
下面看两个常见的空间复杂度示例：空间复杂度O(1)和O(n)。
空间复杂度 O(1)
空间复杂度为O(1)的情况的示例代码与时间复杂度为O(1)的实例代码一致：
int i = 1;
int j = 2;
int k = 1 + 2;
上述代码中临时空间并不会随着n的变化而变化，因此空间复杂度为O(1)。总结一下就是：如果算法执行所需要的临时空间不随着某个变量n的大小而变化，此算法空间复杂度为一个常量，可表示为 O(1)，即 S(n) = O(1)。
空间复杂度 O(n)
示例代码：
int j = 0;
int[] m = new int[n];
for (int i = 1; i <= n; ++i) {
j = i;
j++;
}上述代码中，只有创建int数组分配空间时与n的大小有关，而for循环内没有再分配新的空间，因此，对应的空间复杂度为S(n) = O(n)。
总结一下
本篇文章给大家讲了可以通过时间复杂度和空间复杂度来衡量算法的优劣，同时用具体的实例来讲解如何计算不同方法的时间复杂度和空间复杂度。当我们了解了这些基本的概念、函数、计算方法、计算规则及算法性能之后，再进行算法的学习便可以轻松预估出算法的性能等指标。
参考文献：
https://blog.csdn.net/zolalad/article/details/11848739 https://zhuanlan.zhihu.com/p/50479555
前言
作为一名“程序猿”，大家应该都听过这么一句话：程序=数据结构+算法。
这句话是由瑞士计算机科学家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年获得图灵奖时说的一句话，这位大佬还以这句话为名出了一本书《Algorithms + Data Structures=Programs》，从此这句话就成为了大家耳熟能详的一句名言。
随着时间的推移，不管这句话是不是非常准确，但至少能说明数据结构与算法对程序来说是非常核心的基础，如果我们想要写出更多优秀优雅的代码，那么数据结构与算法是必须要掌握好的。
为什么要学习算法
很多人可能觉得，我不会算法，代码一样写得很"溜"，算法这东西似乎用处不大。现在互联网的发达，我们想要什么几乎都可以在网上找到现成的，各种框架功能十分强大，似乎看起来确实不用算法也可以写出“好代码”。然而假如我们不懂算法，比如项目中用到了排序，我们如何评估代码的执行效率？再比如最常用的 ArrayList 和 LinkedList，我们该如何选择，又比如说我们需要去集合中找某一个数，又该如何写出性能优秀的代码呢？
同样的代码，如何判断谁的代码是优秀的代码？可读性，可扩展性，健壮性可能都可以用来判定，然而这些东西我觉得并不能直接体现出你代码的优秀，因为对用户而言，访问你的代码响应速度快那就是优秀的代码，相反，动辄响应几秒甚至更长时间的接口，恐怕就算你可读性再好，再健壮也称不上是好代码。
所以说一段代码是否优秀，最直接的判断标准就是性能，而如果要写出高性能的代码，那么就必须要了解算法，而且抛开这个因素，但凡不想一辈子都写 CRUD 代码的，也需要去了解算法，我们使用的很多框架和中间件底层都有数据结构和算法的身影，学好算法对我们源码阅读时理解其设计思想也是大有裨益的。
要说功利性的目的，那就是面试，目前很多大厂的面试，算法基本必面，所以想进大厂的话，咱们也得好好学学算法。
算法难学吗
提到算法，很多人的第一反应就是太难学了，学不会，或者说经常是看完就忘了，但是其实对于我们一个普通的开发者而言，因为并不需要我们去发明算法，我们需要的仅仅只是去灵活的运用算法，所以并不需要非常扎实的数据基础，当然基本的数学常识还是要有的。
如果说需要去发明设计一款算法，那就要去推导去证明算法的可行性，这种是需要具有非常扎实的数学基础的，一般人确实无法做到，然而我们普通程序员口中提到算法无非是二分查找法，哈希算法等，高级一点的就还有回溯，贪心，动态规划等等，这些所谓的算法都是已经有现成的公式了，我们要做的无非就是理解它，然后灵活的运用它。这就和我们以前学习数学公式一样，给你一个公式，然后你去做题，做题的过程其实就是去灵活的运用这个公式。
算法也是同理，都是有特定方法和特定思路的，我们也并不需要去推导证明这种方式为什么可行，所以学习算法没有其他诀窍，就是先理解思路，然后多练，等熟练了，自然就可以灵活运用了，也不会说学了立刻就忘了。学完就忘无非两个原因，一是没理解，而是没有练习巩固。
复杂度分析
数据结构与算法经常是放在一起讲，这两者是没办法独立的，因为算法是为了达到某种目的的一种实现方式，而数据结构是一种载体，也就是说算法必须依赖数据结构这种载体，否则就是空谈。换句话说：数据结构是为算法服务的，而算法又需要作用在特定的数据结构之上。
一个算法到底好不好，我们如何去评价？前面我们提到了，你的代码好不好，最直观的就是看响应速度，算法也一样，同样实现一个目的（比如说排序），谁的算法速度快，我们就可以认为谁的算法更优，如果说两种算法实现的速度差不多，那么我们还可以去评价算法所占用的空间，谁占用的空间少，那么就可以认为谁的算法更优，这就是算法的基础：时间复杂度和空间复杂度。
学习算法之前，我们必须要学会如何分析时间复杂度和空间复杂度（也就是“快”和“省”），否则自己写出来的算法自己都不知道算法的效率。
时间复杂度大 O表示法
接触过算法的都知道，算法的时间复杂度是用大写的“O”来表示的，比如：O(1)，O(n)，O(logn)，O(nlogn)，O(n²) 等等。
时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系，上面的这种时间复杂度表示法并不能真正反应一个算法的执行时间，反应的只是一个趋势，所以我们在分析复杂度的时候要关注“变”，忽略“不变”。
变指的是变量，也就是一段代码的执行时间是随着变量的变化而变化的，而不变指的是常量，也就是不论我的变量如何改变，执行时间都不会改变。
接下来我们就实际的来分析下常用时间复杂度的例子来练习一下。
O(1) 常数阶
0(1) 复杂度算法也称之为常数阶算法。这里的 1 是用来代指常量，也就是说这个算法的效率是固定的，无论你的数据量如何变化，效率都一样，这种复杂度也是最优的一种算法。
public static void print(int n){
int a = 1;
int b = 2;
int c = 3;
int sum = a + b + c;
System.out.println(sum);
}
上面的示例中不论有多少行代码，时间复杂度都是属于常数阶。换言之：只要代码不存在循环，递归等循环类调用，不论代码有多少行，其复杂度都是常数阶。
O(n) 线性阶
O(n) 复杂度算法也称之为线性阶。比如下面这个示例我们应该怎么分析复杂度呢？
public static void print1(int n){
int a = 0;
for (int i=0;i<n;i++){
System.out.println(i);
}
}
前面常量阶没分析是因为常量阶比较容易理解，接下来我们就以线性阶这个为例子来分析下具体是怎么得到的。
我们假设每一行代码的执行时间是 T，那么上面这段代码的执行复杂度是多少呢？
答案很明显，那就是 T+n*T，也就是 (n+1)T，而在算法中有一个原则，那就是常量可以被忽略，所以就得到了 nT，换成大 O 表示法就是 O(n)。
这只是一个简略的计算过程，大家也不用较真说每行代码执行时间可能不一样之类的，也不要较真说 for 循环占用了一行，下面的大括号也占用了一行，如果要较真这个，那我建议可以去想一下 1=1 为什么等于 2。
算法中的复杂度反应的只是一个趋势，这里 O(n) 反应的就是一个趋势，也就是随着 n 的变化，算法的执行时间是会降低的。
O(n²) 平方阶
知道了上面的线性阶，那么平方阶就很好理解了，双层循环就是平方阶，同理，三次循环就是立方阶，k 次循环就是 k 次方阶。
O(logn) 对数阶
O(logn) 也称之为对数阶，对数阶也很常见，像二分查找，二叉树之类的问题中会见到比较多的对数阶复杂度，但是对数阶也是比较难理解的一种算法复杂度。
下面我们还是来看一个例子：
public static void print2(int n){
int i=1;
while (i <= n) {
i = i * 2;
}
}
这段代码又该如何分析复杂度呢？这段代码最关键就是要分析出 while 循环中到底循环了多少次，我们观察这个循环，发现 i 并不是逐一递增，而是不断的翻倍：1->2->4->8->16->32->64 一直到等于 n 为止才会结束，所以我们得到了这样的一个公式：2^x=n。
也就是我们只要计算出 x 的值，就得到了循环次数，而根据高中的数学知识我们可以得到 x=log2n（2 在下面，是底数，试了几种方法都打不出来，放弃了），所以根据上面线性阶的分析方法，我们省略常量，就得到了示例中的算法复杂度为 O(log2n)。
同样的分析方式，下面的例子，我们可以很快的分析出复杂度就为 O(log3n)：
int i=1;
while (i <= n) {
i = i * 3;
}
上面得到的 log3n 我们可以再做进一步的转换：log3n=log32 * log2n，而 log32（注意这几个地方的 3 是底数，在下面） 是一个常量，常量可以省略，所以也就得到了：O(log3n)=O(log2n)。同样的道理，不论底数是多少，其实最终都可以转化成和 O(log2n) 相等，正因为如此，为了方便，我们算法中通常就会省略底数，直接写作 O(logn)。
上面的数学公式大家如果忘了或者看不懂也没关系，只要记住不论对数的底数是多少，我们都算作 O(logn)，而对于一个算法的复杂度是否是对数阶，还有一个简易的判断方法：当循环中下标以指定倍数形式衰减，那么这就是一个对数阶。
O(nlogn) 线性对数阶
如果理解了上面的对数阶，那么这种线性对数阶就非常好理解了，只需要在对数阶的算法中再嵌一层循环就是线性对数阶：
for (int j=1;j<=n;j++){
int i=1;
while (i <= n) {
i = i * 2;
}
}
分析了前面这些最常用的时间复杂度，其实我们可以得到以下规律：
- 只要是常量级别，不论多大，效率都是一样的（如：常量阶复杂度例子）。
- 分析一段代码的时间复杂度，只需要分析执行次数最多的一段代码（如：所以例子中我们只分析了循环体中代码执行次数）。
- 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积（如：分析线性对数阶复杂度例子）。
其他复杂度
除了上面常用的复杂度之外，另外还有指数阶，阶层阶，根号阶等，这些接触的相对会较少，我们就不特意做分析了，如果大家感兴趣的话，可以自己去了解下。
组合式复杂度分析
前面我们分析的都是只有一段代码比较复杂的情况下得到的复杂度结果，那么假如我一个算法中，有多段代码都比较复杂呢？这时候复杂度该如何分析？
取最大复杂度作为整个算法复杂度
我们先看下面这个例子：
public static void print1(int n){
for (int i=0;i<1000;i++){
System.out.println(i);
}
for (int j=0;j<n;j++){
System.out.println(j);
}
for (int p=0;p<n;p++){
for (int q=0;q<n;q++){
System.out.println(p+q);
}
}
}
这个例子中有三个循环，首先第一个，是一个常量，那么根据前面的结论，不论这个常量是多大，都属于常量级，所以第一个循环中的复杂度为 O(1)，第二个和第三个循环我们前面也分析过，复杂度分别为 O(n) 和 O(n²)。
也就是这一段代码中有三段代码产生了三种不同复杂度，而且这三个复杂度可以很明显得到的大小关系为：O(1)<O(n)<O(n²)，像这种在同一个算法中有明确大小关系的，我们就可以直接取最大值作为这个算法的复杂度，所以这个例子中算法的复杂度就是 O(n²)。
取多个复杂度之和作为整个算法复杂度
接下来我们再来看一个例子：
public static void print2(int m,int n){
for (int i=0;i<1000;i++){
System.out.println(i);
}
for (int j=0;j<m;j++){
System.out.println(j);
}
for (int k=0;k<n;k++){
System.out.println(k);
}
}
这个例子我们同样对三段循环分别分析可以分别得到如下复杂度：O(1)，O(m)，O(n)。这时候我们只能知道 O(1) 最小可以忽略，但是后面两个无法却无法确定大小，所以这时候我们需要取两段循环复杂度之和来作为算法的复杂度，所以可以得到这个例子的算法复杂度为：O(m+n)。
时间复杂度类型
上面分析的时间复杂度都是比较简单的，实际算法中可能会比示例中复杂的多，而且我们示例中只要是循环都是无脑循环，也就是一定从头循环到尾，然而实际中我们有时候并不需要从头循环到尾，可能中途就会结束循环，所以我们根据实际情况，又可以将时间复杂度从以下四个方面来进一步分析：
- 最好时间复杂度
- 最坏时间复杂度
- 平均时间复杂度
- 均摊时间复杂度
这四种类型的时间复杂度在这里只会介绍前面三种，因为第四种比较复杂，而且使用场景也非常有限，而且对于这四种复杂度的分析，大家也作为了解就可以，不敢兴趣的朋友们可以跳过这一小部分，因为在绝大部分情况我们只需要分析最坏复杂度就行，也就是假设循环全部执行完毕场景下的时间复杂度。
最好时间复杂度
我们通过一个例子来理解下最好时间复杂度：
public static int findEle(int[] arr,int val){
if (null == arr || arr.length == 0){
return -1;
}
for (int i=0;i<arr.length;i++){
if (arr[i] == val){
return i;
}
}
return -1;
}
这个方法就是在一个指定数组中找到指定元素的下标，找不到就返回 -1，这个方法比较简单，应该比较好理解。
注意这个方法中的循环体，如果找到元素，那么就直接返回，这就会有一个现象，那就是我这个循环体到底会循环多少次是不确定的，可能是 1 次，也可能是 n（假设数组的长度） 次，所以假如我们要找的元素就在数组中的第一个位置，那么我循环一次就找到了，这个算法的复杂度就是 O(1)，这就是最好情况时间复杂度。
最坏时间复杂度
理解了最好时间复杂度，那么最坏时间复杂度也很好理解了，那就是数组中不存在我要找到元素，或者说最后一个值才是我要找的元素，那么这样我就必须循环完整个数组，那么时间复杂度就是 O(n)，这也就是最坏时间复杂度。
平均时间复杂度
最好时间复杂度和最坏时间复杂度毕竟只有特殊情况才会发生，概率还是相对较小，所以我们很容易就想到我们也需要有一个平均时间复杂度。
我们简单的来分析一下，为了便于分析，我们假设一个元素在数组和不在数组中的概率都为 1/2，然后假如在数组在，那么又假设元素出现在每个位置的概率也是一样的，也就是每个位置出现元素的概率为： 1/n。
所以最终得到的平均时间复杂度应该等于元素在数组中和元素不在数组中两种情况相加。
- 元素在数组中的复杂度
因为元素在数组中的概率为 1/2，然后在每个位置出现的概率也为 1/n。假如元素出现在第一个位置，复杂度为 1*(1/2n)；假如元素出现在第二个位置，复杂度为 2 * (1/2n)，最终得到当前场景下时间复杂度为：1*(1/2n) + 2 * (1/2n) + ... + n*(1/2n)=(n+1)/4。
- 元素不在数组中的复杂度
前面已经假定了元素不在数组中的概率为 1/2，所以当前场景下的时间复杂度为：n * (1/2)，因为元素不在数组中，那么这个算法必然会将整个循环执行完毕，也就循环是 n 次。
最后我们把两种情况的复杂度之和相加就得到了平均时间复杂度：(n+1)/4 + n/2 = (3n+1)/4，最终我们将常数类的系数忽略掉，就得到了平均时间复杂度为 O(n)。
均摊时间复杂度
均摊时间复杂度的算法需要使用摊还分析法，计算方式相对有点复杂，而且使用场景很有限，本文就不做过多介绍了。
空间复杂度
空间复杂度全称就是渐进空间复杂度，用来表示算法的存储空间与数据规模之间的增长关系。和时间复杂度一样，空间复杂度也是用大 O 进行表示。
其实学会了分析时间复杂度，那么空间复杂度的分析就简单了，主要就看我们在一个算法当中到底有没有使用到了额外的空间来进行存储数据，然后判断这个额外空间的大小会不会随着 n 的变化而变化，从而得到空间复杂度。
我们来看一个给数组赋值例子，假设这就是一个算法，我们可以来分析下这个算法的空间复杂度：
public static void init(int n){
int a = 0;
int arr[] = new int[n];
for (int i=0;i<n;i++){
arr[i]=n;
}
}
一开始定义了一个变量，这里需要空间，但是这是一个常量级的（不随 n 的变化而变化），然后再定义了一个数组，数组的长度为 n，这里数组也需要占用空间，而且数组的空间是随着 n 的变化而变化的，其余代码没有占用额外空间，所以我们就可以认为上面示例中的空间复杂度为 O(n)。
对于算法的空间复杂度也可以简单的进行总结一下：
- 如果申请的是有限个数（常量）的变量，空间复杂度为
O(1)。 - 如果申请的是一维数组，队列或者链表等，那么空间复杂度为
O(n)。 - 如果申请的是二维数组，那么空间复杂度为
O(n²)。 - 如果是在循环体中申请的数组等，可能就需要取嵌套的乘积来作为空间复杂度，这种就需要具体的进一步分析。
总结
本文主要讲述了为什么要学习算法，也简单减少了数据结构与算法之间的关系，随后主要介绍了算法中的入门知识：时间复杂度和空间复杂度。想要学好算法，必须要掌握如何分析一个算法的时间复杂度和空间复杂度，只有自己会分析这两个个衡量算法主要性能的标准，才能更好的写出性能优秀的算法，同时我们也讲到了最好时间复杂度，最坏时间复杂度，平均时间复杂度和均摊时间复杂度，不过这四种复杂度的计算方式大家作为了解即可，等实际确实需要使用到再来回顾也不迟。
