• 【数据结构与算法】时间复杂度和空间复杂度


    🌠 作者:@阿亮joy.
    🎆专栏:《数据结构与算法要啸着学》
    🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根
    在这里插入图片描述

    活动地址:CSDN21天学习挑战赛

    算法

    1.算法的定义

    什么是算法呢?简单来说,算法就是解决问题的方法。如今普遍认为算法的定义是:

    算法是解决特定问题求解步骤的一种描述,在计算机中表现为指令的有限性,并且每条指令表示一个或多个操作。

    2.算法的特性

    输入输出

    输入和输出特性比较好理解。需要注意的是:一个算法可以具有零个或多个输入,但至少有一个或多个输出。 为什么一个算法可以没有输入,但必须要有输出呢?比如:我们需要在屏幕上打印"Hello World",像这样的代码就不需要任何的输入参数,因此算法的输入可以是零个。因为算法是解决问题的方法,你都把问题解决了,怎么会没有输出呢?所以算法至少有一个输出。输出的形式可以是:在屏幕上打印输出、返回一个值或者返回多个值。

    有穷性

    有穷性:**指算法执行有限的步骤之后,自动结束而不会出现死循环,并且每个步骤在有穷的时间内完成。**但是有穷并不意味着,你写一个算法,计算机需要运行上几十年才能结束。那你要这算法又有何用呢?

    确定性

    确定性: 算法的每个步骤都有确定的含义,不会出现二义性。 算法在任何条件下,只有唯一一条的执行路径,相同的输入只能有唯一的输出。

    可行性

    可行性:算法的每一步都必须是可以的,也就是说,每一步都能通过执行有限次数完成。 可行性意味着算法能在计算机上运行,并且得到正确的结果。

    3.算法设计的要求

    正确性

    正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。

    可读性

    可读性:算法设计的另一个目的是为了方便阅读、理解和交流。可读性高有助于别人了解你的算法,晦涩难懂的算法往往隐含错误,难以被发现,并且不方便调试和修改。

    健壮性

    健壮性:当输入的数据不合法时,算法能够对此进行处理,而不是输出异常的结果。一个好的算法应该能对输入数据不合法的情况做出合适的处理。比如输入的时间或身高为负数时,提示使用者输入大于0的数据等等。

    时间效率高和存储量低

    时间效率指的是算法的执行时间,而存储量需求指的是算法在执行过程中需要的最大存储空间,主要指算法运行时所占用的内存或外部硬盘的存储空间。在生活中,人们总想花最少的钱、用最短的时间,办成最大的事。算法也是一样,用最少的空间,花最少的时间,办到同样的事。所以,设计算法要精良满足时间效率高和存储量低的要求。

    算法效率

    1.如何衡量一个算法的好坏

    如何去衡量一个算法的好坏呢?比如对于以下求斐波那契数的函数:

    long long Fib(int n)
    {
    	if (n <= 2)
    		return 1;
    	else
    		return Fib(n - 1) + Fib(n - 1);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    斐波那契数列的递归实现方式非常简洁,但是简洁就一定好吗?那该如何衡量去好与坏呢?这就需要分析算法的时间复杂度和空间复杂度了。

    2.算法的复杂度

    算法在编写成可执行程序后,运行时需要消耗时间资源和夸奖资源。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间

    时间复杂度

    1.时间复杂度的定义

    在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法的时间复杂度不能取决于算法执行所耗费的时间。因为一个相同的算法放在不同的机器上测试,所耗费的时间就可能有很大的不同。一个算法所花费的时间与其中语句的执行次数成正比例,算法的基本操作的执行次数为算法的时间复杂度。

    那一个算法的时间复杂度怎么表示呢?算法的时间复杂度用O()来表示,我们称之为大O渐进表示法。接下来,我们来一起学习一下。

    2.大O渐进表示法

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

    3.时间复杂度分析

    平方阶O(N^2)

    代码示例:

    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++;
    		m--;
    	}
    
    	printf("%d\n", count);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    很明显,Func1函数执行的基本操作次数为F(N)=N^2+2*N+10。

    F(N)=N^2+2*N+10

    • N=10 F(N)=130
    • N=100 F(N)=10210
    • N=1000 F(N)=1002010

    从上面可以看出,N越大后两项对结果的影响越小的。根据大O渐进表示法,Func1函数的时间复杂度为O(N^2)。

    线性阶O(N)

    代码示例:

    void Func2(int N)
    {
    	int count = 0;
    	for (int i = 0; i < 2 * N; i++)
    	{
    		count++;
    	}
    
    	int M = 10;
    	while (M--)
    	{
    		count++;
    	}
    
    	printf("%d\n", count);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    很容易分析得出,Func2函数执行的基本操作次数为F(N)=2*N+10。那么根据大O渐进表示法,函数Func2的时间复杂度就是O(N)。

    代码示例:

    void Func3(int N,int M)
    {
    	int count = 0;
    	for (int i = 0; i < N; i++)
    	{
    		count++;
    	}
    
    	for (int i = 0; i < M; i++)
    	{
    		count++;
    	}
    
    	printf("%d\n", count);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    很明显,Func3函数的时间复杂度为O(M+N)。一般情况下,时间复杂度的未知数用的都是N,但是也可以用M、K等等字母。

    M远大于N,Func3函数的时间复杂度为O(M)
    N远大于M,Func3函数的时间复杂度为O(N)
    M和N差不多大,Func3函数的时间复杂度为O(M)或O(N)

    代码示例:

    long long Fac(int N)
    {
    	if (N <= 1)
    		return 1;
    	else
    		return Fac(N - 1) * N;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    这是一个递归算法,那么递归算法的时间复杂度怎么计算呢?其实递归算法的时间复杂度=递归次数×每次递归调用的次数。那么Fac阶乘函数的时间复杂度就是O(N)。在这里插入图片描述

    常数阶O(1)

    代码示例:

    void Func4()
    {
    	int count = 0;
    	for (int i = 0; i < 100; i++)
    	{
    		count++;
    	}
    
    	printf("%d\n", count++);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    很明显,Func3函数执行的基本操作次数为100。根据大O渐进表示法,Func3函数的时间复杂度就是O(1)。注意:O(1)表示代表算法只运行一次,而是运行了常数次。

    对数阶O(logN)

    代码示例:

    void Func5(int N)
    {
    	int count = 1;
    	while (count < N)
    	{
    		count *= 2;
    	}
    
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    假设循环x次后,count大于或等于N了,不满足循环条件。那么2^x = N,可以得到循环次数x = log2(N)。所以Func5函数的时间复杂度是O(logN)。注意:logN通常表示以2为底的对数。如果是以其他数字为底的对数,需要标注出来

    指数阶O(2^N)

    代码示例:

    long long Fib(int n)
    {
    	if (n <= 2)
    		return 1;
    	else
    		return Fib(n - 1) + Fib(n - 1);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    在算法效率的开头那里,我们提出了一个问题:斐波那契数列算法的效率如何?接下来,我们就来分析一下。因为递归算法的时间复杂度=递归次数×每次递归调用的次数,而该算法的每次递归调用的次数为O(1),所以我们只需要算出递归次数就行了。具体分析见下图:
    在这里插入图片描述
    指数阶的算法已经是时间复杂度非常大的算法了,是不会经常使用的。所以上面斐波那契数列的求解可以使用循环的方式来实现。

    4.常见的时间复杂度

    限于文章的篇幅,有一些时间复杂度还没有提及。在后续的文章,我们会进行讲解。

    5.最好、最坏和平均情况

    在上面,我们分析一些常见的时间复杂度。但是有时候,有一些算法会因为输入的不同,其时间复杂度也会不同。那么算法的时间复杂度就有了最好、最坏和平均三种情况了。

    最好情况:任意输入规模的最小运行次数(下界)
    平均情况:任意输入规模的期望运行次数
    最坏情况:任意输入规模的最大运行次数(上界)

    代码示例:

    const char* strchr(const char* str, int character)
    {
    	while (*str)
    	{
    		if (*str == character)
    			return str;
    		else
    			str++;
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    在这里插入图片描述
    从上图可以看出,随着输入的不同,查找的次数也不同。那这个算法的时间复杂度怎么算呢?注意:当一个算法随着输入的不同,时间复杂度也不同。那么时间复杂度就要做悲观预期,最坏情况的时间复杂度就是该算法的时间复杂度。所以strchr函数的时间复杂度为O(N)。 一般在没有特殊说明的情况下,时间复杂度都是值最坏时间复杂度。 最好情况和平均情况的时间复杂符不经常使用。

    空间复杂度

    1.空间复杂度的定义

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

    空间复杂度不是计算程序占用了多少个字节的空间,因为这个没有太大的意义,所以空间复杂度算的是变量的个数。空间复杂度的计算规则基本跟时间复杂度类似,也使用大O渐进表示法

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

    2.空间复杂度分析

    分析一下代码的空间复杂度:
    代码示例:

    //计算Fib的空间复杂度
    //返回斐波那契数列的前n项
    long long* Fib(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;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    在这里插入图片描述
    代码示例:

    long long Fac(int N)
    {
    	if (N <= 1)
    		return 1;
    	else
    		return Fac(N - 1) * N;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    在这里插入图片描述
    代码示例:

    long long Fib(int n)
    {
    	if (n <= 2)
    		return 1;
    	else
    		return Fib(n - 1) + Fib(n - 1);
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    在这里插入图片描述
    因为现在计算机的存储容量已经到了很高的程度,所以我们如今已经不需要再特别关注一个算法的空间复杂度了。因此,在大多时候,我们所写的算法会采取用时间换时间的方式。

    总结

    🧡 🧡 🧡在本篇博客里,主要向大家介绍了算法的定义、特性和设计要求,还重点分析了算法时间复杂度和空间复杂度。如果大家觉得有收获的话,可以点个三连支持一下! 谢谢大家啦!!!🧡 🧡 🧡

  • 相关阅读:
    电压放大器在超声领域中有哪些应用场景
    Windows 下使用bpg 图片 - 查看,转换,预览
    2023年数维杯国际大学生数学建模挑战赛
    AcWing 1282. 搜索关键词【AC自动机】
    SpringMVC使用(注解、获取各种参数的方式、视图模板、文件上传下载、国际化、RestFul)
    读高性能MySQL(第4版)笔记21_读后总结与感想兼导读
    Java对象的实例化过程是怎样的?
    logstash 编码转换
    轮播图的两种方法
    谈了这么久的无代码到底是什么?
  • 原文地址:https://blog.csdn.net/m0_63639164/article/details/126160356