【数据结构】时间复杂度与空间复杂度-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】时间复杂度与空间复杂度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【数据结构】时间复杂度与空间复杂度

前言

在学习C语言的时候，大多数的小伙伴们并不会对算法的效率了解，也许算法也是一个陌生的领域，当进入了数据结构这个模块，就应该对算法的效率做一个清晰的认识。但是算法的效率是什么呢？这里就引出来时间复杂度与空间复杂度的概念了。

算法效率指的是算法解决问题所需的时间和空间资源。通常用时间复杂度和空间复杂度来衡量一个算法的效率。
对于初学者来说，这里看到复杂度会被认为是代码的的多少，但是这是错误的。

这里举个例子：(这里递归函数看着代码很少，但是这里的时间复杂度很大）

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

时间复杂度是算法在执行时所需的时间资源与问题规模之间的关系。通常以最坏情况下的运行时间为衡量标准，用大O符号来表示。

计算时间复杂度可以通过分析算法中基本操作的执行次数来完成，然后根据这些操作次数的增长趋势得出算法的时间复杂度。
计算时间复杂度的原则是：根据算法中基本操作重复执行的次数来估算算法的时间复杂度，忽略常数项和低阶项，保留最高阶项。

推导大O阶方法:
1、若执行次数都是常数，则用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，常数和低阶项全部去除，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

空间复杂度是算法在执行时所需的内存资源与问题规模之间的关系。同样以最坏情况下所需的额外空间为衡量标准，使用大O符号表示。

计算空间复杂度可以通过分析算法中使用的临时变量、数据结构等占用的空间大小来完成，然后根据这些空间大小的增长趋势得出算法的空间复杂度。
计算空间复杂度的原则是：根据算法中所需存储空间的大小来估算算法的空间复杂度，–忽略常数项和低阶项，保留最高阶项。

推导大O阶方法:
1、若运行时间都是常数，则用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，常数和低阶项全部去除，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

这是在电脑计算机中绘画出的图，或许有人觉得这些曲线会差不多，但是当我将这个图片缩小后就会发现区别了。
【数据结构】时间复杂度与空间复杂度

这里缩小后发现三个相对分区：（这里用时间复杂度表示）

无限接近于 y轴 ：二次方以上的幂函数( O (n ^ 2) )和大于一为底的指数函数
(O(n ^ k))，这里还包括一个阶乘(O(n!))（由于增长速度太快，电脑上绘画不出来,图片上就将其省略）。
x轴 与 y轴 之间：一次函数 (O(n)) 和线性对数 ( O(n * log(n)) ）
无线接近与 x轴：常数( O(1)) 和对数 ( O(log(n)))