02 时间复杂度和空间复杂度

发布时间:2024年01月14日

目录

  1. 算法效率
  2. 时间复杂度
  3. 空间复杂度
  4. 练习

1. 算法效率

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

比如裴波那切数列:

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

return Fib(N-1) + Fib(N -2) ;
}

它的递归方式很简洁,但一定好吗?怎么衡量算法的好坏?

1.2 算法的复杂度

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

时间复杂度主要衡量一个算法的运行快慢
空间复杂度衡量算法运行所需要的额外空间

在计算机发展的早期,存储容量很小,所以对于空间复杂度很在乎,但是经过迅速发展,计算机的存储容量已经达到了很高的程度。所以如今已经不需要再特别关注算法的空间复杂度

2. 时间复杂度

2.1 时间复杂度的概念

时间复杂度的定义: 在计算机科学中,算法的时间复杂度是一个函数(数学),描述了算法的运行时间,一个算法消耗的时间从理论上,是算不出来的,只有在机器上跑起来,才能知道,但每次上机测试很麻烦,所以有了时间复杂度的分析方式,一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度

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

//计算一下++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);

Func1执行的基本次数:

首先有两个for循环,就是N的平方次,下面的for循环次数是2*N,最后的while循环,次数固定是10

???F(N) = N2 + 2 * N + 10

  • N = 10 F(N) = 130
  • N =100 F(N) = 10210
  • N=1000 F(N) = 1002010
  • 实际中计算时间复杂度时,并不一定要一定要精确的执行次数,只需要大概执行次数,这个就是大O的渐进表示法

2.2 大O的渐进表示法

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

推导大O阶的方法:

  1. 用常数1取代运行时间中所有加法常数
  2. 在修改后的运行次数函数中,只保留最高阶
  3. 如果最高阶项存在且不是1,则去除与这个项目相乘的常数,得到的结果就是大O阶

当影响执行次数的变量特别大时,常数的影响微乎其微,时间复杂度只描述最高阶,同样,数量越大,1次方的影响和二次方比越来越小,常数系数也可以省略

这样,大O表示Func1的时间复杂度:

O(N^2^)
  • N = 10 F(N) = 100
  • N = 100 F(N) = 10000
  • N = 1000 F(N) = 1000000

大O渐进法去掉了对结果影响不大的项,简明表示出了执行次数

另外有些算法存在三种情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(上界)

例如找一个数据:
最好情况1次就找到,最坏情况N次找到,平均N/2次找到

在实际中一般情况关注的是最坏运行情况,底线思维。所以数组上面找数据的时间复杂度为O(N)

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

实际执行2 * N + 10 次,大O表示为O(N)

例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);
}

实际执行了M + N次,有两个未知数,所以为O(M + N)

例3:

// 计算Func4的时间复杂度?
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

实际执行100次,时间复杂度O(1),表示常数次

例4:

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

最好情况: 第一次就找到
平均情况: character/2
最坏情况: character次找到或未找到

时间复杂度为O(N)

例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;
	}
}

第一次执行end-1次
第二次执行end-2次
。。。
一直到执行1次

这是一个等差数列,求和 N(1 + N ) /2,大O结果为 O(N2)

例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;
}

二分查找,每找一次,数据集就会缩小当前的一半
第一次需要找N次
第二次需要找N/2次
第三次需要找N/2/2次
。。。
当数据集只剩1个时,就有了结果
假设找了x次,2x = N ,结果就是log2N

时间复杂度O(logN)

logN是优于N的,和折纸相似,可以将数据集扩大看看两者的差距
在这里插入图片描述当14亿数据集时,二分查找最多只需要31次就可以找到

例7:

// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
	if (0 == N)
		return 1;

	return Fac(N - 1) * N;
}

第一次递归Fac(N-1)
第二次递归Fac(N-2)
。。。
最后到Fac(0)

时间复杂度为O(N)

例8:

// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
{
	if (N < 3)
		return 1;

	return Fib(N - 1) + Fib(N - 2);
}

在这里插入图片描述
每一次都需要递归两个函数,公式为
F(n) = 20 + 21 + … 2(n-2)
2F(n) = 21 + 22 + … 2(n-2) + 2(n-1)

用错位相减法,可以抵消,得
2^(n-1) - 1
保留最高项,O(2n)

3. 空间复杂度

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

空间复杂度不是程序占用了多少bytes的空间,算的是变量的个数,也用大O渐进法表示

注意:函数运行时所需要的栈空间(存储参数、局部变量、寄存器信息等)在编译期间已经确定好了,空间复杂度是函数运行申请的额外空间来确定

例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;
	}
}

只有一个变量exchange,所以是O(1)

例2:

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

开辟了N+1个longlong,所以复杂度O(N)

例3:

// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{
	if (N == 0)
		return 1;

	return Fac(N - 1) * N;
}

在这里插入图片描述
每次开辟N个函数空间,每个栈帧使用常数个空间,O(N)

类似的,递归计算裴波那切数列的空间复杂度也是O(N)

因为时间是一去不复返的,空间是可以重复利用的,函数开辟的空间可以重复利用,每次只会执行一个函数

void fun1() {
	int a = 0;
	printf("%p\n", &a);
}

void fun2() {
	int b = 0;
	printf("%p\n", &b);
}

在这里插入图片描述

上面代码,执行后地址是一样的,证明两个函数用的同一份空间

4. 常见复杂度对比

5201314O(1)常数阶
3n+4O(n)线性阶
3n2+4n+5O(n2)平方阶
3log(2)n+4O(logn)对数阶
2n+3nlog(2)+14O(nlogn)nlogn阶
n3+2n2+4n+6O(n3)立方阶
2nO(2n)指数阶

在这里插入图片描述

5. 复杂度练习

在这里插入图片描述
第一种:
排序后,依次查找,如果下一个数不是上一个数加1,就找到了这个数

时间复杂度最好的情况是O(N*logN)

第二种:
将数组内所有数异或,再异或数组长度内每个数,就可以找到这个数

时间复杂度O(N)

int ary[] = { 9, 6, 4, 2, 3, 5, 7, 0, 1 };
int len = sizeof(ary) / sizeof(ary[0]);
int x = 0;

for (int i = 0; i < len; i++)
{
	x ^= ary[i];
}

for (int i = 0; i < len + 1; i++)
{
	x = x ^ i;
}

printf("%d", x);

第三种:
0-N等差数列公式求和,减去数组每个值
时间复杂度O(N)

int x = len * (len + 1) / 2;

for (int i = 0; i < len; i++)
{
	x -= ary[i];
}

printf("%d", x);

在这里插入图片描述
第一种:
暴力求解,旋转k次
在这里插入图片描述
时间复杂度:O(N2)
空间复杂度: O(1)

第二种:
三段逆置
在这里插入图片描述

void Reverse(int ary[], int left, int right)
{
	while (left < right)
	{
		int temp = ary[left];
		ary[left] = ary[right];
		ary[right] = temp;
		left++;
		right--;
	}
}

void Rotate(int ary[], int len, int k)
{
	if (k > len)
		k %= k;

	Reverse(ary, 0, len - k - 1);
	Reverse(ary, len - k, len - 1);
	Reverse(ary, 0, len - 1);
}

int nums[] = { 1, 2, 3, 4, 5, 6, 7 };
int len = 7;
int k = 3;
Rotate(nums, 7, k);
for (int i = 0; i < len; i++)
{
	printf("%d ",nums[i]);
}

时间复杂度: O(N)
空间复杂度: O(1)

第三种:
空间换时间
在这里插入图片描述轮转3个,先把后面的5,6,7放到新数组里,再把前面的拼上

void Rev(int ary[], int len, int k)
{
	if (k > len)
		k %= k;

	int* p = (int*)malloc(len * sizeof(int));
	memcpy(p, ary + len - k, sizeof(int) * k);
	memcpy(p + k, ary, sizeof(int) * (len - k));
	memcpy(ary, p, sizeof(int) * len);
	free (p);
	p = NULL;
}

时间复杂度:O(N)
空间复杂度: O(N)

文章来源:https://blog.csdn.net/qq_43422358/article/details/135579711
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。