数据结构第一课——时间复杂度和空间复杂度

引入

数据结构和数据库的区别？

数据结构：在内存中管理数据，速度快，带电存储。

数据库：在磁盘中管理数据，速度慢，不带电存储。

一、时间复杂度

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

直接上实例！

实例1：

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

这是较简单的一个例子，只需要计算其循环次数即可。

其中，for循环执行了2*N次，while循环了10次。

故：F(N) = 2N + 10. 

在求时间复杂度时，忽略掉系数和常数，保留最大项。

故：例1的时间复杂度为 O(N)。

实例2：

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

可以发现，这里有两个未知数：N和M。

求F(N)，发现 F(N) = M + N ，N和M的指数相同。

在求时间复杂度时，遇到这种两个及以上未知数，且指数相同时，可以分情况讨论，也可以直接将两个未知数都带上。如：

1.两个未知数都带着：

O(M+N)  或  O(max(M,N))

2.分情况讨论：

N远大于M时：O(N)

M远大于N时：O(M)

N和M差不多大时：O(N) or O(M)

实例3：

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

这里循环次数为常数，时间复杂度直接写为 O(1).

注：此处的 1 表示常数次，而不是1次。

时间复杂度的保守估算

另外有些算法的时间复杂度存在最好、平均和最坏情况
最坏情况: 任意输入规模的最大运行次数(上界)
平均情况: 任意输入规模的期望运行次数
最好情况: 任意输入规模的最小运行次数(下界)
例如: 在一个长度为N数组中搜索一个数据X
最好情况: 1次找到
最坏情况: N次找到
平均情况: N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

在上述3例中，都可通过数循环来确定时间复杂度，但事实并非如此。

实例4：

// 计算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个数据的数组冒泡排序共需n-1趟，

第一趟需比 n-1 次；

第二趟需比 n-3 次；

第三趟需比 n-4 次；

...

第 n-3 趟需比 3 次；

第 n-2 趟需比 2 次；

第 n-1 趟需比 1 次；

刚好凑成一个等差数列，而等差数列求和，得到

共需比较 (n*(n-1))/2 次，也就是循环需要执行 (n*(n-1))/2 次；

故：F(N) =  = 

去除系数，保留最大项，得到时间复杂度 O为O(N^2)。

通过例3，我们知道，求时间复杂度是要根据算法思想来计算，而非数循环次数。

切记：时间复杂度的计算不能数代码中的循环，要根据算法思想，灵活计算。

实例5：

// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{
	assert(a);
 
	int begin = 0;
	int end = n - 1;
	//[bedin, 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;
}

这是一个二分查找算法。

在这个算法里就没法用数循环的方式来判断时间复杂度了。

那么来看思想：二分查找（即折半查找）-- 将一个数组每次砍掉一半。

最坏的情况下是将数组砍到一个元素为止，对于一个有n个元素的数组则需要砍 次；

故此算法的时间复杂度为：O()。

实例6：

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

这个递归方程的调用步骤如下：

每次递归n-1；

Fac(N) -> Fac(N-1) -> Fac(N-2) -> Fac(N-3) -> ... -> Fac(2) -> Fac(1) -> Fac(0)

总递归次数：将其累加，即为0—N的等差数列， 与实例4相同。

故时间复杂度为：O(n^2)。

实例7：

long long Fib(size_t N)
{
	if (N < 3)
		return 1;
 
	return Fib(N - 1) + Fib(N - 2);
}

斐波那契的执行看下图：

第一回：执行一次；第二回：执行2次；第三回：执行4次；第四回：执行8次....

能归纳出斐波那契递归的执行次数是一个等比数列（虽然最终图像呈一个斜线收尾，但对于整体的影响不大，因为时间复杂度本身就是一个估算）： 

简化一下，时间复杂度为：O(2^N)

二、空间复杂度

概念：

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

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

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

因为随着计算机硬件的发展，空间对于计算机的影响越发轻微，所以现在对于空间复杂度的考察基本很少。

偶尔在做OJ题时可能会遇到约束空间复杂度为O(1)的这种情况。在以后遇到这种情况是我们再展开细嗦。