初阶数据结构：时间与空间复杂度

前言

数据结构与算法：
计算机中各种各样基本类型的数据都在存储空间放置，它们的存储并不是杂乱无序的，各有各的放置方式，而此种数据间的组织排列与放置方式，我们就称之为数据的结构。
编程的目的在于借助计算机来解决我们在生活工作中所遇到的各种问题，解决问题的方法步骤多种多样，繁琐不一。我们将现实生活中的事物信息问题等抽象成数据，那么解决问题的方式就变成了怎样处理这些数据从而得出想要结果的方法步骤，我们所要学习的算法即是寻求解决问题的最优与最简方法步骤。

数据结构与算法的重要性：
当数据之间存在着联系，互在逻辑上构建成一个整体等情况时，它们于存储空间中的排列方式会影响我们编写出程序的效率。因此，我们不能随意将所需要的数据排列，而是应该通过主动干预设计数据在内存中的结构，从而选择最适用于场景的结构，如此就会大大提高我们的效率。数据结构对于程序的优化是在于计算机物理层面上的，而算法的优化，则是通过寻找逻辑上的最简法来实现提高效率的效果。

1. 时间复杂度与空间复杂度

1.1 算法的复杂度

根据上文所述，数据结构与算法的存在是为了提高程序的质量和效率，可我们应该如何判断一段代码，程序，它的效率高低，优化之后它的效率确实变得更高。无法认识解决以上问题，那么对于数据结构与算法的学习就没有意义，没有判断优劣的标准，优化与提升就无从谈起。接下来就让我门来进行相关知识的学习，算法效率的衡量标准，复杂度。

算法的复杂度：
衡量一个算法的好坏，一般会基于两个层面，一是时间（时间复杂度），二是空间（空间复杂度）。
时间复杂度是用来衡量一个算法其运行的快慢，而空间复杂度则是衡量算法以程序的形式在计算机中运行所需要调用的空间大小。

1.2 时间复杂度

算法的时间复杂度指的是一段程序在计算机中运行时间的长短吗？
事实并非如此，同一段程序，使得它们运行于两台性能迥然的计算机中，它们最后运行完成的时间亦是不同的，计算机的性能会干扰我们对程序本身效率的判断。那么，我们具体应该如何计算，又是以何作为计算的基准呢？具体如下：

1.2.1 时间复杂度的概念

我们已知物理上的时间印受电脑性能的影响不能称为判断的依据，所以在定义中，我们以程序的一条语句为基本单位，计算整个程序中有多少条语句，即执行语句的次数为算法时间复杂度的判断依据。

练习：

//此段代码的语句执行次数，即count的大小
void Func1(int N)
{
	int count = 0;
	int i = 0;
	for(i = 0; i < N; i++)
	{
		for(j = 0; j < N; j++)
		{
			count++;
		}
	}
	// n * n
	int k = 0;
	for(k = 0; k < 2 * N; k++)
	{
		count++;
	}//2 * N
	int M = 10;
	while(M--)
	{
		count++;
	}
	//M
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

答：$N^2$ + 2N + M 次。

算法的时间复杂度是一个函数，它反映了算法本身的运行速度，上文中提到，时间复杂度为判断算法优劣的一个标准，因此，我们不需要获知其准确的次数，只需要获知其大概语句执行次数处于哪一个层级即可。接下来我们来学习，时间复杂度的一种表示方式大O渐进表示法。

1.2.2 大O渐进表示法

大O符号是用于描述函数渐进行为的数学符号，大O阶计数实用方法：

1. 用常数1取代运行使劲按中所有的加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在且不为1，作为略去与最高阶项相乘的常数。

最终通过如上方法的到的，即为大O阶，上文的练习Fuc1的时间复杂度即为O($N^2$)

我们在计算时间复杂度时，在类似实现查找的很多情况下，算法需要的运行次数都会有浮动，这样我们应该作何处理呢，在这里我们引入，最好，平均，与最坏情况下的运行次数概念：
最坏情况：任意输入规模的最大运行次数（上界）
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数（下界）

示例：在一个长度为N的数组中查找到一个数据x
最坏情况：N次
平均情况：N/2次
最好情况：1次
在实际中一般情况只会关注的是算法的最坏情况，所以在数组中搜索数据的时间复杂度为O(N)

1.2.3 常见时间复杂度的计算练习

实例1：

void Func1(int N)
{
	int count = 0;
	int k = 0;
	for(k = 0; k < 2 * N; k++)
	{
		count++;
	}
	//2N
	int M = 10;
	while(M--)
	{
		count++;
	}
	//M：10次
	printf("%d\n",count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

复杂度为：O(N)

实例2：

void Fuc2(int N, int M)
{
	int count = 0;
	int k = 0;
	for(k = 0; k < M; k++)
	{
		count++;
	}
	//M
	for(k = 0; k < N; k++)
	{
		count++;
	}
	//N
	printf("%d\n",count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

复杂度为：O(N)

实例3：

void Fuc3(int N)
{
	int count = 0;
	int k = 0;
	for(k = 0; k < 100; k++)
	{
		count++;
	}
	printf("%d\n",count);
}
1
2
3
4
5
6
7
8
9
10

复杂度为：O(1)

实例4：

const char* strchr(const char* str, int character);
//strchrC语言中的一个库函数
//其作用为查找一串字符串中的一个字符的位置
1
2
3

复杂度为：O(N)

实例5：

void BubbleSort(int* a, int n)
//冒泡排序
{
	assert(a);
	size_t end = 0;
	for (end = n; end > 0; --end)
	{
		int exchange = 0;
		size_t i = 0;
		for (i = 1; i < end; ++i)
		{
			if (a[i-1] > a[i])
			{
				Swap(&a[i-1], &a[i]);
				//交换
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

复杂度为：O($N^2$)

实例6：

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

O($lo{g}_{2}N$)

实例7：

long long Fac(size_t N)
//递归，返回N 到 1之和
{
	if(N == 0)
	{
		return 1;
	}
	
	return Fac(N - 1) * N;
}
1
2
3
4
5
6
7
8
9
10

复杂度为：O(N)

补充：

long long Fac(size_t N)
{
	if(N == 0)
	{
		return 1;
	}
	size_t i = 0;
	for(i = 0; i < N; i++)
	{
		//........
	}
	
	return Fac(N - 1) * N;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

此段程序的时间复杂度为：（等差数列）
N + (N - 1) + (N - 2) + …+ 1 次
复杂度为：O(N)

实例8：

long long Fib(size_t N)
//递归实现求斐波那契数列元素
{
	if(N < 3)
	{
		return 1;
	}

	return Fib(N - 1) + Fib(N - 2);
}
1
2
3
4
5
6
7
8
9
10

等比数列求和：给数列乘以比数再与原数列相减（错位相减法）
复杂度为：O($2^N$)

1.3 空间复杂度

1.3.1 空间复杂度的概念

空间复杂度亦是一个数学表达式，其反应了一个算法在运行过程中临时占用存储空间大小的量度。与时间复杂度相同它不会准确地计算到底一段程序占用了内存空间多少个bytes，而是以程序中变量的个数为基准。空间复杂度的计算同样使用大O渐进表示法，规则与时间复杂度类似。
补充：函数运行时所需要的栈空间（存储参数，局部变量，部分寄存器信息等）在编译期间已经固定，所以空间复杂度主要计算函数运行时申请的额外空间。

1.3.2 空间复杂度练习

实例1：

//二分查找的空间复杂度
void 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-1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

三个局部变量
复杂度为：O(1)

实例2：

long long* Fibonacci(size_t n)
{
//返回前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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

长度n的long long类型的数列，一个局部变量
复杂度为：O(N)

实例3：

long long Fac(size_t N)
//阶乘
{
	if(N == 0)
	{
		return 1;
	}
	return Fac(N - 1) * N;
}
1
2
3
4
5
6
7
8
9

因为递归算法额外占用的空间，n个函数栈帧空间
复杂度为：O(N)

实例4：

long long Fib(size_t N)
//递归实现求斐波那契数列元素的空间复杂度
{
	if(N < 3)
	{
		return 1;
	}

	return Fib(N - 1) + Fib(N - 2);
}

1
2
3
4
5
6
7
8
9
10
11

空间复杂度为O(n)
时间是累加的的，一去不复返，而空间是可以重复利用的（可以理解为房子的退订）

空间重复利用实例验证：

//在两个不同函数中创建的变量地址相同
void func1()
{
	int a = 0;
	printf("%p\n", &a);
}

void func2()
{
	int b = 0;
	printf("%p\n", &b);
}

int main()
{
	func1();
	func2();

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

打印两局部变量地址：

2. 常见复杂度列举

一般算法的常见复杂度

复杂度由低到高自上至下