[数据结构与算法]【数据结构(C语言描述)】时空复杂度

一、时间复杂度

时间复杂度：一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数。

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

举个例子：

void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;//N*N
		}
	}
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;//2*N
	}
	int M = 10;
	while (M--)
	{
		++count;///10
	}
	printf("%d\n", count);//将上面相加得 N*N+2*N+10
}

Func1 执行的基本操作次数 ：$N^2$$+2N+10$

当$N\to \infty$时，按照高数中${\lim }_{x\to \infty }$ 的思想,Func1基本操作大概次数为: $N^2$，该方法称为大O的渐进表示法。

大O的渐进表示法: 实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数。
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。记为： $O(\square )$

🔴注意：算法的时间复杂度存在最好、平均和最坏情况：
① 最坏情况：任意输入规模的最大运行次数(上界)
② 平均情况：任意输入规模的期望运行次数(期望对标概率论中的期望)
③ 最好情况：任意输入规模的最小运行次数(下界)

在实际中一般情况关注的是算法的最坏运行情况

大O法的规则：

1. 结果只保留最高阶项，且去掉系数
2. 结果若为常数,记为 $O(1)$

例题

例一：

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

Func2 执行的基本操作次数 ：$2N+10$
用大$O$法表示：$O(N)$

例二：

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

Func3 执行的基本操作次数 ：$M+N$
用大$O$法表示：$O(M+N)$

? ?情况分析：若$M<<N$,则 $O(N)$
? ?? ?? ? ?? ? ?? ? ?若$M>>N$,则 $O(M)$
? ?? ?? ? ?? ? ?? ? ?若$M\approx N$,则 $O(M)$或$O(N)$

例三：

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

Func4 执行的基本操作次数 ：$100$
用大$O$法表示：$O(1)$

例四：

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );

👉strchr函数的用法
考虑最坏的情况，用大$O$法表示：$O(N)$

例五：

// 计算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]);//第一轮N次，最后一轮1次，三角形面积计算得(N+1)*N/2
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

BubbleSort 执行的基本操作次数 ：$(N+1)N/2$
用大$O$法表示：$O(N^2)$

例六：

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

从BinarySearch的思想来看，一半一半的查找容易得： $O(lo{g}_{2}N)$

例七：

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

由图可得复杂度为： $O(N)$

例八：

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

由图可得执行的基本操作次数大概为 ：$2^N?1$
复杂度为： $O(2^N)$

二、空间复杂度

空间复杂度:是对一个算法在运行过程中临时额外占用存储空间大小的量度

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

例题

例一：

// 计算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;
	}
}

只开辟了end和i两块空间的大小，因此空间复杂度为：$O(1)$

例二：

// 计算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;
}

动态开辟了$N+1$个数组，还有$N?1$个i，因此空间复杂度为：$O(N)$
时间复杂度：$O(N)$

例三：

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

由图可知空间复杂度为：$O(N)$

例八：

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

因此空间复杂度为：$O(N)$

空间是可以重复利用的，但是时间是累计的。

三、常见复杂度对比

算法复杂度优先级：$O(1)>O(N)>O(Nlo{g}^N)>O(N^2)>O(2^N)>O(N!)$