【初阶数据结构】——时间复杂度和空间复杂度详解（C描述）_数组的时间复杂度

前言

什么是数据结构？

数据结构是计算机存储、组织数据的方式。指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

什么是算法？

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

这篇文章，我们就先来学习一下时间复杂度和空间复杂度。

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

斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

1.2 算法的复杂度

对于算法的“好坏”，我们一般用复杂度来衡量：

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

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。
在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

1.2 复杂度在校招中的考察

校招的笔试算法题和面试中都会考察对复杂度的计算和理解：

2. 时间复杂度

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

Func1 执行的基本操作次数 ：

这是它精确的执行次数，那这个就是该算法的时间复杂度嘛？
不是的。
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数。
那么这里我们使用大O的渐进表示法。

2.2 大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项（其余项对结果影响不大）。
3、如果最高阶项系数存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。
4、实际中一般情况关注的是算法的最坏运行情况

那么在使用大O的渐进表示法以后，Func1的时间复杂度就应该是：

O(n^2)

那为什么是O(n^2)呢？

根据第二条规则，对于运行次数函数

只保留最高阶，舍去其他项。

因为随着N越来越大，我们会发现总的执行次数越来越接近N^2的值，其它项对结果的影响越来越小：

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
总的来说，大O的渐进表示法是对算法执行次数的一个估算，算的是大概的次数所属的一个量级。

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

接下来我们就来一起做一些例题，练习一下。

例1双重循环

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

大家思考一下这个算法的时间复杂度应该是多少？

答案是O(N)。
怎么算的呢？
首先准确的执行次数很容易算出来是2n+10，那10 直接就可以去掉了，随着n越来越大，10对结果的影响就越来越小了，加不加都无所谓了。
那为啥不是2n呢？
这就对应了规则3，如果最高阶项存在且不是1，则去除与这个项相乘的常数。
就算是100，1万也要去掉。
所以最终答案是O(N)。

例2. 多未知数

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

这个时间复杂度又是多少呢？

是O(M+N) 。
准确的执行次数就是M+N，都是未知数，没有什么可以省去的项，所以就是O(M+N) 。

例3. 常数次循环

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

O(1)
总共执行了100次，是常数次。
这就对应了第一条：用常数1取代运行时间中的所有加法常数。
也就是说，只要一个算法的执行次数是常数次，不管多大，都是O(1)，当然执行常数次的算法，这个常数，一般也不会特别大。

例4. strchr

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

大家计算一下这个函数的时间复杂度是多少？

先给大家介绍一下这个函数吧。
这是一个库函数：
它就是在一个字符串中去查找一个字符，如果找到，返回该字符的地址，如果找不到，返回空指针。
那它的时间复杂度应该怎么算呢？

比如说，现在有这样一个字符串：

"abcdefgtioevdksjdx"
我们现在借助strchr来查找其中的一个字符，那会有一个问题：
就是如果我们找的字符是a，那上去一下就找到了，如果找的是x，那是不是要遍历到最后一个字符才能找到，假设是第N个。这是最好和最坏的情况，那当然还会有平均情况。

所以：

有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况。
所以数组中搜索数据时间复杂度为O(N)

那strchr的时间复杂度就也是O(N)了。

例5. 冒泡排序

//冒泡排序
void BubbleSort(int* arr, int n)
{
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		int j = 0;
		int flag = 0;
		for (j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				swap(&arr[j], &arr[j + 1]);
				flag = 1;
			}
		}
		// 一趟冒泡过程中，没有发生交换，说明已经有序了，不需要再处理
		if (flag == 0)
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

冒泡排序，相信大家应该都知道这个算法吧，它的时间复杂度又是多少呢？

我们来分析一下，冒泡排序就是两两比较嘛，比如升序的话就是前面比后面大，就交换。
假设N个数，就需要比较N-1趟，每趟比较的次数依次减1（因为每比一趟，就有一个数会交换到最终应该在的位置）。
那准确的次数就是N-1+N-2+...2+1.
是个等差数列，求和是N*（N-1）/2=1/2*N^2-1/2*N
那按照大O的渐进表示法，只保留最高阶，去掉常数系数，就是O(N^2)
有时候我们不用看代码，根据算法的思想就要能够计算出时间复杂度。

例6. 二分查找

再来看一个。二分查找：

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

二分查找其实每次都取中间值和我们要查找的值比，这样每次查找的范围就缩到原来的一半，最坏的情况就是一直缩小，一直缩小，直到就剩最后一个数字，如果是，就找到了，如果不是，就说明找不到。
假设有N个数，查找一次，范围就除2，最坏的情况就是一直除到等于1。

所以结果是log2N。
另外，时间复杂度的计算中log2N可以简写成logN。

例7. 递归求阶乘

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

是一个递归，求阶乘的递归。
递归调用了几次呢？
是不是N次啊，Fac(N )要调用Fac(N - 1) ，Fac (N - 1)再调用Fac(N - 2) ，以此类推，直到Fac(1)结束。
那每次递归有几次运算呢？
return 的时候有个相乘运算，就算加上if判断也就两次，那就是2N次。
那根据大O的渐进表示法吧常数系数2去掉，不就是O(N)嘛。

那现在我们对这个算法做一点改动，变成这样：

long long Fac(size_t N) {
	if (1 == N)
		return 1;
	for (int i = 0; i < N; i++)
	{
		;
	}
	return Fac(N - 1) * N;
}
1
2
3
4
5
6
7
8
9

这次它的时间复杂度又是多少？

我们看到这次多了一个for循环，循环N次，当然每次递归N会减1，第一次是N次（if判断和return的相乘我们就不加了，这个不影响的，而且时间按复杂度最终算的就是一个大概执行次数，当然你加上也没问题，建议这一块有时候不要考虑那么细致，有时反而会因此想不明白），那第二次N-1，然后N-2，…直到N=1，开始返回。
那总的次数其实就是一个等差数列：
N N-1 N-2 ... 3 2 1
求和就是N*（N+1）/2，那只保留最高阶，去掉系数，就是O(N^2)

所以，对于递归函数的时间复杂度的计算：

我们要算的就是每次递归调用的执行次数的累加，当然，得出的结果需要我们使用大O的渐进表示法再去简化。

例8. 递归求斐波那契第N项

long long Fib(size_t N) {
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}
1
2
3
4
5
6

这个算法的时间复杂度时多少呢？

是O(2^N)
我们一起来分析一下：
Fib(N)会递归调用Fib(N - 1) 和 Fib (N - 2) ，Fib (N - 1) 又调用Fib (N - 2)和 Fib (N - 3) ， Fib (N - 2)调用Fib (N - 3)和 Fib (N - 4)，以此类推，每个分支直到 N < 3开始返回：

最终结果是O(2^N)，这个效率是非常低的。求斐波那契第N项的算法写成循环/迭代的实现是比较好的。

3. 空间复杂度

3.1 空间复杂度的概念

空间复杂度又是什么呢？

空间复杂度也是一个问题规模n的函数，是对一个算法在运行过程中临时占用存储空间大小的量度 。

空间复杂度不是计算程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。

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

3.2 常见空间复杂度计算举例

例1.常数次循环

先来看一个简单的：

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

它的空间复杂度是多少呢？

O(1)
它里面是不是就创建了两个变量啊，count 和k ，那我们说了空间复杂度也使用大O的渐进表示法计算，申请两个变量的空间，常数个，那就是O(1)了。
注意：初始化循环变量的语句只执行一次。

例2.冒泡排序

第二个，冒泡排序的空间复杂度：

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

还是O(1)。
我们分析一下，它里面是不是就新定义了3个变量，额外申请了3个变量的空间啊。
那函数参数不算吗？
概念中已经提到了，数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
那3个变量，还是O(1)。

例3.返回斐波那契数列的前n项的数组

第三个：

// 返回斐波那契数列的前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

答案是O(N)
它里面动态申请了一个数组，n + 1个元素，另外还有几个变量，像指针变量long long* fibArray，for循环中还有个int i = 2，但还是常数个N+几，我们可以不用管，所以就是O(N)。

例4.递归求阶乘

再看一个：

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

这个是多少？

O(N)
递归调用了N次，开辟了N个函数栈帧（最后返回时才会逐一销毁），每个栈帧使用了常数个空间。空间复杂度为O(N)

例5. 递归求斐波那契第N项

long long Fib(size_t N) {
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}
1
2
3
4
5
6

该算法的时间复杂度我们求过了是O(2^N)，那空间复杂度呢？

是O(2^N)吗，不是的，它的空间复杂度是O(N)。
为什么呢？
时间是一去不复返的，是累加的，但是空间是可以重复利用的。

什么意思呢？

这是我们计算时间复杂度是分析的图，它递归调用了这么多次，但是，这么多分支，它们进行递归，开辟函数栈帧，是同时进行吗？
不是的。
它们是一个分支，一个分支按照先后顺序进行的。
Fib(N )=Fib(N - 1) + Fib(N - 2)
Fib(N - 1)递归调用完，才会开始Fib(N - 2)，它们会重复利用同一块空间。

最长的那个分支同时建立N个函数栈帧，所以空间复杂度为O(N)

4. 常见复杂度对比

5. 复杂度的oj练习

5.1 消失的数字

链接: link

链接放这里，大家可以自己做一下。

这里给两种解法：

1. 0到n求和减去数组元素之和
2. 让0和0到n异或，异或的结果和数组元素异或，最终得到的结果就是缺失的那个数字。
原理：0和任何数异或结果还是这个数，两个相同的数字异或结果为0。

上代码：

int missingNumber(int* nums, int numsSize){
    //思路一：0到n求和减去数组元素和
    // int i=0;
    // int sum=0;
    // for(i=1;i<=numsSize;i++)
    // {
    //     sum+=i;
    // }
    // int j=0;
    // for(j=0;j<numsSize;j++)
    // {
    //     sum-=nums[j];
    // }
    // return sum;

    //思路二：单身狗问题
    int i=0;
    int x=0;
    //x=0和0到n异或
    for(i=1;i<=numsSize;i++)
    {
        x^=i;
    }
    //x和数组元素异或
    int j=0;
    for(j=0;j<numsSize;j++)
    {
        x^=nums[j];
    }
    return x;
}
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

5.2 轮转数组

链接: link

还是给两种解法：

1. 再创建一个同样大小的数组，把需要轮转的元素放在数组前面，然后把剩余元素放到数组后面，再拷贝到原数组中。
另外需要注意，如果N个元素的数组，你轮转N次是不是就还和原来的一样，而且K如果太大，大于 题中的numSize，下标为负，还会越界访问，所以加上一句k%=numsSize;

void rotate(int* nums, int numsSize, int k)
{
    k%=numsSize;
    int arr[numsSize];
    int i=0;
    int j=0;
    //需要轮转的元素放在数组前面
    for(i=numsSize-k;i<numsSize;i++)
    {
        arr[j]=nums[i];
        j++;
    }
    //剩余元素放到数组后面
    for(i=0;i<numsSize-k;i++)
    {
        arr[j]=nums[i];
        j++;
    }
    //拷贝到原数组中
    j=0;
    for(i=0;i<numsSize;i++)
        {
            nums[j]=arr[i];
            j++;
        }
}
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

2. 先将前n-k个元素进行逆序，然后将剩余元素进行逆序，最后再逆序整个数组。
   

void reverse(int* start, int* end)
{
    while (start < end)
    {
        int tmp = *start;
        *start = *end;
        *end = tmp;
        start++;
        end--;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    //向右轮转numsSize次相当于没轮转
    k %= numsSize;
    reverse(nums, nums + numsSize - 1 - k);
    reverse(nums + numsSize - k, nums + numsSize - 1);
    reverse(nums, nums + numsSize - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

好了，以上就是这篇文章的全部内容，欢迎大家指正！！！