算法的时间复杂度和空间复杂度（数据结构）

这篇具有很好参考价值的文章主要介绍了算法的时间复杂度和空间复杂度（数据结构）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

1、算法效率

1>如何衡量一个算法的好坏

2>算法的复杂度

2、时间复杂度

1>时间复杂度的概念

2>大O的渐进表示法

2>时间复杂度计算例题

1、计算Func2的时间复杂度

2、计算Func3的时间复杂度

3、计算Func4的时间复杂度

4、计算strchr的时间复杂度

5、计算BubbleSort的时间复杂度

6、计算BinarySearch的时间复杂度

7、计算阶乘递归Fac的时间复杂度

8、计算斐波那契递归Fib的时间复杂度

3、空间复杂度

1>空间复杂度概念

2>空间复杂度例题

1、计算BubbleSort的空间复杂度

2、计算Fibonacci的空间复杂度

3、计算阶乘递归Fac的空间复杂度

4、计算斐波那契递归Fib的空间复杂度

4、一道leetcode编程题

1、题目链接

2、题目描述：

3、题目解析

1>思路1

2>思路2

5、总结

1、算法效率

1>如何衡量一个算法的好坏

在现实生活中编写程序的时候，对于一道算法题，不同的人会写出不同的算法。那我们该如何知道那个人写的算法更优呢？对于这种情况有人就想到，我们看那种算法跑的更快不就得了！但事实上在市面上每种电脑的配置有高低之分，高配置的电脑上算法跑的快，低配置的电脑上算法跑的慢，由此可知我们没法通过一个算法跑的快慢来判断那个算法更优！我们为了针对这一问题，我们从两方面来入手比较。第一个方面是空间方面，通过一个算法完成后，所占的空间大致的一个量级，来判断该算法的好坏，而取到的所占空间的量级，就是该算法的空间复杂度！第二个方面是时间方面，通过一个算法完成之后，所用到的时间（也就是该算法的执行次数）的大致的一个量级，来判断算法的好坏，而取到的这个所用时间（执行次数）的量级，就是该算法的时间复杂度！

即：以后对比两个算法的好坏我们只对比它们的空间复杂度和时间复杂度即可！

2>算法的复杂度

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

时间复杂度主要衡量的是一个算法的运行快慢。

空间复杂度主要衡量一个算法运行所需要的额外空间。

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

2、时间复杂度

1>时间复杂度的概念

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

即：算法中的基本操作的执行次数，为算法的时间复杂度！

上代码：
// 请计算一下Func1中++count语句总共执行了多少次？
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\n", count);
}
看以上函数，通过分析Func1执行的次数为：F(N)=(N)^2+2*N+10

在实际中，我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概的执行次数即可，也就是取到它的一个量级，看它是属于那个量级的，那么这里我们是用大O的渐进表示法！

2>大O的渐进表示法

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

推导大O的方法：

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

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

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

上述代码用大O的渐进表示法来表示：

F(N)=(N)^2+2^N+10

当 N= 10 时 F(N)=100

当 N=100 时 F(N)=10000

当 N=1000 时 F(N)=1000000

通过以上我们发现大O的渐进表示法去掉了那些对结果影响不大的项，保留了影响最大的一项，简洁的表示了最大执行次数！

算法的时间复杂度一般分为：最好，平均，最坏三种情况：

最好：一种算法最小的运行次数

平均：一种算法期望的运行次数

最坏：一种算法最大的运行次数

例如：在一个长度为N的数组中，搜索数值X

最好：1次

平均：N/2次

最坏：N次

一般情况下我们所说的时间复杂度是算法运行最坏的情况，所以上面的数组搜索的时间复杂度为：O(N)

2>时间复杂度计算例题

1、计算Func2的时间复杂度
// 计算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);
}
解析：

时间复杂度：O(N)

Func2函数，内部，for循环总共执行了2*N次，while循环执行了10次（M的值为10），Func2的总执行为：2*N+10，而在式子中N是影响最大的哪一项，且通过大O的渐进表示法，去掉常数项，以及去掉与最高阶项相乘的常数。即：Func2的时间复杂度是O(N)

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

时间复杂度：O(M+N)

Fun3函数，内部，第一个for循环执行了M次，第二个for循环执行N次。Fun3函数总共执行了：M+N次。由于我们不知道M和N的关系，M和N 两个未知数都有可能是影响最大的那一项。通过大O的进阶表示法可知，Fun3的时间复杂度为：O(M+N)

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

时间复杂度：O(1)

fun4函数，内部，for循环总共执行了100次，是一个常数次。通过大O的渐进表示法，用常数1取代运行时间中所有的加法常数，即Fun4的时间复杂度为：O(1)

4、计算strchr的时间复杂度
// 计算strchr的时间复杂度？
const char* strchr(const char* str, int character);
说明：strchr是在一个字符串里面，查找单个字符，若该字符存在返回该字符的地址，若找不到则返回NULL

解析：

时间复杂度：O(N)

strchr函数在字符串中找指定的字符的时候，是从头到尾遍历字符串的每个字符进行查找，假设字符串有n个字符！

最好情况：字符在第一个

平均情况：字符在中间

最坏情况：找不到字符

时间复杂度我们按照最坏的情况来说，因为最坏的情况包含最好情况和平均情况，通过大O的渐进表示法可知，strchr的时间复杂度为：O(N)

5、计算BubbleSort的时间复杂度
// 计算BubbleSort(冒泡排序）的时间复杂度？
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

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;
	}
}
解析：

时间复杂度：O(N^2)

BubbleSort函数，内部，第一层for循环执行了n次，第二层for循环执行了end次，end和n都是一个未知数，即end也可以看做是n次。在循环内部有一个exchange变量用来标记数据是否进行交换，若走完一趟没有数据交换，说明数组是有序的，则不需要进行交换！由此可知，时间复杂度可分为两种情况：

最好：有序O(N)

最坏：无序O(N^2)

时间复杂度我们取最坏，即BubbleSort函数的时间复杂度为：O(N^2)

6、计算BinarySearch的时间复杂度
// 计算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;
}
说明：BinarySearch(二分查找）函数，实现思想：前提是数组必须是有序的，随后进行折半查找，假设数组升序，首先取到数组的中间数，若查找的数比中间数要大，则舍弃左边，在右边进行查找，若比中间数要小，则舍弃右边，在左边查找，左边或右边继续进行查找的时候依旧是取中间数折半查找，如此往复，最终要么找到，要么找不到！

解析：

时间复杂度：O(logN)

由说明可知，在进行查找的时候是折半的，即就是 N/2/2/2/2/2/2/2.......一直除下去直到得到结果为值！即执行的过程为：2*2*2*2*2*2..........*2=N 即 2^x=N 则执行次数x为：logN(log以2为底N的对数)，即BinarySearch(二分查找）函数的时间复杂度为：O(logN)

注意：虽然二分l算法看着很牛逼，其实基本上没啥用处，因为它前提是有序！

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

	return Fac(N - 1) * N;
}
解析：

时间复杂度：O(N)

Fac函数，内部，就是函数自己不断的调用自己，直到N的值变为0才开始返回，最终Fac函数的执行次数为N次。通过大O的渐进表示法，去掉常数项（影响对结果不大的项），即Fac函数的时间复杂度为：O(N)

8、计算斐波那契递归Fib的时间复杂度
// 计算斐波那契递归Fib的时间复杂度？

long long Fib(size_t N)
{
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}
解析：

时间复杂度：O(2^N)

Fib函数，内部，进行了两路递归调用，分别调用Fib(N-1)，以及Fin(N-2)，这两路递归，在调用的时候先调用Fib(N-1)这一路递归，返回之后，再接着调用Fib(N-2）这一路递归，直到N小于3的时候返回，最后返回它们的和！

看图理解：

有图可知Fib函数调用自身总共的执行次数是2^N这一量级，即Fib函数的时间复杂度为：O(2^N)

3、空间复杂度

1>空间复杂度概念

空间复杂度：是对一个算法在运行过程中，临时占用存储空间大小的度量。空间复杂度不是计算程序占用了多少bytes的空间，而是计算程序中变量的个数。空间复杂度跟时间复杂度类似，也用大O的渐进表示法来表示！

注意：函数运行时所需要的栈空间(存储参数，局部变量，以及一些寄存器信息等）在编译期间已经确定好了，即一个算法的空间复杂度主要是计算函数在运行时显式申请的额外空间来确定！

2>空间复杂度例题

1、计算BubbleSort的空间复杂度
// 计算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;
	}
}
解析：

空间复杂度：O(1)

BubbleSort函数，内部，额外开辟了常数个变量的空间，从代码中可看到总共开辟了3个变量，即：BubbleSort函数的空间复杂度为：O(1)

2、计算Fibonacci的空间复杂度
// 计算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)

Fibonacci函数，内部，用malloc函数在内存的堆区中总共开辟了n+1个long long类型的空间，根据大O的渐进表示法，去掉常数项。即：Fibonacci函数的空间复杂度为：O(N)

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

	return Fac(N - 1) * N;
}
解析：

空间复杂度：O(N)

Fac函数，内部，函数进行了递归，函数每次递归调用一次都会额外开辟常数个变量，函数总共调用N次，且函数每次递归调用都不会释放栈帧，栈帧空间会进行累加，直到调用到N=0为止，才进行返回，也就是一一释放栈帧空间，因为函数调用了N次，总共开辟了N块栈帧空间，每一空间中都会开辟常数个变量，即调用Fac函数总共开辟的变量空间大致是在N这个量级的！即：Fac函数的空间复杂度为：O(N)

4、计算斐波那契递归Fib的空间复杂度
// 计算斐波那契递归Fib的空间复杂度？
long long Fib(unsigned int N)
{
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}
解析：

空间复杂度：O(N)

说明：Fib函数在进行调用的时候是双路递归，先递归Fib(N-1)，返回之后再递归Fib(N-2)，

所以在递归的时候，会进行空间复用，Fib(N-1)调用完返回之后本次调用的栈帧空间会销毁（注意：这里的销毁指的是将使用权还给操作系统，并不是真的销毁空间），而再继续递归调用Fib(N-2)的时候会继续使用前面调用Fib(N-1)使用的那片栈帧空间，因为两个函数内部开辟空间是一样的，所以恰好可以复用同一块位置。即每一次递归调用函数内部，在函数内部继续递归的那两个函数Fib(N-1)和Fib(N-2)，是用同一块栈帧空间的！即：Fib函数的空间复杂度是：O(N)

看图理解：

4、一道leetcode编程题

1、题目链接

189.轮转数组https://leetcode.cn/problems/rotate-array/

2、题目描述：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：

1 <= nums.length <= 105

-231 <= nums[i] <= 231 - 1

0 <= k <= 105

3、题目解析

1>思路1

第一种思路：

就是将最后一个数拿出来，然后将数组整体往后挪动一位，然后将拿出来的数放到数组的第一个位置。如此往复总共重复K次，就将后K个数字都拿到前面了。

注意：

K有三种情况，K小于数组长度、K等于数组长度、K大于数组长度。对于K小于数组长度情况，我们可以直接进行轮转操作。对于K等于数组长度的情况，其实就是数组转一圈，又变成原样，也就是数字没动。对于K大于数组长度的情况，数组转完之后，又进行转就发生越界了！所以对于K大于数组的长度，我们可以对K进行处理：让K%数组长度得到结果。随后轮转该结果个数，最终得到正确结果，很好得规避越界问题！

画图理解：

代码：
void rotate(int* nums, int numsSize, int k)
{
	//处理K大于numsSize的情况
	k = k % numsSize;
	int a = 0;
	while (k--)
	{
		//将最后一位的数据保存起来
		a = nums[numsSize - 1];
		//进行往后覆盖移动
		for (int i = numsSize - 1; i > 0; --i)
		{
			nums[i] = nums[i - 1];
		}
        //将保存的最后一位数放到数组的第一位
		nums[0] = a;
	}
}
总结：

该思路的时间复杂度为：O(N^2)

该题目是有限制的要求是O(N)的时间复杂度，所以这种思路虽然可以完成效果，但是通不过该题，会报一个超出时间限制的一个错误！思路2可以很好的规避该问题！

2>思路2

第二种思路：

1、先逆序后K个元素。

2、再逆序前数组大小减k个元素(也就是前面剩余的元素）。

3、最后再整体逆序！

注意：

这种思路的K也需要进行处理，当K大于数组大小时会越界，所以要处理，让K%数组大小的值赋给K，再进行逆置操作即可！

画图理解：

代码：
//逆序函数
void Reverse(int* arr, int left, int right)
{
	while (left < right)
	{
		int tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}

void rotate(int* nums, int numsSize, int k)
{
	//处理K大于numsSize的情况
	k = k % numsSize;

	//先逆序后K个数
	Reverse(nums, numsSize - k, numsSize - 1);

	//再逆序前（numsSize-K）个数
	Reverse(nums, 0, numsSize - k - 1);

	//最后逆序整体
	Reverse(nums, 0, numsSize - 1);
}
总结：

该思路的时间复杂度：O(N)

没次逆序，程序的执行次数大致可以看成是N，总共逆序三次，总执行次数是三倍的N，也就是3N，利用大O的渐进表示法，去掉常数，即该算法的时间复杂度为：O(N)。满足该题目的要求，该思路能顺利通过该题！