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

【C语言】时间复杂度与空间复杂度

• 算法的效率
• 时间复杂度
• 空间复杂度

算法的效率

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

int Fib(int N)
{
	if(N < 3)
		return 1;
	return Fib(N-1) + Fib(N-2);
}

这种写法运算的时间很长，如果你把他放在你的编译器上，然后给这个函数传值50，会算很长时间才会出现结果（不算溢出）。 时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

时间复杂度

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

//计算complex函数中count变量进行了多少次运算
#include <stdio.h>
void complex(int N)
{
	int i = 0;
	int j = 0;
	int count;
	for (i = 0; i < N; ++i)
	{
		for (j = 0; j < N; j++)
		{
			++count;//运行了N*N次
		}
	}
	for (i = 0; i < 5 * N; ++i)
	{
		++count;//运行了5*N次
	}
	for (j = 0; j < 10; ++j)
	{
		++count;//运行了10次
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	complex(n);
	return 0;
}

一共运行了N2+5*N+10次 因为现代用的计算机CPU计算的速度非常快，所以不用计算到很细，只需要一个大概就可以了。 这里就用到了大O表示法： 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中，只保留最高阶项。 3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。 那么complex的时间复杂度为O(N^2). 在某些算法中分为最好，平均，最坏的情况，例如在一个数组中寻找一个数： 最好：第一个数就是我们要查找的数，O(1) 平均：中间的数是我们要查找的数。O(N/2) 最坏：最后一个数才是要查找的数。O(N) 在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N) 再举个例子

//计算Fib的时间复杂度
int Fib(int N)
{
	if(N < 3)
		return 1;
	return Fib(N-1) + Fib(N-2);
}

时间复杂度为 O(2N).

在这里插入图片描述

2(N-1)+ 2(N-2)+…20=2N-1

空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。 注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 我们还用这段代码举例：

//计算complex的空间复杂度
#include <stdio.h>
void complex(int N)
{
	int i = 0;//开辟了一个空间
	int j = 0;//开辟了一个空间
	int count;//开辟了一个空间
	for (i = 0; i < N; ++i)
	{
		for (j = 0; j < N; j++)
		{
			++count;
		}
	}
	for (i = 0; i < 5 * N; ++i)
	{
		++count;
	}
	for (j = 0; j < 10; ++j)
	{
		++count;
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	complex(n);
	return 0;
}

一共开辟了三处，那么complex的空间复杂度是O(1)

//计算Fib的空间复杂度
int Fib(int N)
{
	if(N < 3)
		return 1;
	return Fib(N-1) + Fib(N-2);
}

这段代码的空间复杂度为O(N),因为时间是一去不复返的，而空间是可以重复利用的

在这里插入图片描述

我们首先用最左边的一趟，从Fib（N）到1，然后一共创建了N个函数的空间，之后从1开始返回并且销毁函数的空间，然后0的地方又创建一个函数和1的相等，以此类推，这段代码的空间复杂度为O(N).