数据结构入门【算法复杂度】

1.数据结构前言

1.1 数据结构

数据结构是计算机存储，组织数据的方式，指相互之间存在的一种或者多种特定关系数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以就有各式各样的数据结构，如：线性表，树，图，哈希等。

1.2算法

算法就是一系列的计算步骤，用来将输入数据转化成输出结果。4

1.3算法效率

复杂度的概念：
算法在编写成可执行程序时，运行时需要耗费一定的时间和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度衡量算法运行所需要的快慢，空间复杂度是衡量算法运行时所需要的额外的空间。

2.时间复杂度

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运行时间。
我们知道算法程序被编译后生成二进制指令，程序运行，就是cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式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(N)=N²+2N+M
此时这个式子为一元二次方程，对式子影响结果最大的就是N²。所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法。

3.大O渐进表示法

3.1大O渐进表示法概念

大O渐进表示法：是用来描述渐进的数学符号。
推导大O的规则：

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

3.2时间复杂度示例

示例一：

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

Func2的时间复杂度为： O(N)
示例二：

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

Func3的时间复杂度为： O(1)
示例三

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

T (N) = M + N
因此：Func4的时间复杂度为： O(N)

4.空间复杂度

空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
注意：函数运⾏时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

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

BubbleSort额外申请的空间有exchange等有限个局部变量，使用了常数个额外空间。
因此空间复杂度为 O(1)