算法的复杂度

一、算法的效率

在完成同一个算法题的过程中会有许多的方式和方法，最终完成的效果都是相同的都是正确的，但效率可能会有所差异。
就像在同一的地点出发要到到达另一个地点一样，到达地点的方式有飞机、火车、私家车……，但所用的时间不同，经济也不同。

1、复杂度的概念

算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源 。因此衡量⼀个算法的好坏，⼀般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。
在计算 机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展，计 算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。

2、复杂度的重要性

在我玩一些游戏的时候，有的游戏玩起来手机会很烫，有的游戏玩起来不烫，就离不开复杂度，我的手机在运行简单的算法很快就运行完了，但运行复杂的算法，要确保时间用的少就要启用全部功率，这样就会发烫。

二、时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？

• 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。
• 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。
• 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

所以在判断算法的时间赋值度时不 考虑执行算法的时间，只看执行多少次指令。

案例：

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

通过过观察：
Func1执行的基本操作次数：
T(N)=N²+ 2*N + 10

实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执⾏次数意义也不⼤，因为我么计算时间复杂度只是想⽐较算法程序的增⻓量级，也就是当N不断变⼤时T(N)的差别，上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩，所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

三、空间复杂度

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。
空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。
注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定
空间在现在的计算机发展中不是考虑的重点，但也要避免过度的浪费，浪费多了也会产生不必要的问题。

四、大O的渐进表示发

⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号
推到大O渐进表示法的规则：

• 1、时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，
  低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
• 2、如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数
  对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
• 3、T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。

最坏情况：任意输⼊规模的最⼤运⾏次数(上界)
平均情况：任意输⼊规模的期望运⾏次数
最好情况：任意输⼊规模的最⼩运⾏次数(下界)
⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。

五、计算复杂度案例

1、计算Func1函数的复杂度

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

时间复杂度：

把运行一次代码的省略比如count=0，这条代码.
保留对运行时间影响大的代码执行次数
第一个循环的执行次数是一个两次循环执行次数为NN
第二个循环为一层循环执行次数为2N
第三次循环为10次
执行次数和为T(N)=N²+2*N+10
大O表示时间复杂度，把影响小的舍去取极限
O(N²)

空间复杂度：

Func1函数申请空间的大小，如int count = 0，申请了int类型的空间大小，int M=10，也是申请了int类型的空间.
在循环中也是使用这两个空间没有额外申请空间。
申请空间大小为常数
用大O表示空间复杂度为：
O(1)

2、计算Fun2的时间复杂度

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

时间复杂度：

代码运行的次数较大的为第一个循环运行次数为N*2
第二个循环运行10次
用大O表示时间复杂度，影响最大的为2*N，省略前面的系数项：
O(N)

3、计算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);
}

时间复杂度

有两个未知数，影响较的是两个循环
第一个循环运行M次
第二个循环运行N次
应为是未知数不确定谁大谁小都不省略
O(M+N)

4、计算Func4的时间复杂度

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

时间复杂度：

这里影响最大的是一个循环
循环运行的次数为100
是一个固定的常数
O(1)

5、计算strchr的时间复杂度

const char* strchr(const char* str, int character)
{
	const char* p_begin = str;
	while (*p_begin != character)
	{
		if(*p_begin == '\0')
			return NULL;
		p_begin++;
	}
	return p_begin;
}

这个函数完成的功能是在一个数组中找一个字符在这个数组中的下标。
这里运行次数是不确定的
有可能一次就找到了F(N)=1
有可能在中间找到了F(N)=N/2
有可能最后才找到，或者找不到返回NULL，F(N)=N
大O是取最坏的情况：
时间复杂度为O(N)

6、计算Func5的时间复杂度

void func5(int n)
{
	int cnt = 1;
	while (cnt < n)
	{
		cnt *= 2;
	}
}

这个运行次数是根据n的大小有关，但不是循环n次，应为在循环时循环变量会乘2，会很快的跳出循环，运行十次循环变量cnt的值就会来到1024
设循环次数为x,则2^x=n
x=logn
所以时间复杂度为:O(longn)

7、计算BubbleSor的复杂度

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-1)+(n-2)+(n-3)+……+2+1+0
是一个等差数列，求和为：

时间复杂度为：O(N)

空间复杂度：

没有额外申请空间，申请的空间为常数
O(1)

8、计算阶乘递归Fac的复杂度

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

时间复杂度：

递归了N次
所以时间复杂度为：O(N)

空间复杂度：

每次递归都要申请空间
递归了N次申请了N次空间
空间复杂度为：O(N)