数据结构——复杂度(时间，空间)

注：以下用冒泡排序排序数组的统一都是排成升序

冒泡排序代码：

void Bubble_Sort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		int flag = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}

时间复杂度：

0.时间复杂度指的是算法中的基本操作的执行次数

例：

for (int i = 0; i < 10; i++)
{
	for (int j = 0; j < 20; j++)
	{
		printf("haha");
	}
}

该代码的printf执行次数为10 * 20 = 200

递归的时间复杂度计算方式依旧：

例：

int func(int n)
{
	if (n == 1)
	{
		return 1;
	}

	return func(n - 1) * n;
}

func的执行次数为n

1.不论是时间复杂度还是空间复杂度，都取的是最坏的情况

关于最坏的情况的定义：

举个例子：

用冒泡排序排序一个数组(已知该数组为5个元素但具体情况未知)，使之有序

那么冒泡排序需要最少排序0次，最多排序10次才能实现该数组有序

那么此时的最坏情况就是10次

2.推倒大O阶的方法：

(1).加法常数通通用1取代

(2).在得到了具体的复杂度表达式之后，只保留该表达式的最高阶项，并将前边的系数改为1

(3).如果没有最高阶项，即得到的具体表达式只有常数，则O(N) = 1

例：

推导出来的具体表达式为 2 *  N ^ 2 + N

那么此时的时间复杂度为N ^ 2

而第0点中的第一个例子的时间复杂度是1，第二个是n

3.要想推出具体的时间复杂度，则要用到数学知识，大部分都涉及到的是等差数列求和或等比数列求和

例：

用冒泡排序排列数组元素为N的未知数组，那么用数学分析如下：

按照第一点的最坏情况理论，该数组的

第一个元素想要排列完毕则要经过n - 1重循环

第二个元素想要排列完毕则要经过n - 2重循环

第三个元素想要排列完毕则要经过n - 3重循环

……

倒数第二个元素(即第n - 1个元素)想要排列完毕则要经过n - (n - 1)重循环

那么n - (n - 1) + n - (n - 2)+ …… + n - 3 + n - 2 + n - 1 即时间复杂度的具体表达式

运用等差数列求和公式得：

(n - 1) * (1 + n - 1) / 2

化简得：(n - 1) * n / 2

用第二点推导方法得：O(N) = n ^ 2

空间复杂度：

4.空间复杂度指的是一个算法在运行时临时占用的存储空间的大小

注：是临时！不包含那些一开始就分配好了的空间

例：

最上边的冒泡排序的空间复杂度就是1，因为他只用了常数次的临时变量，或称为只开辟了常数次的空间，所以按照第2点的推导方法，得冒泡排序的空间复杂度为1