数据结构初阶——时间复杂度

朋友们我们又见面了，今天我们来学习数据结构的时间复杂度，在讲数据结构之前，大家可能只知道我们学习的是数据结构，但是还是不知道数据结构的具体定义，其实就是在内存上的数据。然后我们就像通讯录一样对它进行增删查改。

1. 什么是数据结构？

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

今天我们的内容就是数据结构中的时间复杂度，时间复杂度听起来好像是在比较它们的运算时间，其实并不是只是字面上的意思，我们来细看吧。

目录

1.算法效率
2.时间复杂度
3.空间复杂度
4. 常见时间复杂度以及复杂度oj练习

我们今天围绕着上面的内容来依次学习。

1.算法效率

1.1 如何衡量一个算法的好坏

我们下面给一个代码，是斐波那契的递归实现，代码很简短，但是我们觉得它的效率高吗。

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个斐波那契数。
但是递归是有缺陷的，当深度够深的时候，它的效率大大的减慢。还不如我们用迭代的方式实现，所以代码越简单，并不是效率高。

那我们应该拿什么来衡量一个算法的效率呢

1.2算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.时间复杂度

时间复杂度的概念

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

那我们下面来给一个例子，我们来算一下在这段代码里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;
	}
	printf("%d\n", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

我们可以看到第一个for循环是个双层的for循环，所以执行N的2次方 ，第二个又是执行2*N次
然后加上一个常数M。整合起来就是-》

当我们的N趋向于无穷大的时候，我们这里只看最高次的项就行了，我们用大O的渐进表示方那就是O（N*N）

2.2 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项

我们的大O渐进表示法就可以去掉那些对我们的结果影响不大的项，简洁的表明了执行次数。

我们的算法是存在最好，最坏和平均情况的，为什么这样说呢

这个可以拿我们的算法中最常见的排序来说，就举冒泡排序来讲，冒泡排序最好的情况就是遍历第一遍数组的时候，发现有序，就可以排序好了，这就是我们的最好情况，但是也有最坏的情况，那就是如果我们的数组是逆序的话，那就是最坏的情况，最坏的情况下的时间复杂度用大O渐进表示那就是O（N*N）大家可以写成O（N的平法），打那个符号的时候变成……，大家理解就行了

那这里我们就可以对它进行分类，我们分为最坏情况，最好情况，还有平均情况。

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

2.3常见时间复杂度计算举例

那我们要评价一个时间复杂度的大O渐进法就得使用最坏的情况，我们下面来看几个例子。
在讲之前，大家算他们的时间复杂度的时候不能只看代码，也不是看这个代码实行了几次，而是我们要看他的算法思想，这样才能算出他们的时间复杂度，我们可以假设这个例子，比如我们要写一个代码，大家肯定都在牛客网上和leetcode上见过一些题目对我们的时间复杂度有限制，所以我们在写代码肯定要先构思路，那这个时候就要去想它的思想，这也是时间复杂度的好处，所以我们在计算它的时间复杂度的时候我们需要去看它的思想，而不是它的代码。

// 计算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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

那我们来计算这个的时间复杂度
前面几个例子我们都是先计算准确的，然后在计算用大O渐进表示的。
我们可以看到这里的count执行次数Func2（） = 2*N +10
所以我们可以写成O（N）。

大家可能对这里有点疑问就是为什么我们系数可以直接去掉，这里我给出的原因就是当N趋向于无穷大的时候，极限就是N，所以可以直接去掉系数，还有就是常量也可以直接去掉，这里还要和大家说我们如果执行的是常量次的话，我们也可以直接写成O（1）.（后面也有例子）

// 计算Func3的时间复杂度？
void Func3(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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这里首先我们可以看到的是M和N都是变量，所以要分开分析，如果M和N差不多大的时候我们就可以写成O（M+N），当M远大于N的时候，就可以写成O（M），相反如果N远大于M的时候，我们就可以写成O（N），那如果他们两个是差不多大的时候，我们就可以写成O（N）。

// 计算Func4的时间复杂度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d", count);
}
1
2
3
4
5
6
7
8
9
10

这题大家一定要擦亮自己的眼睛，不要以为K是个变量，这里就是常数项，所以就可以写成O（1）

下面这个是一个库函数，如果不了解的话，可能就想不出来，但是我们可以用Cplusplus进行查询

const char * strchr ( const char * str, int character );
1

它的作用就是找到字符在这个字符串中的位置。
那我们就好比查找一样，是需要遍历一下这个字符串的，然后遇到这个字符就返回它的地址，那我们如果假设要找的这个字符在最后的位置，那我们就是遍历字符串，所以就是O（N）。

// 计算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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在冒泡排序中再次强调我们计算时间复杂度的时候是要看他们的思想，不是看他们的代码，比如现在这个代码的话，冒泡排序第一次是找到最大的数字（假设是升序）放到这个数组的末尾，那第一次比较的次数是（n-1）次，因为一次排序，我们的最大的数已经找到，所以下一次比较的次数就是n-2，依次下去到1就是一个等差数列，那后面也不多说了，最后用等差数列的结果我们在根据大O渐进法来计算就行。答案就是O（N*N）

我们再来看一个二分查找的题目。

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

二分查找的思路就是一次查找我们会去掉一半的数据，然后在在另一个区域里进行查找，所以二分查找的效率是特变高的，那我们来计算它的时间复杂度也就好理解很多了，就是（logN）

其实这些有些内容我在之前更过，但是感觉不是特别好，加上我总是忘记之前学得，在学一遍，在写一遍代码，也让自己回忆一下，那今天的分享就到这里，明天继续学习。