C语言数据结构时间复杂度及空间复杂度简要分析

一、时间复杂度和空间复杂度是什么？
- 1.1算法效率定义
- 1.2时间复杂度概念
- 1.3空间复杂度概念
二、如何计算常见算法的时间复杂度和空间复杂度
- 2.1时间复杂度计算
- 2.2空间复杂度计算
- 2.3快速推倒大O渐进表达法
三、一些特殊的情况
总结

一、时间复杂度和空间复杂度是什么？

1.1算法效率定义

算法效率分为两种，一种是时间效率――时间复杂度，另一种是空间效率――空间复杂度

1.2时间复杂度概念

时间复杂度，简言之就是你写一个代码，它解决一个问题上需要走多少步骤，需要花费多长时间。打个简单的比方：现在给10个数，要求找到7在哪里1,2,3,4,5,6,7,8,9,10。我们要求写一个代码，同学狗蛋写了一个暴力查找，从第一个数依次往后遍历，他的算法要找7次，同学狗剩写了一个二分法查找，只要找2次，这就是时间复杂度的比较
算法中的基本操作的执行次数，为算法的时间复杂度

1.3空间复杂度概念

空间复杂度，是对一个算法在运行过程中临时占用存储空间大小的量度。举个栗子：我们现在要求写一个代码，狗蛋啪啪啪敲了一大堆变量，程序运行了，狗剩就用了很少的变量，程序也运行了。但是他们两个在代码运行中变量多少不同，占用的内存多少是不一样的。空间复杂度，它计算的是变量的个数。

二、如何计算常见算法的时间复杂度和空间复杂度

我们在计算时间/空间复杂度时用的都是大O渐进表示法（是一种估算法）

2.1时间复杂度计算

我们以一个简单的函数举例
代码如下：

void func1(int n)
{
	int i = 0;
	int j = 0;
	int k = 0;
	int count = 0;
	for (i = 0;i < n;i++)
	{
		for (j = 0;j < n;j++)
		{
			count++;
		}
	}
	for (k = 0;k < 3 * n - 1;k++)
	{
		count++;
	}
}

试问：该函数如果被调用，要运行多少次？
我们清楚的看出i进去有n次，共有n个i，第一个for结束要运行n^ 2次，第二个for要执行3n-1次，共执行n^ 2+3n-1次
那么我们这里的时间复杂度是否就是n^2+3n-1呢？答案是否的
我们前面说过，时间复杂度和空间复杂度用的都是大O渐进表示法，是一种估算法

我们取的值，是取对表达式中影响最大的那个

我们以n^ 2+3 * n-1这个式子进行举例：设f(n)=n^2+3n-1
n=1,f(n)=1+3-1=3
n=10,f(n)=100+30-1=129
n=100,f(n)=10000+300-1=10299
n=1000,f(n)=1002999
…
很容易发现，对f(n)影响最大的是n^ 2,设g（n）=n^2
n=1,g(n)=1
n=10,g(n)=100
n=100,g(n)=10000
n=1000,g(n)=1000000
…
当n越大，g（n）就越接近f（n）
那么这里的时间复杂度大O渐进表达法写法是这样的：O(n^2)

2.2空间复杂度计算

在学习空间复杂度的求解之前，我们要知道，空间复杂度也是用大O渐进表达法进行求解，我们计算的不是所占空间大小，而是变量的个数。先来看一段代码：
代码如下（示例）：

#include<stdio.h>
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;
	}
}

在上面这个代码中，我们创建了三个变量分别是size_t end、int exchange、size_t i，尽管我们这个函数会经历很多的循环，但这三个变量是反复使用的，也就是说他们所占的空间是被反复使用的，空间的多少是没有变的,这里区别时间复杂度――时间是累计的，空间是不累计的（对于时间复杂度，每次循环都会被计算；对于空间复杂度，空间是可以被反复使用的）。

我们上面说过，空间复杂度计算也是用的大O渐进表示法，对于常数，我们统一用O(1)表示（大O渐进表示法详情见时间和空间复杂度篇1）

ps1:assert通常用于诊断程序中潜在的BUG，通过使用assert(condition)，当condition为false时，程序提前结束运行，利于程序BUG的定位。
ps2:size_t是一种类型，把它看作long unsigned int

我们再来看一段代码：
代码如下（示例）：

//计算bubblesort的空间复杂度
#include<stdio.h>
long long Factorial(size_t n)
{
	return N < 2 ? N : Factorial(n - 1)*n;
}

这段代码是一个很简单的递归实现阶乘运算，那么它的空间复杂度是多少呢？我们先假设传过去的n=10。

C语言数据结构时间复杂度及空间复杂度简要分析

10传过来我们会进行10次递归，每次递归是创建一个函数栈帧（也就是一个空间），共创建10次，每一次的空间复杂度都是O（1）。把10换成n，也就是进行n次递归，每次递归会创建1个函数栈帧，空间复杂度是O(n)。

ps：可能会有小伙伴问，那函数栈帧递归往回走的时候不是销毁了吗？注意：这里的空间复杂度是计算的“最坏、最多的情况”，况且不管是什么函数，在使用过后其栈帧都会销毁，空间复杂度算的是它用的空间最多的时候。

2.3快速推倒大O渐进表达法

1.常数1代替所有加法运算中的常数
2.只保留最高阶（高数极限思想）
3.若最高阶存在且不为常数，则去除最高阶的系数，比如3*n^ 9，去掉系数变为n^9

我们再来看两个代码训练一下
代码1如下：

void func2(int n)
{
	int i = 0;
	int k = 0;
	int count = 0;
	for (i = 0;i < 3n;i++)
	{
		count++;
	}
	for (k = 0;k < 6;k++)
	{
		count++;
	}
}

这里f（n）=3n+6，它的大O渐进表达法就是O（n）

代码2如下：

void func3(int n)
{
	int i = 0;
	int count = 0;
	for (i = 0;i < 1000;i++)
	{
		count++;
	}
}

这里一眼就看出是运行1000次，用什么来表示呢？前面说过：常数1代替所有加法运算中的常数，所以这里不管常数有多大，只要你只有一个常数都用O(1)表示

一些注意事项：

O(1)这个时间复杂度的估值是不随n的改变而改变的，以大白话说，不管你输入的n是多少，我这个算法的效率是不变的

O(n)这个时间复杂度是随n改变的
打个通俗的比方：设一个函数O(x)=1,那你x随意多少，函数值都是1
设一个函数O(X)=x，那这里函数值就随x变换而变换了

三、一些特殊的情况

有些算法的时间复杂度是存在最好、平均、最坏情况：
最坏情况：任意输入规模的最大运行次数（上界）
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数（下界）
不多说，举例说明：
代码如下：

const char*strchr(char*str, char c)
{
	while (*str != "")
	{
		if (*str == c)
		{
			return str;
		}
		++str;
	}
	return NULL;
}

上面的代码是一个简单的查找字符的函数，比如我们现在给一串字符共n个字符“aaaaba…aaac”（省略号省略a）
这里查找a一下子就找到了，查找b要点功夫，查找c就更慢了，如果查找d，不好意思，查无此d。
那么这里就出现了最好情况：一次找到O（1）
平均情况：O（n/2）
最差情况：O（n）
对于这里最坏情况可能有同学要说为什么是O（n），你看最坏情况没找到不是吗？这里解释是这样的，你找c要n次，找d是找不到也要找n次才能确定找不到。