[初阶数据结构】时间复杂度与空间复杂度

前言

📚作者简介：爱编程的小马，正在学习C/C++，Linux及MySQL。

📚本文收录于初阶数据结构系列，本专栏主要是针对时间、空间复杂度，顺序表和链表、栈和队列、二叉树以及各类排序算法，持续更新！

📚相关专栏C++及Linux正在发展，敬请期待！

本文主要讲解时间复杂度以及空间复杂度，对大O渐进法会有比较详细的讲解，相信大家学完本文，会对复杂度有个很好的理解，那现在开始吧！

前言

1. 算法效率

1.1 如何衡量一个算法的好坏？

1.2 算法的复杂度

2. 时间复杂度

2.1 时间复杂度的概念

2.2 大O的渐进表示法

2.3 常见的时间复杂度计算举例

3. 空间复杂度

4. 复杂度的OJ练习

4.1 消失的数字OJ链接：消失的数字

4.2 轮转数组OJ链接：轮转数组

总结

1. 算法效率

1.1 如何衡量一个算法的好坏？

首先给大家看一段求斐波那契数列数：

int Feb(int n)
{
	if (n < 3)
		return 1;
	else
		return Feb(n - 1) + Feb(n - 2);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Feb(n);
	printf("%d\n", ret);
	return 0;
}

斐波那契实现递归非常的简洁，但是简洁的代码一定好吗？简洁的代码执行效率就高吗？其实不是的，我可以告诉大家，这个递归的时间复杂度是O(2^n)，比如我想求第50个斐波那契数，是很慢的。那我们如何衡量一个代码是好还是坏呢？

1.2 算法的复杂度

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

时间复杂度主要衡量一个算法运行的快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早起，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的地步，所以我们如今已经不再需要特别关注一个算法的空间复杂度，而是要两者综合考虑。

2. 时间复杂度

2.1 时间复杂度的概念

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

即：找到了某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。

例如：

void Func1(int N)
{
	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", count);
}

Func1执行的基本操作次数：

$F(N) = N^{_{2}}+2*N+10$

怎么样得到的这个函数表达是呢？挨个循环分析，首先第一个 i 和 j 控制的循环，是不是里外都是N次，求和就是N*N ，其次第二个k控制的循环，是不是2N次，最后是M控制的循环，是10次，时间是累计的，所以用加法加在一起就是上文代码的时间复杂度。

实际上，我们不需要精确到这种程度，因为没有意义。只是需要大概的精确度，可以知道这个算法的时间复杂度是什么level就可以了。那么这就需要我们使用大O的渐进表示法。

2.2 大O的渐进表示法

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

推导大O阶的方法：

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

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

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

上文函数算法如果使用大O阶的方法，那就是保留最高阶的函数，也就是时间复杂度为：

$F(N) = O(N)$

另外有些算法的时间复杂度存在最好，平均和最坏三种情况

例如：在长度为N的数组中搜索X

最好的情况，是不是第一个就找到X了，这个时候1次找到

平均情况，在中间找到X，这个时候是N/2次找到

最坏情况，遍历完一次数组，N次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

2.3 常见的时间复杂度计算举例

实例1：

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

计算Func2的时间复杂度，首先需要简单计算出数学表达式，K控制的循环有2N次，M控制的循环有10次，那时间复杂度函数就是：

$F(N) = 2*N+10$

但是根据我们的大O表示法，F(N) = O(N)

实例2：

// 计算Func3的时间复杂度？
void Func3(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);
}

计算Func3的时间复杂度，F(N) = M+N ，这个时候都不能省略，因为M对复杂度的影响和N一样，所以该算法的时间复杂度是 F(N) = O(M+N)

实例3：

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

计算Func4的时间复杂度，F(N) = 100 ，根据大O渐进法，常数都要置为1，所以该算法的时间复杂度是 F(N) = O(1)

实例4：

const char* strchr(const char* str, int character);

计算这个函数的时间复杂度？找一个字符串，可能1次就找到了，也可能找了一半找到了，也可能找到最后一个找到了，也可能找不到了，上文我们提到，要考虑最坏的情况，所以N次查找，该函数的时间复杂度也就是 F(N) = O(N)

实例5：

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;
	}
}

这是一个升序的冒泡排序，BubbleSort的时间复杂度是多少？

先简单给大家介绍一下，在冒泡排序里有详细讲解，就是两两对比，你比我大我就往后移动，直到比完，最大的就到后面去了。第一次需要比n-1 ，第二次需要比n-2 次，直到最后1次

我们用等差数列求和来算一下时间复杂度

$F(N) = \frac{N*(N-1))}{2}$

那么根据大O渐进法，F(N) = O(N^2)

实例6：

int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return -1;
}

这是二分查找法，那么如何求时间复杂度呢？实际上是这样的，就是我每查找到一次，就除以2对不对，那我查找X次找到了，是不是可以有这个表达式：

$2^{n} = x$

实际上， $F(N)=\log_{2}x$

所以，时间复杂度就是 $f(N) = O(\log_{2}N)$

实例7：

long long Fac(size_t N)
{
	if (0 == N)
		return 1;

	return Fac(N - 1) * N;
}

这个Fac，我每调用一次函数，是不是都是常量个时间复杂度，那我调用了多少次函数？是N次，所以Fac的时间复杂度就是 F(n）= O(n)

实例8：

int Feb(int n)
{
	if (n < 3)
		return 1;
	else
		return Feb(n - 1) + Feb(n - 2);
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = Feb(n);
	printf("%d\n", ret);
	return 0;
}

上文给大家埋下伏笔的这个代码，应该是如何求时间复杂度，和实例7一样，就是看函数的调用，画个图给大家看看：

实际上是等比数列的求和，为什么可以先求左边的，而不管右边开辟的函数，因为函数栈帧是可以重复利用的，实际上调用完就销毁了，留个下一个函数使用。所以斐波那契数列的时间复杂度表达式是：

$F(N) =2 ^{_{}^{N-1}}-1$ （并没有经过二叉树的复杂计算，就是个估计值，等以后写了二叉树系列在和大家讲解详细的算法）

所以，斐波那契数的时间复杂度是：

$F(N)=2^{N}$

3. 空间复杂度

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

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

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

实例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;
	}
}

如何计算呢？其实数组以及形式参数n已经是建立好的，不计入空间复杂度计算中。只有exchangde这个显式申请的额外空间需要计入。开辟了常数个额外空间，所以是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;
}

可以看到，动态内存开辟了一个数组，那么我们空间复杂度就是O(N)

实例3：

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

	return Fac(N - 1) * N;
}

可以看到，这里的额外空间主要就是函数的调用，那么其实函数栈帧的开辟是可以重复使用的，所以，这里的空间复杂度就是O(N)

4. 复杂度的OJ练习

4.1 消失的数字OJ链接：消失的数字

题目是这样的，数组nums包含从0到n的所有整数，但其中缺了一个。题目要求，要在O(N)时间内完成。那么我们最好想的是什么办法？先给数组排个序，排序了之后，让数组看看是不是后一个等于前一个+1，如果不是，那么上一个+1就是小时的数字，那么这个时间复杂度是多少呢？其实是

F(N)=O(n*logn)，题意，那我再介绍两个方法。

1、异或法

原理：我把原数组中所有的数字进行异或，再讲0-n的所有整数进行异或，最后输出的就是消失的数字，为什么会这样呢？因为相同的就全部异或为0了，而保留下来的就是消失的数字，那这个时间复杂度是多少呢，实际上是O(2N-1)也就是O(N)，看代码：

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

还有一种方法，对0-n的等差数列求和，求出来的值和缺失数字的数组挨个相减，即可得到消失的数字。看代码：

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

4.2 轮转数组OJ链接：轮转数组

比方说 1 2 3 4 5 6 7 ，旋转一次 7 1 2 3 4 5 6 ，旋转两次， 6 7 1 2 3 4 5，可以看到，我们有一个方法，是不是每次把最后一个拿出来，所有数组往后移动，再插入到第一个，这个的时间复杂度是O(N^2)，很慢。那么有没有比较快的方法，有，下面给大家介绍两个，第一，首先是很巧妙的方法，是翻转法。

1、翻转法：

我要移动3位那我们就对前n-k个逆置得到 4 3 2 1 5 6 7 再对k个之后的数字进行逆置，4 3 2 1 7 6 5 再整体逆置得到 5 6 7 1 2 3 4 是不是很巧妙，我们来实现以下，看以下代码：

void reverse(int* nums,int left , int right)
{
    while(left<right)
    {
        int tmp = nums[left];
        nums[left]=nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k) 
{
    if(k>numsSize)
        k%=numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

还有一种方法，就是我们把前k个拷贝到新数组中去，再把后k个也拷贝到新数组中去，最后一起拷贝到数组中即可。

void rotate(int* nums, int numsSize, int k) 
{
    if(k>numsSize)
        k%=numsSize;
    int* tmp = (int*)malloc(sizeof(int)*numsSize);
    memcpy(tmp,nums+numsSize-k,k*sizeof(int));
    memcpy(tmp+k,nums,(numsSize-k)*sizeof(int));
    memcpy(nums,tmp,numsSize*sizeof(int));
    free(tmp);
    tmp=NULL;
}