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

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

一、算法效率

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

以上是斐波那契数列的递归实现，可以看出，这段代码十分简洁，但是我们是不是说
简洁的代码就一定很好呢，我们该以什么标准来衡量一个算法的好坏呢？按照以往的
经验，我们在解决OJ问题时，经常会遇到因为运算超时或者申请内存空间太多而导致的错误，而与这两个错误相对应的时间复杂度和空间复杂度便是我们判断算法好坏的重要标准。

2.算法的复杂度

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

3.复杂度的应用

我们以校招的面试问题和OJ题为例

从图中我们可以看出，像是腾讯这样的大厂在一面时都会考察最基本的时间复杂度问题，而剑指offer中很多企业用来对我们进行考核的编程题也是非常注重对复杂度的理解和应用，所以想要找到一个好工作，学好算法，学好复杂度是必要的。

二、时间复杂度

1.时间复杂度的概念

首先我们来看一下时间复杂度的定义:在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
即：找到某条基本语句与问题规模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++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

我们可以看出，这个函数执行了多少次基本操作，count最后得到的值就是多少,并且直接写出count随着N变化而变化的函数

当N=10时，count的值即F(N)的执行次数是130次
当N=100时，F(N)的执行次数时10210次
当N=1000时，F(N)的执行次数时1002010次

可以看出，随着N越来越大，后面的2*N+10对算法的运算次数的影响相对N^2来说越来越小。而我们实际在计算时间复杂度时，并不一定要计算精确的执行次数，而只需要大概的执行次数即可，所以这里我们使用大O的渐进表示法。

2.大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
使用大O的渐进表示法以后，Func1的时间复杂度为：
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

现在我们已经基本了解了大O的渐进表示法的原理，下面让我们来做一些练习来掌握如何在对一些典型的算法进行时间复杂度的计算

3.常见时间复杂度的计算举例

实例1：

// 计算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

实例1基本操作进行了2N+10次，我们根据大O的渐进表示法可算出其时间复杂度时O(N)。注意这里不要错写作O(2N)，大O的渐进表示法是要舍去相乘的系数的。

实例2：

// 计算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

实例2基本操作执行了M+N次，有两个未知数M和N，由于我们不知道M和N的大小关系，故这里要将时间复杂度表示为 O(N+M)

实例3：

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

实例3基本操作执行了10次，即进行了常数次数的操作，通过推导大O阶方法，时间复杂度为 O(1)

实例4：

// 计算strchr的时间复杂度？
const char* strchr(const char* str, int character);
1
2

实例4基本操作执行最好1次，最坏N次，而我们在计算时间复杂度时一般看最坏情况，故该例时间复杂度为 O(N)，这里附上strchr在cplusplus网站上的解释

实例5：

// 计算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

实例5基本操作执行最好N次，最坏执行了(N*(N+1)/2次，通过推导大O阶方法，时间复杂度一般看最坏，故该例时间复杂度为 O(N^2)

实例6：

// 计算BinarySearch的时间复杂度？
int 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;
		else
			return mid;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

实例6基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN) ps：logN在算法分析中表示是底数为2，对数为N。有些地方会写成lgN。
如上所述，我们先来介绍一下我们如何计算这个时间复杂度。我们可以看出上述代码使用了“二分查找（折半查找）”的算法，执行状况最好就是所需要查找的数刚好就在中间位置，最坏的情况是直到查找到最后一个位置即left和right的值是相等的时候才查找到我们需要的数。对于最坏的情况，我们可以假设进行了x次运算后，找到了最后一个位置，而二分查找每次都越过left到right之间一半的数组长度，所以有2^x=N(N为数组长度)，得到x为logN，故该算法的时间复杂度就是O(logN).

实例7：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}
1
2
3
4
5
6
7

实例7通过计算分析发现基本操作递归了N次，时间复杂度为O(N)，主要考察是否对递归有一定了解

实例8：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
	if (N < 3)
		return 1;
	return Fib(N - 1) + Fib(N - 2);
}
> 实例8通过计算分析发现基本操作递归了2^N次，时间复杂度为O(2^^N)
> 这道题的计算相对来说复杂一些，我们借助数据结构阶段最常用的放大：画图，来帮助我们理解和计算这一道题
![在这里插入图片描述](https://img-blog.csdnimg.cn/62dbe8f059b2467e90c087d8fccc850c.png)
从上图可以看出，递归一次所进行的运算次数是2的1次方,递归两次所进行的运算次数是2的2次方，递归N次所进行的运算次数是2的N次方，所以这个算法时间复杂度是O(2^N).
1
2
3
4
5
6
7
8
9
10
11

上述八个例子基本概括了我们平时会用到的各种时间复杂度的运算模型，掌握了这些，相信以后计算大部分的时间复杂度都不会有问题了。接下来我们介绍空间复杂度。

三、空间复杂度

1.什么时空间复杂度

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

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定

以上便是空间复杂度的基本介绍，下面我们同通过四个例子来练习一下。

2.常见空间复杂度计算举例

实例1：

// 计算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

实例1使用了常数个额外空间，所以空间复杂度为 O(1)

实例2：

```c
// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t 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
17
18

实例2动态开辟了N个空间，空间复杂度为 O(N)。注意：上面的代码申请了N+1个变量空间，因为数组下标从0开始到N为止，所以必须申请至少N+1个空间

实例3：

long long Fac(size_t N)
{
	if (N == 0)
		return 1;
	return Fac(N - 1) * N;
}
1
2
3
4
5
6

实例3递归调用了N次，开辟了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

之前我们已经计算过了，这个算法的时间复杂度是O(2^N)，而通过画图我们很容易认为这个算法的创建了2的N次方个栈帧空间，错误的认为空间复杂度是和空间复杂度都是一个量级，实际上并不是这样

我们仍然一图形为例来解释如何计算这一算法的时间复杂度:我们首先要知道函数栈帧的创建规律：**由Fib(N)开始，第一个函数栈帧创建，然后运行到return语句时先FIb(N-1)创建栈帧,Fib(N-1)运行return语句时先给Fib(N-2)创建栈帧，一直按照这个规律，先一路创建N-1个栈帧到达Fib(2)，Fib(2)不会在进行更多的函数栈帧的创建，此时Fib(2)运行到return语句结束，创建的栈帧销毁，程序返回到程序为Fib(3)创建的栈帧之中，然后Fib(3)接着运行return语句，为Fib(1)创建栈帧，此时程序创建的栈帧数仍然是N-1，Fib(1)运行结束之后栈帧销毁再返回Fib(3)所在的栈帧空间,Fib(3)运行结束，返回Fib(4)…**以这样的规律不断进行函数栈帧的创建和销毁，程序最多同时创建N的量级个栈帧空间，而每个栈帧空间内只有常数个变量，故该算法最终的空间复杂度时O(N).

最后附上一张常见复杂度的对比图表帮助大家更好的运用复杂度的知识

通过以上的叙述，我相信大家一定对时间复杂度和空间复杂度有了一定的了解和计算能力，下面我们通过两个OJ来实践一下我们的所学。

四、复杂度oj练习

消失的数字

消失的数字OJ链接：https://leetcode-cn.com/problems/missing-number-lcci/

对于这样的题目，这里介绍三种方法
1.排序+二分查找，我们知道二分查找时效率很高的算法，但是它有一个致命缺陷，就是需要在数据有序的时候才可以使用
而即使是排序之王快速排序算法的时间复杂度都达到了O(N*logN),所以这道题虽然使用这种方法可以解决，但是并不推荐
2.运用位操作异或运算，这里也是在考察对位运算的了解，这里直接附上代码
int missingNumber(int* nums, int numsSize)
{   
   int a[numsSize+1];
   int i;
   for(i=0;i<numsSize+1;i++)
        a[i]=i;
    int ans=0;
    for(i=0;i<numsSize;i++)
    {
        ans^=a[i];
        ans^=nums[i];
    }
    ans^=a[numsSize];
    return ans;
}
3.运用数学公式，这是最为简单的方法，直接附上代码
int missingNumber(int* nums, int numsSize)
{
    int ans;
    int sum=0;
    int i;
    for(i=0;i<numsSize;i++)
    {
        sum+=nums[i];
    }
    int n=numsSize;
    ans=(n*(n+1))/2-sum;
    return ans;

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
26
27
28
29
30
31
32
33

轮转数组

3.2 旋转数组OJ链接：https://leetcode-cn.com/problems/rotate-array/

对于这一题，进阶的做法是时间复杂度为O(1),这里只阐述一下空间复杂度为O(1)的解法。对于题给这种轮转数组，我们
可以先将前k个逆转一次，再把后k个逆转一次，最后整体逆转一次，代码如下
void reverse(int *nums,int numsSize,int start,int end)
{
   while(start<=end)
   {
       int tmp=nums[start];
       nums[start]=nums[end];
       nums[end]=tmp;
       start++;
       end--;
   }
}

void rotate(int* nums, int numsSize, int k)
{
    k%=numsSize;
    k=numsSize-k;
    reverse(nums,numsSize,0,k-1);//0到下标为k-1
    reverse(nums,numsSize,k,numsSize-1);//k到下标为numsSize-1
    reverse(nums,numsSize,0,numsSize-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

以上便是对数据结构中复杂度的解释了。这不过是基础中的基础，学习算法和数据结构之路才入门，你我都要好好努力。