数算部分-----第一节----算法的时空复杂度

简介: 数据结构,Data Structure, 指的就是计算机存储、组织数据的一种方式。并且可以理解为,这些数据的元素间有着特定关系。而这些数据包含其特定关系的集合,就叫数据结构。

数算部分-----第一节----算法的时空复杂度


目录


数据结构前言:


——算法的时空复杂度


算法效率


算法的特性


算法的时间复杂度


算法的空间复杂度


数据结构前言:

学习数据结构之前,需要问一问自己,何为数据结构?


实际上,数据结构,Data Structure, 指的就是计算机存储、组织数据的一种方式。并且可以理解为,这些数据的元素间有着特定关系。而这些数据包含其特定关系的集合,就叫数据结构。


那算法呢?我们在学习数据结构的时候,总能听到:数据结构与算法这样的说法。


即意为数据结构于算法不分家。


那么算法(Algorithm)简单来说就是经过一系列的计算步骤,达到输入与预期输出之间的关系。


那么数据结构有多重要?我们不从学校考试、绩点等方面来分析,这样显得格局太小且没有意义。我们从个人的工作中来说,数据结构在校招、笔面试是必考的环节,它体现着一个人的算法功底以及发展潜力。在日后的工作中,不会用数据结构,那....只能说...可能比较惨。(不排除个例,如果你不信的话你可以去吃个螃蟹哈~~~)(可以参见《大话数据结构》中作者举的例子)


所以说,数据结构与算法是一门极其极其重要的课程!!!


好,我们正式进入第一章的学习


——算法的时空复杂度

对于很多学校和老师来说,这一节是直接不讲的。


但我想说,这一节,正是算法的核心。


甚至于比我们后面所有学的数据结构以及算法的知识都要重要。


它对于我们代码的优化、代码的规范和简化、代码的书写习惯都提升了一个更高的要求。


它往往体现在一些看似“微不足道”的地方。


但是,当一个项目有几万行、几百万行代码的时候,就会被无限放大。


可以想象,


一种算法for循环套着for循环又套装for循环,另外的一种几句话搞定。


一种算法是要2^n次,而另外一种算法只要处理logn次(注:我们本章所有的log均指以2为底),当n趋向于无穷时,二者所需的时间可谓千差万别。


我们本章暂时先不探讨代码风格,就只谈算法的优化和简化。


我们先来说说什么叫算法的复杂度。


算法的复杂度包含算法的时间复杂度和算法的空间复杂度。我们将分别详细地探讨这两个概念。


先打个预防针,这一节其实概念性的东西比较多,实操性比较弱,但我们从下一节顺序表开始,将会在教大家思路的同时,教会大家代码的实现。


我们目前的数据结构用的是C语言来实现。


算法效率

算法效率分析分为两种:第一种是时间效率,第二种是空间效率。


时间效率被称为时间复杂度,而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度。


空间复杂度主要衡量一个算法所需要的额外空间。


在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。


但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。


所以我们如今已经不需要再特别关注一个算法的空间复杂度。


算法的特性

这里我们简单提一下:


1.输入:在算法中可以有零个或者多个输入


2.输出:在算法中至少有一个或者多个输出


3.有穷性:在执行有限的步骤之后,自动结束不会出现无限循环并且每一个步骤在可接受的时间内完成


4.确定性:算法的每一个步骤都具有确定的含义,不会出现二义性


5.可行性:算法的每一步都必须是可行的,也就是说,每一步都能够通过执行有限的次数完成


算法的时间复杂度

在理解这个概念之前,我们需要知道,什么叫做好的算法?


我们还记得计算斐波那契数列的时候所用的算法么?


我们当时是怎么做的?


大概率,我们是用下面的代码实现的:


代码运行起来之后,当我们输入10,20,30等小数字的时候,答案确实会一下子就出来了。


但是,当我们输入50的时候,它迟迟不出结果(下图视频以三倍速播放):


有兴趣的小伙伴可以试一下,应该是要十几分钟就能出来了😀



(这个图gif太不清楚了~~~~555)


为什么会这样?原因在于它的算法的效率,真的是太太太太太低了,算法的时间复杂度巨高。学完本章,你就能更深层次地理解这其中的原因了。


接下来,我们就要来了解一下,什么叫做算法的时间复杂度或者说时间效率?

image.png



(图)


(源自百度百科)


从字面意思去理解的话,实际上就是计算算法的运算效率的函数,它也就是这个意思。


说是时间复杂度,但是我们不可能去真的计算每个程序每一次运行的时间。


因为每一次运行的时间不仅仅与你设计的代码有关,还与你的电脑的性能、电脑当前的CPU运行的速度等等都有关系。所以,计算每一次运行的时间,意义就不大了。


那我们算什么?


实际上,我们比较的,可以认为是算法过程中的大头,主要矛盾。


我们用大O渐进表示法来表示。


至于大O渐进法到底是什么?


我们回到概念上去,我们刚刚说算法的时间复杂度是计算算法的运算效率的函数。


假设,我们用f(n)来表示一个程序要执行的语句次数,n可以先理解为函数f的规模。那么我们将会得到f(n)关于规模n的一个函数。


我们不要光干讲概念,来举个例子吧:


在数学中,我们如果有这么一个表达式:


F(n)=n*n + n + 5。


当n取100时,n*n为10000,而后面的只有105,105相较于10000而言,非常的小,如果n再大,那么n*n的值比n+5大的更多。n+5会相较于n*n而言会更小。小到可以忽略不计。那么n如果还要再大,后面的n+5就会更更小……


所以决定F(n)的阶数的是前面的n*n,后面的n+5在n很大的时候,相较于n*n,对于结果的影响便会微不足道。


我们对于这样的F(n),取能主要影响结果的那一项,即n^2(n*n),那么用大O进阶表示法的话就是O(n^2)。


同样的道理,我们可以再举一个例子:


F(n) = 1/2*n + 5; 这里影响最终结果的一项(或者可以直接理解为次数最高的一项)为1/2*n,然后将前面的系数变成1(因为我们只抓”主要矛盾、关键部分“),最终,得到的大O阶为O(n)。


那如果F(n) = 5呢?对于常数函数,我们就用O(1)来表示。


那么我们总结一下:


大O符号(Big O notation):


是用于描述函数渐进行为的数学符号。


推导大O阶方法:


1、用常数1取代运行时间中的所有加法常数。


2、在修改后的运行次数函数中,只保留最高阶项。


3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。


好。我们再用具体的代码来举例。


请看:(例1:)



我如果调用这么一个函数,请问它的时间复杂度是多少?(用大O表示)


首先,应当将其表达式写出来。


它的表达式可以表示为:f(n) = 1+n*n+n+2n。整理一下,得:f(n)=n^2+3n+1。


所以,得到它的时间复杂度为O(N^2)。


我们再来看几个例子:

(例二:)

请问,这个函数的时间复杂度是多少?


同样的道理,我们还是先写出表达式:f(n,m)=n+m+1;1相对于m和n对表达式的影响很小,所以可以忽略不计。而由于我们并不知道m与n之间的关系,所以我们应当予以保留。即该函数的时间复杂度为O(m+n)


例三:

我们再来看一个例子:



请问这个算法的时间复杂度是多少?


还是先算表达式:f(n)=1+100+1=102;    常数阶,所以为O(1);

例四:(作用是在一个字符串中找到我们想要的元素)


假如我们传入的str为一个字符串,字符串的长度为n,那么请问该函数的时间复杂度为多少?


其实,这样的情况分为很多种,换句话说,看运气。


如果运气好,我们一次就能找到。


如果运气不好,要遍历完才能判断能否找到,就是说要到第n个才能找到(或找不到)。


还可以是平均的情况,就是n/2次。


那么我们算这个函数的复杂度应该怎么弄呢?实际上,我们在算复杂度的时候,是按照最坏的情况算的。最坏情况运行时间是一种保证,那就是运行时间将不会再坏了,在应用中也是一种需求。这是一种确定的情况。所以我们在一般没有特殊说明的情况下,都是按照最坏的情况来算。


所以,上述的算法的时间复杂度为O(n)


例五:


微信图片_20221208152626.png


请问该冒泡排序算法的时间复杂度是多少?


我们还是把表达式写出来:


f(n)=(n-1)+(n-2)+(n-3)+(n-4)+...+1=n*(n-1)/2


所以,它的算法的时间复杂度应当是O(n^2)


例六:

微信图片_20221208152654.png



该二分查找的算法的时间复杂度是多少?


同样,还要分最好和最坏的情况来讨论:


最好的情况:一次就找到,那就是O(1);


最坏的情况:最后一次才找到。假设找了x次,有n个元素,则n/2/2/2/2.../2=1,那么/2这个运算进行了x次。所以n = 2^x,所以x = logn。


因此,该二分查找的算法的复杂度为(logn)


例七:



请问该算法的复杂度为多少?


对于递归的算法复杂度,它等于    递归次数*每次递归函数中的次数


那么对于这个例子,它递归了多少次?


Fac(N)->Fac(N-1)->Fac(N-2)->Fac(N-3)->Fac(N-4).....->Fac(1)    递归了n次。


故f(n) = 1*n


所以算法复杂度为O(n)


例八:

我们回到当初的那个例子,来看看它的算法复杂度是多少。

image.png


实际上,它的次数是一个完全二叉树的形式(我们后面会讲)。那么它要算的次数就是完全二叉树的节点的个数。所以它要运算的次数为f(n) = 2^(n-1) - 1 -X(X为完全二叉树与同等深度的满二叉树的节点的个数之差,一个常数),这个我们后面也会讲。


所以,它的时间复杂度为O(2^n)。


所以,我们刚刚在算50的斐波那契数列时,可想而知,得到的数字将会是一个天文数字~~~~~


关于算法的时间复杂度,我们就先说到这里。


下面,我们再来说说算法的空间复杂度


算法的空间复杂度

类比于时间复杂度,对于算法的空间复杂度,我们也不会去计算每个算法都开辟了多少字节的空间。因为这个也没太大意义,所以空间复杂度算的是变量的个数。


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


我们还是通过举几个例子来说明:


例一:

微信图片_20221208152925.png



还是来看刚刚的冒泡排序:


请问,它的空间复杂度是多少?


实际上,它创建的变量就一个exchange,就是说,它的变量的数量是一个常数阶。


所以,它的空间复杂度为O(1)


例二:


来看这么个斐波那契数列的算法。


我们可以看出,我们用malloc创建了n+1个变量。


所以,它的空间复杂度为O(n)

例三:

来看这个阶乘。


它递归调用了n次。


我们在C语言的函数部分介绍过,函数的每一次递归调用都会为新的函数重新开辟一个栈帧,上一级的函数由于并未结束,所以上一级的函数的栈帧并未被销毁。所以在调用下一级的函数的时候,就不得不在新的位置重新为其开辟栈帧。


所以,它的空间可以理解为开辟了n次。


所以,它的空间复杂度为O(n)。


关于算法的时空复杂度,对于优化代码算法是十分重要的,不过理解起来并没有那么困难。希望读者在理解上述的例题及概念后,可以去牛客网和Leetcode上找一些相应的oj题来练一练。


好啦,有关算法的时空复杂度,我们就探讨到这里啦。



目录
相关文章
|
2月前
|
机器学习/深度学习 存储 算法
1 .算法的复杂度(超全)
1 .算法的复杂度(超全)
|
1天前
|
算法
【初阶数据结构】复杂度算法题篇
该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 kmodn 个元素会移动至数组头部,其余元素向后移动 kmodn 个位置。
|
28天前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
【7月更文挑战第23天】在Python编程中,掌握算法复杂度—时间与空间消耗,是提升程序效能的关键。算法如冒泡排序($O(n^2)$时间/$O(1)$空间),或使用Python内置函数找最大值($O(n)$时间),需精确诊断与优化。数据结构如哈希表可将查找从$O(n)$降至$O(1)$。运用`timeit`模块评估性能,深入理解数据结构和算法,使Python代码更高效。持续实践与学习,精通复杂度管理。
37 9
|
1月前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
38 1
【数据结构】算法的复杂度
|
3月前
|
存储 算法 C语言
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)(上)
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)
48 2
|
2月前
|
算法 搜索推荐
数据结构和算法——表排序(算法概述、物理排序、复杂度分析,包含详细清晰图示过程)
数据结构和算法——表排序(算法概述、物理排序、复杂度分析,包含详细清晰图示过程)
22 0
|
2月前
|
存储 机器学习/深度学习 算法
数据结构和算法学习记录——空间复杂度的计算(冒泡排序、阶乘递归、斐波那契数列递归、常见复杂度对比、栈帧、栈溢出)
数据结构和算法学习记录——空间复杂度的计算(冒泡排序、阶乘递归、斐波那契数列递归、常见复杂度对比、栈帧、栈溢出)
20 0
|
3月前
|
存储 算法
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)(下)
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)
28 0
|
3月前
|
机器学习/深度学习 存储 算法
数据结构与算法①(第一章复杂度知识点)(大O渐进表示法)(下)
数据结构与算法①(第一章复杂度知识点)(大O渐进表示法)
24 0