【数据结构初阶】算法的时间复杂度和空间复杂度

各位读者老爷好！现在鼠鼠我呀来浅谈一下数据结构初阶中的一个知识点：算法的时间复杂度和空间复杂度，希望对你有所帮助。

在浅谈时间复杂度和空间复杂度之前，咱们可以来了解一下一下几个概念：

1.什么是数据结构

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

其实简单来说吧。数据结构就是在内存中管理数据。

拓展：

1.什么是数据库？

简单来说：数据库就是在磁盘中管理数据。

2.内存和磁盘的异同

同：内存和磁盘都是电脑的两个核心存储介质，都是存储数据的两个硬件。

异：内存的速度快，需要带电存储；磁盘的速度（相对）慢，不带电存储。

比如：我们在电脑中创建一个文本文档，在该文档中输入数据，在数据没有保存之前如果电脑突然关机了，那我们重启电脑后这些数据就没有了，因为这些数据是在内存中存储的，内存却需要带电存储。但如果我们在电脑关机之前保存了这些数据，重启之后打开文本文档还可以看到数据，因为保存的数据已经到了磁盘中了，磁盘无需带电存储。（不考虑文本文档有自动保存的情况。）

2.什么是算法

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

咱们再简单来说。算法就是对数据做各种处理的方法。

那咱们如何判断一个算法的好坏呢？

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度（时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。）。

3.时间复杂度

3.1时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

那时间复杂度该如何计算呢？

咱们来抛砖引玉一下子哈，分析一下下面代码的时间复杂度：

void Func1(int N)//计算Fun1中++count总共执行多少次
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n",count);

咱们为了方便介绍，鼠鼠我直接揭晓答案，这个函数的时间复杂度是O(N^2)；

那为什么是O(N^2)呢？什么是O(N)呢？这就要看下面的知识了：

3.2大O的渐近表示法

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

上面的解释其实意思就是说我们计算时间复杂度用的是大O的渐近表示法表示，时间复杂度都是用O(?)表示的，至于括号里面的问号"?" 该用什么替代我们就要根据推导大O阶方法具体分析了，咱们来分析一下上面的代码看看。

函数Func1中++count的基本操作次数是一个函数F(N)=N^2+2*N+10。根据推导大O阶方法我们可以知道Func1的时间复杂度是O(N^2)。其实推导大O阶方法意思就是去掉那些对结果影响不大的项，推导大O阶方法的思想精髓就是估算。

咱们分析一个代码的时间复杂度看看：

int Func2(int*nums,int numsSize,int n)
{
int i=0;
for(i=0;i<numsSize;i++)
{
if(*(nums+i)==n)
{
return i;
}
}
return -1;
}

咱们看看这个函数Func2中是写不出那个操作次数的函数的，操作次数有三种情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)

咱看这个函数Func2无非就是一种遍历数组的算法，在数组nums的numsSize个元素中遍历找n，找到了返回下标，找不到返回-1。最好情况：1次就找到了；平均情况：numsSize/2次找到了；最坏情况：numsSize次找到了。所以这个函数的时间复杂度是O(N)，因为时间复杂度是保守的估算，取最坏情况。

3.3常见时间复杂度举例分析

上面两个代码计算时间复杂度都是看代码的内容，好像在数循环次数就行。其实不然，看一个算法的时间复杂度要看算法思想，无需了解代码细节，咱们在下面代码来体会。

实例1：

// 计算Func3的时间复杂度？
void Func3(int N)
{
int count = 0;
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}

咱们看这个算法基本操作执行了2N+10次，所以这个时间复杂度是O(N)。为什么不是O(2N)呢？推导大O阶方法第3条可以知道要去除常数2。（举个例子：如果有一颗距离地球100亿光年的适合居住的星球和距离地球200亿光年的适合居住的星球对于人类来说没有区别，因为人类远行距离的量级能达到百亿光年的话，多一个百亿是无所谓的，这里去除常数2就是这个思想。）

实例2：

// 计算Func4的时间复杂度？
void Func4(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++ k)
{
++count;
}
for (int k = 0; k < N ; ++ k)
{
++count;
}
printf("%d\n", count)；
}

这个算法基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)，也可以写成O(max(N,M))。

实例3：

// 计算Func5的时间复杂度？
void Func5(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}

这个算法基本操作执行了10次，也就是常数次，通过推导大O阶方法第1条，时间复杂度为 O(1)。

实例4：

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}

这里是一个冒泡排序，这个算法呢基本操作执行最好N次，最坏执行了(N*(N+1)/2次，通过推导大O阶方法+时间复杂度一般看最坏，时间复杂度为 O(N^2)。

实例5：

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
// [begin, end]：begin和end是左闭右闭区间，因此有=号
while (begin <= end)
{
int mid = begin + ((end-begin)>>1);
if (a[mid] < x)
begin = mid+1;
else if (a[mid] > x)
end = mid-1;
else
return mid;
}
return -1;
}

这里是一个二分查找。基本操作执行最好1次，最坏O(logN)次（每查找1次可以排除一半，最好情况当然是第1次就找到，最坏情况得查到最后1次，最后1次是第几次呢？我们一共查找了x次，因为每找1次N就除1个2，所以N=2^x，所以最坏要查找x（x等于log以2为底以N为指数）次。）所以时间复杂度为O(logN)。

ps：logN在算法分析中默认表示是底数为2，对数为N。所以这个底数2可以省略，但以其他数为底就不能省略。

根据二分查找算法的时间复杂度O(logN)来看，二分查找是一个很牛的算法，因为根据这个算法就算是有1百万个数据，最多查找20次就够了。但二分查找又不是很牛，因为这个算法有一个致命缺陷，就是要求数据必须有序。

实例6：

/ 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}

咱看这是一个求阶乘的函数。这个函数算法思想无非就是当传参不为0时递归调用函数自己。那基本调用调用了N+1次，时间累加N+1次，所以时间复杂度是O(N)。

实例7：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}

这是一个递归求斐波那契数的函数。算法思想是双路递归，类似细胞分裂：1生2，2生4……。所以时间复杂度是O(2^N)。

根据这个时间复杂度O(2^N)，我们可以知道这个算法求斐波那契数不是一个好算法，因为指数爆炸太费时间了。那我们采用什么算法求斐波那契数更优呢？鼠鼠我这里写一个代码：

int Fib(size_t N)
{
	if (N == 1 || N == 2)
	{
		return 1;
	}
	int i1 = 1, i2 = 1, i3 = 0;
	int j = 0;
	for (j = 0; j < N - 2;j++)
	{
		i3 = i1 + i2;
		i1 = i2;
		i2 = i3;
	}
	return i3;
}

咱们这个代码求斐波那契数的算法就比上面的代码好，这个算法根据思想可知时间复杂度是O(N)。相比于递归算法大大节省时间。所以我们写代码之前需考虑好各种算法的时间复杂度再考虑用哪种算法写代码，能让代码更加优质。

4.空间复杂度

4.1空间复杂度的概念

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

4.2常见的空间复杂度举例分析

实例1：

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

咱们知道这是一个冒泡排序嘛！那上面代码实现这个算法逻辑的需要额外开辟了常数个（1个）空间（就是exchange），所以空间复杂度是O(1)。

实例2：

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; ++i)
{
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}

这个算法逻辑的实现需要动态开辟malloc了n+1块空间，所以空间复杂度为 O(N)。

实例3：

// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}

这个算法递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)。

5.复杂度的oj练习

消失的数字OJ链接：https://leetcode-cn.com/problems/missing-number-lcci/。打开链接可以做这道题哈！

这道题要求时间在O(N)中完成，鼠鼠我呀有2种解法，咱们依次写写：

解法1：

int missingNumber(int* nums, int numsSize){
    int sum=(0+numsSize)*(numsSize+1)/2;
    int i=0;
    for(i=0;i<numsSize;i++)
    {
        sum-=*(nums+i);

    }
    return sum;
}

这个解题思路就是利用等差数列公式求出0到n所有整数之和，再用这个和依次减去数组元素得到的就是消失的数字呗！这个时间复杂度妥妥是O(N)，空间复杂度是O(1)，oj是可以通过的，大家可以去试试，鼠鼠我就不展示了哈!

解法2：

int missingNumber(int* nums, int numsSize){
    int missnum=0,i=0;
    for(i=0;i<=numsSize;i++)
    {
        missnum^=i;
    }
    for(i=0;i<numsSize;i++)
    {
        missnum^=nums[i];
    }
    return missnum;
}

这个解题思路是：利用0^任何数=任何数、任何数^任何数=0这两个特点得到的。这个时间复杂度也是O(N)，空间复杂度也是O(1)，oj也是可以通过的！