时间复杂度与空间复杂度_时间复杂度和空间复杂度的概念

目录

一、数据结构前言 ：

1.1、什么是数据结构？

1.2、什么是算法？

二、算法复杂度：

2.1、算法效率：

2.2、时间复杂度：

2.2.1、时间复杂度的计算：

2.3、空间复杂度：

2.3.1、空间复杂度的计算：

三、常见复杂度对比：

---

一、数据结构前言 ：

1.1、什么是数据结构？

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合、

1.2、什么是算法？

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出，简单来说算法就是一系列的计算步

骤，用来将输入数据转化成输出结果、

二、算法复杂度：

算法复杂度包括时间复杂度和空间复杂度， 时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间、

2.1、算法效率：

算法效率分析分为两种：第一种是时间效率，第二种是空间效率，时间效率被称为时间复杂度，而空间效率被称作空间复杂度，时间复杂度主要

衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小，所以对空间

复杂度很是在乎，但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度，所以我们如今已经不需要再特别关注一个算法的

空间复杂度、

2.2、时间复杂度：

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间，一个算法执行所耗费的时间，从理论上

说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道，但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻

烦，所以才有了时间复杂度这个分析方式，一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时

间复杂度、

我们知道，同一种算法，在不同的环境下，比如在，8核（8个CPU）64G内存环境下就会比在2核4G内存环境下，执行的速度更快，由于环境的

不同，我们是没有办法通过时间来计算的，所以我们就没有办法把时间当做时间复杂度的衡量标准，会受到配置环境的影响，而我们又知道，一

个算法所花费的时间与其中语句的执行次数是成正比的，因此，我们可以把算法中的基本执行次数作为算法的时间复杂度、

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多，一个算法中的语句执行次数称为语句频

度或时间频度，记为T(n)、

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f (n)

的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度、

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低、

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知

道哪个算法花费的时间多，哪个算法花费的时间少就可以了、

2.2.1、时间复杂度的计算：

时间复杂度的计算使用的是大O的渐进表示法，其实是一种估算，最后的时间复杂度结果应为：O (N^2) 

N = 10     T(N) = 130             O (N^2)=100

N = 100   T(N) = 10210         O (N^2)=10000

N = 1000 T(N) = 1002010     O (N^2)=1000000

由此我们可知，当N趋向于无穷大的时候，O (N^2)近似等于 T(N) ，因此，大O的渐进表示法，利用的就是高等数学中趋向无穷大的思路，可以

把2*N+10省略掉不考虑，得到的结果作为我们的时间复杂度，实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需

要大概执行次数，那么这里我们使用大O的渐进表示法，大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数、

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。

例2：

我们假设计算机运行一行基础代码需要执行一次运算，要注意，函数体的外层不算做一次执行，那么下边这个方法需要执行2次运算：

​

另看一个例子：

 这个方法需要 (1+n + 1 + n + n+1) = 3n + 3 次运算，我们把算法需要执行的运算次数用输入大小 n 的函数表示，即 T(n) ，则有：T(n)=3n+3

那么当我们拿到算法的执行次数函数 T(n) 之后怎么得到算法的时间复杂度呢？

常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)，如果 T(n) 不等于一个常数

项时，则直接将T(n)中的常数项省略即可、

比如：第一个 Hello World 的例子中 T(n) = 2，所以我们说那个函数(算法)的时间复杂度为 O(1) ，，若T(n) = n + 29，此时时间复杂度为 O(n)、

高次项对于函数的增长速度的影响是最大的，n^3 的增长速度是远超 n^2 的，同时 n^2 的增长速度是远超 n 的，同时因为要求的精度不高，所以

我们直接忽略低次项、

比如:

T(n) = n^3 + n^2 + 29，此时时间复杂度为 O(n^3)、

因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数。

比如：

T(n) = 3n^3，此时时间复杂度为 O(n^3)、

由此可见，由执行次数 T(n) 得到时间复杂度并不困难，很多时候困难的是从算法通过分析和数学运算得到 T(n)，对此，提供下列四个便利的法

则，这些法则都是可以简单推导出来的，总结出来以便提高效率。

在例2中，所用的计算时间复杂度的方法是最为标准的，但是如果每次都这样计算的话，就会比较麻烦，因此，我们在计算时间复杂度的时候，

只考虑复杂的循环结构即可，对于不是复杂的循环结构来说，他们累加起来就是常数项，而常数项最终会被舍弃，所以直接不考虑也是可以的、

比如：

首先，常见的时间复杂度量级有：

常数阶O(1) —— 对数阶O(logN) —— 线性阶O(n) —— 线性对数阶O(nlogN) —— 平方阶O(n2) —— 立方阶O(n3) —— K次方阶O(nk) —— 指数

阶(2n)，上面从左至右依次的时间复杂度越来越大，执行的效率越来越低、

像这种类型的话，对于上图而言，程序要么进入 if  语句，要么进入 else 语句，则要选择执行(循环)次数最多的那部分来算时间复杂度，故选择 if 语句中的代码来求

时间复杂度，则T(N)=N^2 ，故时间复杂度就是O(N^2)、

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是O(1)，如：

​

上述代码在执行的时候，它消耗的时间并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。 

​

时间从0到24，，单位是ms，几乎可以忽略不计，因此，我们就可以认为，当n=10000和n=10000000的时候，for循环执行完毕所需要的时间很

少，即得，时间复杂度很低，执行效率很高，因此，无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。

线性阶O(n)，即线性时间复杂度、

​

对于这段代码，在上述例2中的第二个例子中，已经分析过，但是方法过于冗余，我们可以简单的来计算，即，不考虑该循环内部的这些代码，

只考虑for循环的次数即可，i从1到n，所以共循环了n次，它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复

杂度，这种简单的方法能够让我们更加快捷的计算出最后的时间复杂度的结果。 

对数阶O(logN)

​

在while循环里面，每次都将i乘以2，乘完之后，i 距离n就越来越近了，我们试着求解一下，假设循环x次之后，i 就等于n了，此时这个循环就退

出了，也就是说2的x次方等于n，那么x = log以2为低的n次方，也就是说当循环 log以2为低的n次方次以后，这个代码就结束了，因此这个代码

的时间复杂度为：O(log以2为底的n次方)，，又因为，log以2为底的n次方在计算机中不方便书写， ，因为，就规定了，log以2为底的n次方简写

成log n，把2省略掉，更方便的进行书写，但是不要把这种与数学中的 lg 进行混淆，两者不是一个概念。

线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环n遍的话，那么它的时间复杂度就是 n * logN，也就是了

O(nlogN)、

​

平方阶O(n2)

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了，举例：

​

这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)

如果将其中一层循环的n改成m，即：

​

那它的时间复杂度就变成了 O(m*n)，如果是：

​

那么它的时间复杂度就是：O(m+n)，这是因为，算法里面，不一定只有一个未知数，在这里，n和m的阶数是一样的，不知道两者的大小，也不

知道两者对结果的影响那个大，所以，只能写成上述形式，要注意，这里不是O(1)，，只有是常数的时候，结果才能写成O(1)，这里m和n都不是

常数，不可以直接写成O(1)、如果条件告诉了，n远大于m，那么n对结果的影响更大，则时间复杂度就是O(n)、

立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似、

在时间复杂度计算中，通常假设数组(整型数组和字符数组)或者是字符串的长度是N，和通常使用大小N来表示某种未知（不定）的大小，例如：

有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

这就是在一个字符串里面找一个字符，本题以上举的例子中的时间复杂度是不会变化的，比如，就是O(1)或者是O(n+m)，，不会发生改变，，

但是在，本题中，是在一个字符串中找一个字符，我们不知道，要找的那个字符在该字符串中的所在位置，可能寻找一次就找到了，那么

T(N)=1，1是常数，所以有O(1)，这就属于最好的情况，如果寻找N次才找到，则有T(N)=N，则有O(N)，，这是最坏的情况，，，那么平均的情

况，就是寻找N/2次找到该字符，则有T(N)=N/2，，所以，平均情况的时间复杂度就是：O(N)，去掉系数1/2、

但是，在面对这种情况的时候，通常看最坏的情况，默认时间复杂度就看最坏，所以，上述题目中的时间复杂度应该是：最坏情况下的O(N)。

特别注意的是，像这种长度由自己输入决定的情况时，不可以单独看一个例子来判断其长度，比如，在字符串abcdef中找字符x的情况，即，

strchar("abcdef",'x')，我们已知字符串长度为6，但是不可以把他的时间复杂度看做O（1），因为，字符串中的内容是由我们自己掌控的，每一

次设定的字符串长度都是不一样的，，所以，像这种长度由自己输入决定并且每一次输入的长度都可能不一样的情况，就默认他们的长度是N，

而不是根据其中一个特例来看，总而言之，像数组(整型数组和字符数组)或者是字符串这种内容由我们自己输入决定的情况，不要抓住一个特例

来看它的时间复杂度，要考虑所有的情况，我们可以输入的长度并不是一个定值，所以，就默认把他长度看做是N、

例题：

由于所求的时间复杂度和空间复杂度是针对于某一个算法而言的，所以，上图中所求的时间复杂度即为调用函数中的时间复杂度，因为是两层for

循环嵌套，并且内外for循环的循环次数都是定值，所以，T=x*y，但是由于，x和y是实参传给形参的，在该代码中，x=3，y=3，但是，当我们求

时间复杂度的时候，不能单看个例，要考虑整体情况，此次x=3，y=3，即三行三列，但当该代码对4行4列或者是多行多列进行运算的时候，就不

再是x=3，y=3了，像这种大小不确定或者是未知的情况，通常使用N来代替其大小，所以，T=N*N，，则T=N^2，，所以时间复杂度即为：

O(N^2)、此时只需要看这两层for循环的次数即可，不需要考虑其中的条件语句、所以，如果在调用函数的时候，实参把某一个固定值传给调用函

数形参部分，那么当在调用函数中使用该固定值时，再去求时间复杂度的时候，不能单看这一个固定值，因为，下次实参再传过来的值可能就不

是该值了，所以要考虑整个算法，而不是单独考虑这一个特例的情况、
 

例3、

通过以上例子可知，只需要考虑循环等复杂结构的时间复杂度即可，本题是一个冒泡排序，具体冒泡排序的实现过程不在讲述，在这里只考虑该

冒泡排序的时间复杂度，首选，简略说明，如果通过冒泡排序来排SZ个数字的话，就需要SZ-1趟冒泡，外层for循环的次数已经确定是SZ-1次，

但是内层for循环的次数是不断变换的，当i=0时，内层for循环第一次循环的次数是SZ-1次，，当i=1时，内层for循环第二次循环的次数是SZ-2

次，所以，内层for循环的次数是不断在改变的，我们不可以让两个for循环次数直接相乘，必须要捋清楚他们的执行次数才可以，所以要记住，当

for循环嵌套的时候，如果内外for循环的循环次数都是定值的时候，才可以直接相乘得到执行次数，再通过大O方法推导出时间复杂度，但是，嵌

套循环如果有一层循环的循环次数在不断改变的时候，一般都是外层循环次数是定值，内层循环次数会不断改变，这样的话就不可以直接相乘得

到执行次数，必须捋清楚总的执行次数才可以，本题中的冒泡排序就不可以直接相乘，我们知道，如果通过冒泡排序来排SZ个数的话，外层for

循环需要循环SZ-1次，内层for循环每次循环SZ-1-i 次，所以，总的执行次数T（SZ）=SZ-1 + SZ-2 +SZ-3 + ..... 1 ，，则有：

T（N）= N-1 + N-2 +N-3 + ... + 2 + 1 这就是总的执行次数，一共是N-1项相加， 这N-1项代表的是外层for循环的次数，每一项代表的是每一次外

层for循环对应的内层for循环的次数，，通过等差数列求和公式可知，T（N）=(（N-1+1）( N-1 ) )/2 最高次数项就是(N^2)/2，，所以最终的时间

复杂度就是O(N^2)、

例4、

力扣——消失的数字

本题要求时间复杂度是O(n)，具体的思路如下：

思路一：

冒泡排序，然后再使用 if 语句来判断，前一项加1是否等于后一项，如果等于则往后移动一项再去判断，如果不等于，则返回前一项+1这个数

值，就可以找到缺失的数字，但是，由于我们已知，冒泡排序的所执行的次数是(n^2)/2-n/2，，接下来的 if 判断还要遍历一下数组，我们又知

道，对于数组来说，默认它的长度就是n，，所以，总执行次数就是:T(n)=(n^2)/2-n/2+n，，在通过大O估计得到，时间复杂度就是O（n^2），显

然不符合题意要求，所以该方法不行；

思路二:

qsort快排，在此我们要记住qsort快排的执行次数就是n*logn，，快排结束后仍需要遍历一下数组，数组的长度默认是n，则总的执行次数就是：

T（n）=n*logn+n，，则最后的时间复杂度就是O(n*logn)，也不符合题意，所以该方法也是不行的，如果仅考虑qsort快排的话，总执行次数就是

n*logn，则时间复杂度就是O(n*logn)、

思路三：

计算 0-n 该等差数列的和，然后再减去数列中所有数字相加之和，得到的就是所缺失的那个数字

首先要知道，上题中所缺失的数字只考虑数列中间的一个数字，不考虑两端，然后就可以通过观察整型数组就可以知道了最大数，然后通过等差

数列公式来计算该等差数列的和，如果通过等差数列求和公式来求和的话，只执行了一次，然后再遍历数组求和，由于是数组，所以长度是

n，，则总执行次数就是T（n）=n+1，，则时间复杂度就是O(n)，满足题意要求，如果不知道等差数列求和公式，也可以通过for循环来求该数列

之和，代码如下：

该数组里面的数字是一个等差数列，差值为1，并且从0开始，因为，缺失一个数字后的个数为numsSize个，所以，则不缺失的话，数字个数应

为numsSize+1个，即这里的n个数字，由于是差值为1的等差数列，并且起始项为0，，所以，我们只需要从0开始，依次加到n个数字，并且后一

项比前一项大1，得到的和就是该等差数列之和，，这样就可以在不知道等差数列求和公式的情况下，求出来等差数列之和sum1，然后，在使用

一次循环来遍历整个数组来求得数组中所有数字之和sum2，然后sum1-sum2得到的就是所缺失的那一个数字，通过上述代码可知，第二个for循

环是遍历一个数组，默认数组的长度是n，所以执行的次数也是n，第一个for循环执行的次数是数组长度+1，则执行次数为n+1，所以，总的执行

次数就是：T（n）=2n+1，，则时间复杂度就是O（n），满足题意要求。

思路四：

通过异或来得到缺失的数字，由于异或满足交换律，且有相同的数字异或得到0，0与某一个数字异或得到的还是这个数字，比如，假设输入的整

型数组中的元素是，[ 1,0,3 ]，，我们知道，补充后的元素即为：0,1,2,3， 依次异或，即： 1^0^3^0^1^2^3=2，根据这一原理，我们首先假设要

找的数字x=0，利用，0与任何数字异或得到的就是这个任何数字的原则，拿着x分别依次去异或数组中的数字和补充后的数字，，不考虑顺序，

先去异或数组中的数字也行，先异或补充后的数字也是可以的，利用的就是异或满足交换律，都可以得到最终的要寻找的数字x，直接返回即

可。

第一个for循环是遍历数组，则执行次数就是n，第二个for循环执行次数是n+1，，所以，总执行次数T（n）=2n+1，则时间复杂度就是：O(n)，

满足题目要求、

思路五、

映射方式：

开辟一个下标从0 - N的数组，把每一个位置都初始化为 -1 ， 遍历里面的每个值，把该值放在下标为该值的位置上，比如，把数值2放在数组中

下标为2的位置上，放完之后再进行遍历找数组中数值为-1的位置的下标，该下标就是确实的数字，此时，遍历两次数组，对于数组来说，一般

默认其长度为N，则遍历两次总执行次数为：2*N，所以，时间复杂度是O(N)，满足要求，但是该方法要有O(N)的空间复杂度，因为，要开辟下

标从0 - N ，共N+1个额外的空间，再加上其他常数个额外的空间，所以，最后的空间复杂度是O（N），这就是典型的拿空间换时间、

例5、

二分查找的时间复杂度的计算：

在二分查找中，最好的情况就是查找一次就找到了，执行次数是1，则时间复杂度就是O(1)，默认数组的长度为N，遍历的时候，则最坏情况就是

执行N次，时间复杂度就是O（N），但是，现在是二分查找，不是暴力查找，所以，时间复杂度不可能是O（N），对于二分查找，最坏的情况

就是，两端中间只有一个数字，如果该数字是我们要找的那个数字，就找到了，如果中间数字不是我们要找的数字，那么就找不到了，，所以，

最坏的情况就是两端中间只有一个数字了，，由于二分查找是对半查找，最坏就剩一个数字，所以，反推则有：1*2*2.....*2=N，，假设乘了x个

2，，则有，2^x=N，，所以，x=log以2为底的N次方，则执行次数就是log以2为底的N次方，，所以，时间复杂度就是O（log以2为底的N次

方），简写成O（logN） 、

例6、

对于非递归算法求时间复杂度，不管最好最坏的情况是否一样，均可以按照自己的方法直接求时间复杂度，除此之外，所有的非递归算法均可分为最好最坏的情

况，分别求各自的部分时间复杂度，再由最坏的情况得出整体的时间复杂度，只不过是有的算法最好最坏情况是一样的，没有区别，有的算法最好最坏的情况是不

一样的，有区别，但不管怎么样都可以分为最好最坏的情况，再根据最坏来得出整体的时间复杂度、

对于非递归算法求空间复杂度，则不分最好最坏的情况，不考虑栈帧的问题，只数一下算法代码中定义的变量的个数就可以了、

对于递归算法求时间复杂度，当最好最坏的情况一样的时候， 则可以直接套结论求解，具体套哪个结论需要再分析，也可以分为最好和最坏的情况，然后再分别套

结论求出各自的部分时间复杂度，具体套哪个结论需要在分析，再根据最坏的情况得出整体的时间复杂度，当最好和最坏情况不一样时，不可以直接套结论求解，

只能求出两种情况下再分别套结论求解部分时间复杂度，具体套哪个结论需要在分析，再根据最坏的情况得出整体的时间复杂度、

对于递归算法求空间复杂度，当最好最坏的情况一样的时候， 则可以直接套结论求解，具体套哪个结论需要再分析，也可以分为最好和最坏的情况，然后再分别套

结论求出各自的部分空间复杂度，具体套哪个结论需要在分析，再根据最坏的情况得出整体的空间复杂度，当最好和最坏情况不一样时，不可以直接套结论求解，

只能求出两种情况下再分别套结论求解部分空间复杂度，具体套哪个结论需要在分析，再根据最坏的情况得出整体的空间复杂度、

首先，关于递归求时间复杂度需要掌握两个结论：

1、如果每次函数调用中总的执行次数和递归参数无关，则递归算法的时间复杂度= 递归的次数  x  每次递归函数中的时间复杂度、

2、如果每次函数调用中总的执行次数和递归参数有关，则递归算法的时间复杂度就等于所有的递归调用中执行次数的累加、

在递归算法中，只考虑能递归的部分，即考虑N>=2的时候，对于N<2的情况，当做递归结束的标志、

如上题所示，从 Fac(N)—— Fac(N-1)—— Fac(N-2)—— Fac(N-3) ..... —— Fac(1) ，递归的次数为N次，，每一次递归中只有一个三目操作符，

不管三目操作符是否可以再简化，没有循环等复杂结构，所以，每次递归函数中的时间复杂度是1，即O(1)，则，总的时间复杂度就是:O(N*1)=O(N)、

使用公式法求解递归算法的时间复杂度：

如果是下面这种情况的话：

每次递归的时候，N的大小在发生改变，所以，不能直接N*O(N)，而是，由于递归了N次，每一次中，N的值就会发生改变，所以，T（N）=N+

(N-1)+(N-2)+...+1  ，，是一个等差数列求和，则时间复杂度为：O（N^2）、        

 例7、

计算斐波那契数列的时间复杂度的公式也是：递归算法的时间复杂度= 递归的次数 x 每次递归函数中的时间复杂度、

首先，我们先看每次递归函数中的时间复杂度，发现，没有循环等复杂结构，不管三目操作符是否可以再简化，则都认为每次递归函数中的时间

复杂度就是1，然后再去看递归的次数、

会有一部分提前结束， 假设都不提前结束的话，，递归次数总和应为：2^0 + 2^1 + .... +2^(N-1) = 2^N - 1 由等比数列求和可知，但是这只是假

设的情况，还有一部分会提前结束，所以，精确的递归次数应为： 2^N - 1 - 常数 ，，所以，递归算法的总时间复杂度应为：

O( ( 2^N - 1 - 常数 ) * 1 ) =O( 2^N - 1 - 常数 )，再化简得到时间复杂度应为O(2^N)，如果直接求出来的时间复杂度不是最简，则需要进一步化

简，如果是最简，则时间复杂度就是这个结果、

例8、

思路:

1、

首先，让数组里面的数都异或一下，，按照之前的做法，先定义一个ret=0，拿着ret分别去和数组里面的数字异或，因为ret=0，0和任何一个数异

或得到的还是这个数，对于数组里面的数字，出现两次的数异或之后就没了，所以说，最后的ret的结果就是两个出现一次的数异或之后的结果，

假设两个出现一次的数分别是x和y，则，ret=x^y；

2、

我们现在知道的ret是x和y异或后的结果，题目中要找出x和y，不好直接下手，所以，要通过分离的方法来求，所谓分离，即指：假设，

x=5,y=3，，对应的补码即为，0101和0011，，异或后得到的结果是：0110 ，得到的十进制数字是6，和5,3，没有任何关系，，，但是，ret在

这里肯定不是0，因为，只有两个相同的数字异或才能得到0，我们这里的ret是x和y异或得到的结果，并且，已知，x和y不相同，所以，ret一定

不是0，，，假设一个数组里面的数字有: 1 3 1 2 5 2 ，，，让该数组里面的数字都异或得到的结果ret就是3和5异或的结果，，因为ret不等于

0，，那么它的补码里面一定存在1，，不一定只有一个1，，但是至少有一个位上的二进制数字是1，，我们要在ret的补码里面随便任取一个二进

制序列为1的位，， 要注意是任意选一个即可，，比如，，ret=6，，6的补码是：0110 ，，从右往左位数增大，，可知，ret的第二第三位，都是

1，，我们随便选一个，假设选第二位，，即，从右往左数，ret补码里面的第一个1，，异或得到的该位是1，说明，x和y对应的该位肯定有一个

0，也有一个1，，因为是相同为0，相异为1，，所以，x和y对应的该位肯定相异，并且二进制序列中只有0和1，所以，对应的该位，x和y，要么

分级别是0和1，要么就是1和0，，这样就可以把原数组里面的数，因为上面我们取的是，第二位，所以，就可以把原数组里面的数，第二位为0

的分为一组，第二位为1的分为另一组，，如果选ret中第二位上的1进行分离的话，，则，数组中数字第二位为0的有：1 1 5

第二位为1的有： 2 2 3 ，，原理就是，根据ret补码中某一位上面为1，从而得到x和y在该位一定不相同，进而来分组，这样就可以保证，x和y不

被分在一组里面，，因为，ret的补码里面二进制位上不一定只有一个1，可能存在多个，即大于等于1个，，，我们是任选一个即可，，如果我们

选择ret补码中第三位上的1进行分离的话，，，则，数组中数字第三位为0的有：1 1 2 2 3，，第三位为1的有： 5 ，，这样也可以把3和5分到两

个组中，，所以，，在ret的补码中，，无论选哪一个位上的1进行分离，都能保证把3和5分开，，由于是任意选则一个，，我们只需要选择最低

位上的1即可，即选择从右往左数第一个1所在的位进行分离即可，分离之后，让每个组里面的数字和自己所在的组中的数字异或，就可以得到我

们所求的x和y了，本题中要求的是返回一个数组，并不是返回数字，要注意、，所以在本题中，把找出来的x和y放在一个数组里面，，然后把该

数组返回出去才行。

 一个int类型的整数不允许进行左移31位的操作，会改变符号位，除非强制类型转换为long，long long类型，这样左移31位就不会改变其符号

位、

2.3、空间复杂度：

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 ，空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，

所以空间复杂度算的是变量的个数，空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法（估算），不使用额外的空间的含义就

是空间复杂度为O(1)，他表示的含义不是只能使用一个空间，而是可以使用常数个空间、

不考虑形参部分接收的变量，也不考虑输入数组中变量的个数，考虑的是算法运行中所需的额外需要开辟的空间，时间是累计的，，空间是不累

计可以复用的，所以在本题中的形参部分里面的 int* a 和 int n 不算入额外开辟的空间里面、

不考虑该算法运行外的数组中变量的个数，但是在该算法运行时，内部如果定义了数组，则需要考虑数组中变量的个数、

2.3.1、空间复杂度的计算：

例1：

求空间复杂度的时候，只需要去数变量的个数即可，不需要考虑为函数开辟额外的空间，在本题中，只有三处定义的变量，要记住，虽然在for循

环里面，第一次循环定义一个变量，为其开辟了空间，但是出了第一次for循环，该空间就会被销毁，接下来第二次for循环再为其开辟空间的时

候，该空间和第一次为其开辟的空间是同一块空间，，所以还认为是一个空间即可，，即，时间是累计的，但是空间不可以累计，可以重复使

用，共有3个变量，3处需要开辟额外的空间，，3是常数，，所以，空间复杂度就是O(1)、

例2：

返回下标从0-n的斐波那契数组，，使用malloc函数动态开辟n+1个内存空间，即在算法运行中额外开辟了n+1个变量，，，size_t n不算该算法的

变量，，int i 算一个变量，long long* fibArray 也算一个变量，故有 n+3 个变量，，所以，空间复杂度就是O（n），空间复杂度通常上只有两种

情况，，即：O(1) 或 O（N）、

再如：

此处的numsSize是数组输入的元素个数， 每次输入的元素个数是不一样的，是一个不定(未知)的个数，而在算法内部动态开辟的额外的内存空间

的大小也是不定的，像这种大小不定或未知的数，都假设其大小为N，所以，算法内部一共开辟了N+1个额外空间，则空间复杂度即为：O(N)、

 变长数组的分析和上图也是一样的、

例3：

对于递归算法求空间复杂度时，要考虑栈帧的问题，默认调用函数时，即每一次递归时在栈帧中开辟常数个额外的空间，此时计算递归算法的空

间复杂度时，不能简单的只看递归的深度(层数)，当每一次递归内部的代码没有定义变量时，不可以说每一次递归额外开辟了0个空间，还要考虑

每一次递归时在栈帧中开辟了常数个额外的空间，这是默认的，所以，当递归算法求空间复杂度并且每一次递归代码中没有定义变量的时候，则

递归算法的空间复杂度 = 递归的深度（递归的层数） x  每一次递归的空间复杂度，，就如下图所示，虽然每一次递归代码中没有定义变量，但

是还要考虑每一次递归调用函数时栈帧中开辟了常数个额外的空间，所以，每一次递归中的空间复杂度就是O（1），其中包括，代码中开辟的0

个额外的空间和栈帧中开辟的常数个额外的空间，此时，递归的深度为N，所以空间复杂度即为：N*O(1)，则为：O(N)、

再如下图：

此时，每一次递归中，代码中额外开辟了m+1个空间，再加上每一次递归时栈帧中开辟的常数个额外的空间，所以，每一次递归的空间复杂度

为：O(m)，又因为递归深度为N，所以，总的空间复杂度即为：O（N*m），如果把上图中的m改为N，则此时就不可以直接再直接套上述公式

了，因为，算法内部每一次动态开辟额外的内存空间的个数是变化的，此时，就要使用累加的方式，一共递归N层，第一层递归额外开辟的内存

空间准确的个数是：N+1+常数个，第二层递归额外开辟的内存空间准确的个数是：N-1+1+常数个，所以精确来说的话，总共开辟了：N+(N-1)+

(N-2)+...1+总常数个，所以，总空间复杂度即为：O(N^2)、

对于不是递归算法求空间复杂度时，不考虑栈帧的问题，只数一下代码中定义的变量的个数就可以了、

单路递归时，递归深度(递归层数) === 递归次数，比如上面的计算阶乘递归，此时的递归深度(层数) = 递归次数，都是N、

多路递归时，递归深度(递归层数) 不等价于 递归次数，比如上面的菲波那切数列，此时，递归次数为：2^N - 1 - 常数 ，递归深度或层数则为： N、

递归算法计算空间复杂度时，不可能是O(1)、

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间、

最坏情况下的时间复杂度称最坏时间复杂度，一般讨论的时间复杂度均是最坏情况下的时间复杂度， 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入

实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长、

平均时间复杂度和最坏时间复杂度是否一致，和算法有关、

三、常见复杂度对比：

例题1：

力扣

思路一：

右旋K次，一次移动一个数字，定义一个变量tmp，把数组中最后一个数字保存在变量tmp内，默认数组长度为N，把数组中前N-1个值全部向右移

动一位，再把tmp中的值放在数组的首位，这就完成了一次右旋，右旋K次就可以达到目的，此时，每次右旋时，都要把数组中前N-1个值全部右

移一位，这就需要遍历数组，遍历一次数组执行的次数为N-1次，，现在，由于给定的K值是不定(未知)的，所以，假设K值也是N，所以，

乘积起来得到最终的时间复杂度是：O(N^2)，由于没有额外开辟数组，所以，空间复杂度就是：O（1）、

虽然该方法满足空间复杂度的要求，但是时间复杂度不太好，并且在力扣上不能正常运行，所以不采用该方法，

思路二：

额外开辟一个数组，把后K个数不改变顺序的依次放在新开辟的数组的前面，再把原数组中前N-K个数字直接拷贝到新数组内容的后面即可，此时

要开辟的新的数组的大小和原数组是一样大的，并且，原数组的大小默认为N，所以新开辟的数组的大小也是N，此时遍历一遍数组即可，则时

间复杂度是：O（N），但是由于额外开辟了数组，所以，空间复杂度是：O(N)，此时不满足要求，不采用该方法、

思路三：

三次逆置，先逆置前N-K个数字，再逆置后K个数字，然后整体再进行逆置，不需要额外开辟数组，所示空间复杂度是：O(1)，，第一次遍历就可

以把前两部分逆置，第二次遍历逆置整体，执行次数为：2*N次，所以时间复杂度就是：O(N)、

例题2：

力扣

原地删除等价于空间复杂度为：O(1)、

思路一：

开辟一个新的数组，把原数组中不是val值的数据都放在新开辟的数组中去，但是由于原数组中元素个数是不确定的，并且原数组中不是val值的

数据的个数也是不确定的，但是最坏的情况就是，原数组中所有元素都不是val值，而原数组中元素的个数又是不确定的，所以则假设开辟的新的

数组元素个数为N个，或者可以理解为，开辟一个新的数组，把原数组中不是val值的数据都放在新开辟的数组中去，由于原数组中的元素的值每

次输入的都有可能不一样，所以，原数组中不是val值的数据的个数是不确定的，现在要把这些值都放在新开辟的数组中去， 所以新开辟的数组

的元素个数也是不确定的，所以假设新开辟的数组的元素个数为N个，又因为最后还要把新开辟好的数组中的元素拷贝到原数组中，这是因为题

目要求是在原数组中进行修改的，把原数组中不是val值的数组放在新开辟的数组中则需要遍历，之后还要把新数组中的数据拷贝到原数组中，又

因新开辟的数组中元素个数是不确定的，所以遍历新的数组时，默认新数组长度为N，所以，总的时间复杂度就是:O(N)，，由于额外开辟了数

组，所以，空间复杂度是：O(N)，不满足题目要求，不采用该方法、

思路二：

双指针，两个指针都指向原数组，刚开始时，两个指针都指向原数组首元素的地址，把原数组中不是val值的数据依次放在指针dst所指的位置

上，指针src指向的数据若不是val值，则把该值放在指针dst所指的位置上，同时，指针变量src和dst都各自++，若指针变量src指向的数据是val

值，则不把该值放在指针dst所指的位置上，此时，只需要指针变量src++即可，此时，时间复杂度是：O(N)，遍历一遍即可，由于没有额外开辟

数组，是在原数组上进行操作的，所以，空间复杂度就是：O(1)，满足题目要求、

int removeElement(int* nums, int numsSize, int val)
{
//字符串一般用指针,数组一般使用下标进行访问、
 
  /*  int src=0;
    int dst=0;
    int i=0;
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]!=val)
        {
            nums[dst]=nums[src];
            dst++;
            src++;
        }
        else
        {
            src++;
        }
    }
    return dst;*/
    int src=0;
    int dst=0;
    while(src<numsSize)
    {
        if(nums[src]==val)
        {
            src++;
        }
        else
        {
            nums[dst]=nums[src];
            src++;
            dst++;
        }
    }
    return dst;
}

思路三：

对原数组进行第一次遍历，找到第一个val值，然后把该val值所在的位置后面的所有的数据依次由左向右的向前挪动一个位置，同时原数组中元

素个数减去一个，由于假设数组长度默认为N，所以，第一次遍历的时候执行次数为N次，然后再进行第二次遍历，由于原数组中元素的个数减

去1，所以，现在数组中元素个数为N-1个，再进行遍历的时候，执行次数为N-1次，，并且还不明确原数组中到底有几个val值，像这种不明确大

小的值，默认其为N个，当有1个val值时，需要遍历一次数组，执行次数为N次，当有两个val值的时候，第一次遍历执行次数为N次，要进行两次

遍历，第二次遍历执行次数为N-1次，同理，当有N个val值的时候，执行次数则为N-(N-1) === 1次，所以，总的执行次数为N+（N-1）+(N-

2)+..1，所以，时间复杂度则为：O(N^2)，或者可以理解为，因为不知道原数组中，val值的个数为多少，就按最坏来看，即，原数组中全部的值

都是val，并且原数组长度默认为N，所以还是有N个val值，其次分析同上，所以时间复杂度是：O(N^2)，，由于直接在原数组上进行操作，所以

没有开辟额外的空间，故，空间复杂度是:O(1)、

关于复杂度的讲解到此为止，希望大家点赞收藏哦~