算法的时间复杂度和空间复杂度

发布时间:2023-04-13 14:00

目录

1.算法效率

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

1.2算法的复杂度 

2.时间复杂度

2.2大O的渐进表示法

2.3较为复杂的算法的时间复杂度的计算

2.3.1计算strchr函数的时间复杂度

2.3.2计算BubbleSort的时间复杂度

2.3.3计算BinarySearch的时间复杂度

2.3.4计算阶乘递归Fac的时间复杂度 

2.3.5计算Fib递归的时间复杂度

3.空间复杂度​​​​​​​

现在先来想这样一个问题,算法的时间复杂福和空间复杂度我们在哪里会用到呢?为什么学习这个东西?

如果你也有相同的疑问,就请看下面的这张图。算法的时间复杂度和空间复杂度_第1张图片

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

1.算法效率

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

如何衡量一个算法的好坏,我们可以以斐波那契的递归实现为例:

long long Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}

当然,现在我们还不知道怎样进行复杂度的计算,这道题的复杂度的计算我们就放在文章后面了。

一个问题:斐波那契数列的递归方式非常的简洁,但简洁就一定好吗?怎么去衡量它的好坏?

1.2算法的复杂度 

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

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

2.时间复杂度

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上来说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。算法在可以上机测试的,但是这样很麻烦,所以有了时间复杂度这个分析方式。

而且有时候算法上机测试出来的是不准确的,因为不同的机器算出的时间不尽相同。

比如说使用冒泡排序堆10000个数据进行排序:

使用i7cpu   16G内存的机器上机和使用i3cpu 2G内存的机器跑出来的结果是有很大不同的,一个算法的运行时间跟硬件配置也有关系,所以同样的一个算法是没有办法算出准确时间的。

综上所述,才有了时间复杂度这个分析方式,一个算法所花费的时间与其中语句的执行次数成正比例,算法中基本操作的执行次数,就是这个算法的时间复杂度。

找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。

示例1: 

请计算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()中++count语句执行的次数,我们可以通过一个函数表达式来表述:

F(N) = N*N + 2*N + 10,这个函数表达式是一个准确的,没有任何省略的。

我们发现,求出一个算法的准确函数表达式是没有任何意义的,主要是比较起来不方便,所以才有了大O的渐进表示法。 

2.2大O的渐进表示法

大O符号(Big O notation) :用于描述函数渐进行为的数学符号。

推导大O的方法:

  • 用常熟1取代运行时间中的所有加法常数
  • 在修改后的运行次数函数中,只保留最高阶项
  • 如果最高阶项存在而且不是1,则去除与这个阶项想乘的常数

这就是推导大O的三部曲,掌握了这三部,也就掌握了大O渐进表示法。

下面我们就可以使用大O渐进法来表示Func1()中的时间复杂度O(N^2)

示例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()中基本算法的准确的复杂度函数是F(N) = 2*N + 10,如果使用大O的渐进表示法的话Func2()的时间复杂度就是O(N)

示例3:

计算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);
}

还是和前两个示例一样,先算出准确的函数表达式F(N) = M + N,那么这样问题就来了,是M大还是N大呢,求时间复杂度的话就需要分情况进行讨论了:

  • M和N一样大时,O(N)或O(M)
  • M远大于N,O(M)
  • N远大于M,O(N)
  • M和N的大小关系不知道,O(N+M)

示例4:

计算Func4()的时间复杂度

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

算法基本操作语句执行的次数是常数次,所以时间复杂度是O(1)。

2.3较为复杂的算法的时间复杂度的计算

2.3.1计算strchr函数的时间复杂度

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

相信有很多人并不知道strchr这个函数是用来干什么的,这里给大家推荐一个查阅C/C++文档的网站:

C library - C++ Reference

算法的时间复杂度和空间复杂度_第2张图片

这个网站是我个人经常使用的,里面的文档很全面,有注释,有举例等。

查阅得到的是一个英文文档,这么和大家说吧,读英文文档是很大的能力提升,国内的文档也是从英文文档翻译出来的,而且有的翻译是错误的,所以我建议大家直接阅读英文文档,不会的单词或者句子可以借助翻译软件。

strchr函数:返回字符串目标字符的第一个出现的位置。

算法的时间复杂度和空间复杂度_第3张图片

 在分析和计算strchr函数的复杂度之前,先来介绍一下时间复杂度的最好,平均、最坏情况:

有些算法的时间复杂度存在最好、平均、最坏情况:         例如在长度为N的数组中查找数据X

最好情况:任意输入规模的最小运行次数(下界)              1次找到

平均运行情况:任意输入规模的期望运行次数                      N/2次找到

最坏情况:任意输入规模的最大运行次数(上界)               N次找到

 在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)。

strchr函数也是一个搜索算法,这里我们关注最坏情况,时间复杂度为O(N)

2.3.2计算BubbleSort的时间复杂度

void BubbleSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				flag = 1;
			}
		}
		if (flag == 0)
			break;
	}
}

冒泡排序的思想:每次进行两两比较,一趟找出一个最大值或者最小值到最后。

找出的这个最大值或者最小值之后不用再参与比较,只要比较前面的值即可,这里给大家找一张动图看一下:

算法的时间复杂度和空间复杂度_第4张图片

冒泡排序时间复杂度的分析和计算:

第1趟比较N-1次,第2趟比较N-2次,第3趟比较N-3次……第N-2趟比较2次,第N-1趟比较1次。

F(N) = N-1 + N-2 + N-3 + ......+ 2  + 1 = N(N-1) / 2

所以BubbleSort的时间复杂度为O(N),这也是最坏情况。

当然肯定有很多小伙伴也看到了,我们的这个BubbleSort是有一个优化的,这个优化之后是存在最好的情况的:

那就是只进行一趟比较,一趟比较之后break跳出循环  F(N) = N - 1;

最好情况下BubbleSort的时间复杂度是O(N)。

2.3.3计算BinarySearch的时间复杂度

int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int left = 0;
	int right = n - 1;
	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (a[mid] == x)
			return mid;
		else if (a[mid] > x)
			right = mid - 1;
		else
			left = mid + 1;
	}
	return -1;//没找到
}

BinarySearch时间复杂度的分析和计算:

算法的时间复杂度和空间复杂度_第5张图片

假设我们要查找的数组是一张A4纸,每查找一次的话就把纸对折一下,就这样一直对折,直到A4纸中只有一个数据,那这个数据要么是我们查找的数据,要么数组中没有我们要查找的数据。

假设这个过程中对折了X次,数组中一共有N个数据;

那么   2^X = N,X = logN,算法的执行次数就是logN次。

注意:因为要在文本当中写对数不好写,而时间复杂度中以2为低的对数经常出现,所以我们会把他简写为logN。

有些书籍或者博客资料会简写成lgN,其实这样是不太对的,如果看到的话,要知道其实写的就是以2为低的对数。

2.3.4计算阶乘递归Fac的时间复杂度 

long long Fac(size_t N)
{
	if (1 == N)
		return 1;
	return N * Fac(N - 1);
}

Fac中,每次函数调用算法的基本操作的次数为O(1),一共调用了N次,时间复杂度为O(N)

2.3.5计算Fib递归的时间复杂度

long long Fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fib(n - 1) + Fib(n - 2);
}

Fib递归的时间复杂度分析和计算:

算法的时间复杂度和空间复杂度_第6张图片

 综上Fib递归的时间复杂度为O(N)。

3.空间复杂度

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

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

空间复杂度计算规则基本和实践复杂度的计算规则相同,也使用大O的渐进表示法。

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

示例1: 

计算BubbleSort的空间复杂度

void BubbleSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)
	{
		int flag = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				flag = 1;
			}
		}
		if (flag == 0)
			break;
	}
}

BubbleSort在函数运行的时候没有申请额外的空间,所以空间复杂度为O(1)。

示例2:

计算Fib的空间复杂度(返回前N项)

long long* Fibonacci(int 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;
}

返回斐波那契的前N项使用malloc开辟了一个空间为N的数组,空间复杂度为O(N)

示例3:

计算阶乘递归Fac的空间复杂度

long long Fac(size_t N)
{
	if (1 == N)
		return 1;
	return N * Fac(N - 1);
}

Fac递归调用了N次,开辟了N个栈帧,每个栈帧使用了常熟个空间,空间复杂度为O(N)。 

到这里算法的时间复杂度和空间复杂度就结束了,阅读完的铁子们记得给个点赞、收藏+关注哦

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号