基本概念和术语
讲到了数据结构是什么,我们就得先知道什么叫做数据。
数据
数据,《大话数据结构》这本书中,给出的定义:是描述客观事物的符号,是计算机中可以操作的对象,是能够被计算机识别,并输入给计算机处理的符号集合。
数据不仅仅包括整型,实型等数值类型,还包括字符及声音,图像,视频等非数值类型。
数据结构与数据库的区别
首先,我们先要区别开两个概念,这两个概念分别是什么呢?
分别是数据结构和数据库。这两个都是对数据进行管理,但他们的区别呢:数据结构是在内存中管理数据,而数据库呢是在磁盘中管理数据。
两个管理数据分别有着各自的好处:数据结构呢是速度快,但是需要带电存储。
而数据库呢是在磁盘中管理数据,相对于数据结构在内存中管理数据它的速度较慢,但是可以不带电存储。
算法
算法定义
什么是算法呢?
我们继续看《大话数据结构》这本书中,书中给中的解释是算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
我认为我们可以简单理解一下算法,其实就是解决问题的方法,在生活中,我们会遇到各种各样的问题,算法呢,可以说是我们解决问题的途径。
比如,在大学生活的我们,刚刚到月中,但是我们的生活费却没有了,这是我们现在所遇到的问题,针对于这个问题,我们就得想出我们的解决办法了。我们可以有好几种解决办法。
比如:
1.我们去向父母寻求支援。
2.我们可以向朋友请求支援。
3.我们可以去打工,做兼职,去挣取我们的生活费。
算法定义中,得到了指令,指令能被人或者机器等计算机装置执行。为了解决某个或者某类的问题,需要把指令表示成一定的操作序列,操作序列包括一组操作,每一个操作都能完成特定的功能。
在这个问题中,我们看到了三种解决方法,而这三种方法一步步可以当成指令,我们按照指令一步步运行起来,我们就可以得以解决我们所需要面对的文问题。
上述我们提出的三个问题进一步细分成我们一步步的步骤,然后我们完成操作,达成功能。这就是算法。
算法的特性
算法具有五个特性,分别是输入、输出,有穷性、确定性和可行性。
有穷性。一个算法必须总在执行有穷步之后结束,且每一步都可以在有穷时间内完成。
确定性。算法中每条指令必须有明确的含义。对于相同的输入只能得出相同的输出。
可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入。一个算法有零个或者多个输入,这些输入取自于某个特定的对象的集合。(这一条不是很准确的理解,自我感觉是对于输入数据的定义嘛?比如 int a = 0;这种对于a变量的类型的锁定,使其在int整型集合中吗?)
输出。一个算法有一个或者多个输出,这些输入取自于某个特定的对象的集合。
针对于解决问题的算法,应该考虑达到以下目标。
1.正确性。算法应该能够正确地解决求解的问题.
2.可读性。算法应该具有良好的可读性,让人们可以方便理解。
3.健壮性。输入非法数据时,算法能适当地做出反应或者进行处理。而不会产生莫名其妙的输出结果。
4.高效率性和低存储量需求。效率是指算法执行的时间,存储量需求是指算法执行过程中所需要的最大存储空间。这两者都与问题的规模有关。
在效率与存储空间的要求下,我们当然愿意选择效率高的和低存储空间的算法,可是我们又该怎么对这两个东西比较呢。所以我们引出了时间复杂度和空间复杂度的定义。
时间复杂度
时间复杂度的定义
在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。
一个算法执行所消耗的时间,从理论上来说是不能算出来的,只有你把你的程序放在机器上跑起来才能知道。但是我们如果每个算法都上机测试,这是很麻烦的一件事情。
所以才有了时间复杂度这个分析方式,它是一个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例。
算法中的基本操作的执行次数,为算法的时间复杂度。
即:找到某一条基本语句与问题规模N之间的数学表达式。就是算出了该算法的时间复杂度/。
我们从一个相对简单的例题引入我们的时间复杂度的计算。
从上面我们得知,我们需要某条基本语句与问题规模N之间的数学表达式,从上面这个例题,我们进行分析
,第一个循环语句进行N次,然后在它里面的循环语句,也进行了N次,所以外层循环加内层循环总共进行了N的平方次,然后再将下面的循环语句进行累加,和最下面的while循环循环次数10进行累加,我们得知F(N)=N*N+2N+10;
经过上述分析,我们就可以得出这个的时间复杂度是这个上面的表达式,但因为我们在计算时间复杂度时候通常是进行的大约计数,所以我们在进行时间的复杂度的计算时,通常采用:
大O的渐进表示法
推导大O阶的方法:
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。取决定性的那一项,即上方例子中的N*N这一项。
3.如果最高阶项存在且不是1,则去除掉与这个项目相乘的常数。得到的结果的就是大O阶。
最好,最坏,和平均。取最坏的O (N)
时间复杂度的计算估算是保守的估算
在实际中,我们一般关注的是算法的最坏运行情况。所以在这个情境下的时间复杂度我们是O(N)。
我们下面来关注一下这个例题,从中我们看出循环的次数是一个常数。我们将这个算法的时间复杂度记成O(1).它中间代表的1代表的意思不是一次,而是常数次。我们需要多加区分,因为在现在cpu运行条件下,常数次的运算情况并不会让我们在感觉上产生太大的感觉。
时间复杂度计算不能数代码中的循环,要根据思想,灵活计算。
我们将视角先看到这张图的左边,这个冒泡排序的时间复杂度是多少呢,是O(N*N),有的同学是怎么计算的呢,是数它的算法中有两层循环,两次循环就粗略的认为是O(N*N)了,这样的理解是错误的。
我们将视角投向到右边那个代码中,右边那个代码的时间复杂度是你想象中的那个样子嘛?
不对,它的时间复杂度是O(N)。
为什么会是这样呢,这是我们后续需要学习的一个排序方法,假设我们第一数是5,我们就将这个5设置成了一个keyi,然后右边给了一个right,左边给了一个left,如果我们右边的right大于keyii,我们就将right--,这是一个找小过程,而左边的left同样的道理,它是一个找大的过程然后。从代码中看,right和left走走走,最后会在途中的某个地方相遇,然后一边是比keyi大的,一边是比keyi小的数。
这样我们时间复杂度大家就可以说出来了吧,因为它总共才遍历了一遍这个数组,所以它的时间复杂度是O(N)。文章来源:https://www.toymoban.com/news/detail-763989.html
如果有什么错误,请大家多多指正,我也会在学习了新的知识后,对旧的知识进行更新与反思。希望大家多多支持。有错误也请麻烦大家多多指正。文章来源地址https://www.toymoban.com/news/detail-763989.html
到了这里,关于数据结构初阶的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!