C/C++【数据结构】一文秒懂时间复杂度和空间复杂度！-Toy模板网

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

个人主页：仍有未知等待探索_C语言疑难,数据结构,小项目-CSDN博客

专题分栏：数据结构_仍有未知等待探索的博客-CSDN博客

一、前言

1、什么是数据结构

2、什么是算法

3、为什么要考虑时间复杂度和空间复杂度

二、时间复杂度和空间复杂度

1、算法效率

1.如何评判一个算法的好坏？

2.算法的复杂度

2、时间复杂度

1、什么是时间复杂度

2、大O的渐进表示法

3、空间复杂度

三、常见的复杂度的大小

四、练习题

一、前言

1、什么是数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

2、什么是算法

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

3、为什么要考虑时间复杂度和空间复杂度

学数据结构的第一节课就是讲的时间复杂度和空间复杂度。为什么呢？感觉这个用处不大啊。但是时间复杂度和空间复杂度的重要性和感觉恰恰相反，这个非常的重要。

如果评判一个算法的好坏呢？

通过时间复杂度，时间复杂度越小，算法越优。当然也要结合着空间复杂度看。

二、时间复杂度和空间复杂度

数据结构为什么看重时间复杂度？

首先数据结构是计算机存储数据的方式。如果数据比较少的时候，也就谈不上要将数据怎么存，反正空间有的是。但是现实中数据可是很庞大的，如果没有一种存储数据的规则的话，要查找一个数据所需要的时间太长，计算机发明的初衷就是为了缩短和简便计算，如果计算时间过长的话就违背初衷了。

如果数据少的话，也就谈不上什么数据的存储，也就说不上什么数据结构了。

C/C++【数据结构】一文秒懂时间复杂度和空间复杂度！,数据结构,数据结构,c语言

1、算法效率

1.如何评判一个算法的好坏？

代码简洁就可以评判出一个算法的好坏吗？显然不是。

可以举出反例的，如果用递归写的计算斐波那契数，代码量确实很小，但是它效率高吗？

通过下面计算第3个斐波那契数和计算第40个斐波那契数的时间就可以比较出来，代码量小不一定代表高效。
#define _CRT_SECURE_NO_WARNINGS  1
#include<stdio.h>
#include<time.h>
//代码量确实很小，但是它效率高吗？
int Fib(int n)
{
	if (n < 3)
		return 1;
	return Fib(n - 1) + Fib(n - 2);
}
int main()
{
	double start1 = clock();
	printf("Fib(3)=%d：", Fib(3));
	double end1 = clock();
	printf("%lf毫秒\n", end1 - start1);
	double start2 = clock();
	printf("Fib(40)=%d：", Fib(40));
	double end2 = clock();
	printf("%lf毫秒\n", end2 - start2);
	return 0;
}

2.算法的复杂度

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

2、时间复杂度

1、什么是时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行

所耗费的时间，但是这个是不可以计算出来的，只有在机器上跑出来才知道。（每个机器可能因为

CPU等硬件的不同，跑出来的时间也不一定相同）

所以，规定：算法中的基本操作的执行次数，为算法的时间复杂度。即找到某条基本语句与问题规

模之间的数学表达式，就是算出了该算法的时间复杂度了。

2、大O的渐进表示法

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

有的算法有最好的运行时间，也有最坏的运行时间。但是实际情况中，一般考虑最坏的运行时间。

3、空间复杂度

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

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

的个数。

空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定

好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

三、常见的复杂度的大小

从上到下依次变慢

快	O(1)
	O(logn)
	O(n)
	O(nlogn)
慢	O(n^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)
}
代码中有两个循环，一个循环了2*N次，另一个循环了10次。

故，时间复杂度为O(2*n+10)，根据大O的渐进法，得O(n)。