时间复杂度和空间复杂度

数据结构前言

什么是数据结构？

数据结构是计算机存储，组织数据的方式，相互之间存在一种或多种特定关系的数据元素的集合。

数据结构与数据库的区别

数据结构：在内存中管理数据--增删查改
数据库：在磁盘中管理数据--增删查改
1
2

什么是算法？

算法：一系列的计算步骤，将输入数据转化成输出结果。

算法效率

如何衡量一个算法的好坏

从时间复杂度和空间复杂度两方面去衡量

算法的复杂度

算法在编写成可执行程序之后，运行需要耗费时间资源和空间资源
便需要从时间复杂度和空间复杂度去衡量算法的好坏
1
2

时间复杂度主要衡量一个算法运行的快慢；空间复杂度主要衡量一个算法运行所需要的额外空间。

时间复杂度

时间复杂度的概念

算法的时间复杂度是一个函数，数学中带未知数的函数表达式。算法中基本操作的执行次数，就是算法的时间复杂度。

简单来说便是：找到某条基本语句与问题规模N之间的数学表达式，就是该算法的时间复杂度。

不能纯粹直接数循环，需要观察算法逻辑，计算时间复杂度。

实例如下

计算函数test中a++语句一共执行多少次

void test(int m)
{
	int i = 0;
	int j = 0;
	int k = 0;
	int a = 0;
	for (i = 0; i < m; i++)
	{
		for (j = 0; j < m; i++)
		{
			a++;
		}
	}
	for (k = 0; k < 2 * m; k++)
	{
		a++;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

test执行的基本操作次数
F(m) = m*m + 2*m
1
2

实际计算时间复杂度时，只需要计算大概执行的次数，这里便需要使用接下来学习的大O的渐进表示法

大O的渐进表示法

大O：用于描述函数渐进行为的数学符号

推导大O渐进法：

1. 用常熟1取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不为1，则去除最高阶项的常数表达式，得到的结果便是大O。

大O的渐进表达法删去对结果影响不大的项，简介明了地展示出执行次数。

有些算法的时间复杂度存在最好，平均和最坏的情况

最好：任意输入规模的最小运行次数（下界）
平均：任意输入规模的期望运行次数
最坏：任意输入规模的最大运行次数（上界）

实际中关注的是算法的最坏运行情况，所以数组中搜索数据的时间复杂度为O(N)

常见时间复杂度计算

实例1

void test(int m, int n)
{
	int a = 0;
	int i = 0;
	for (i = 0; i < m; i++)
	{
		a++;
	}
	for (i = 0; i < n; i++)
	{
		a++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1. m远大于n O(M)
2. n远大于m O(N)
3. m和n一样大 O(N)或者O(M)

实例2
计算冒泡排序的时间复杂度

void Bubblesort(int* str, int n)
{
	assert(str);
	int i = 0;
	int j = 0;
	for (i = n; i > 0; i--)
	{
		int exchange = 0;
		for (j = 1; j < i; j++)
		{
			if (str[j] > str[j + 1])
			{
				Swap(&str[j], &str[j + 1]);
				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

实例3

void test(int n)
{
	int a = 0;
	int i = 0;
	for (i = 0; i < 10000; i++)
	{
		a++;
	}
}
1
2
3
4
5
6
7
8
9

时间复杂度为O(1)，但不代表1次，而是代表常数次。

实例4

计算二分查找的时间复杂度

void Binarysearch(int* str, int n, int k)
{
	assert(str);
	int begin = 0;
	int end = n - 1;
	while (begin <= end)
	{
		int mid = begin + (end - begin) / 2;
		if (str[mid] < k)
		{
			begin = mid + 1;
		}
		else if (str[mid] > k)
		{
			end = mid - 1;
		}
		else
			return mid;
	}
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

实例5
计算斐波那契递归时间复杂度

long long Fib(int n)
{
	if (n < 3)
	{
		return 1;
	}
	return Fib(n - 1) + Fib(n - 2);
}
1
2
3
4
5
6
7
8

空间复杂度

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

空间复杂度计算规则基本与实践复杂度类似，同样使用大O渐进表示法

函数运行所需要的栈空间（存储参数，局部变量，一些寄存器信息等）在编译期间就已经确定好啦，因此空间复杂度主要通过函数在运行时申请的额外空间来确定

空间可以重复利用，不积累；时间一去不复返，需要积累

实例1

计算冒泡排序的空间复杂度

void Bubblesort(int* str, int n)
{
	assert(str);
	int i = 0;
	int j = 0;
	for (i = n; i > 0; i--)
	{
		int exchange = 0;
		for (j = 1; j < i; j++)
		{
			if (str[j] > str[j + 1])
			{
				Swap(&str[j], &str[j + 1]);
				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

冒泡排序额外占用的空间只有i,j,exchange，所以空间复杂度为O(1)

实例2

计算斐波那契递归空间复杂度

long long Fib(int n)
{
	if (n < 3)
	{
		return 1;
	}
	return Fib(n - 1) + Fib(n - 2);
}
1
2
3
4
5
6
7
8

由于空间可以重复利用，不积累；时间一去不复返，需要积累。所以开辟了N个栈帧， 空间复杂度为O(N)