#####废话的开始#####,从今天开始,可能就会多一个话题了,虽然以前在学校也学过数据结构这门课程,但是作为新世纪的90后,还是把学到的东西原原本本还给了老师,有借有还再借不难。其实后续也陆陆续续学习过,但是没有去做很好总结,容易忘记,毕竟作为一个半路出家的码农来说,这个需要好好学习,主要是没怎么写代码,所以基本没用到这些,就算写了代码,好像也用的不多,除非是从事底层开发的小伙伴,不过学会了这个数据结构和算法还是有有很多好处的,具体怎样,请继续往下看。
为什么要写一个数据结构和算法的相关的介绍呢?学这个前至少也要知道自己为什么要学这个东西吧,学好了可以干嘛,可以怎么去学习。此文只是为了更好的从全局去了解数据结构和算法,为后期的学习做一个认知,做一个全局的认知后,对后期的学习会更好,会更加的系统,更加的巩固,对于数据结构和算法的介绍所以也是很重要的,因为我们每做一件事情之前都要知道做这件事的目的,能够带来什么好处,怎么去做,用什么方式做的更好更有效率。不说别的吧,就说对于面试就很有用,看java的源码也有用,越是接触到底层的代码,就越能体现数据结构和算法的重要性。如果你只是满足于调用封装好的代码,那就到此为止,没必要往下看,如果想好好的了解数据结构和算法,就认真的往下看,什么是数据结构和算法,有什么用,有什么魅力。
其实只要作为一个码代码的程序员来说,写程序的都需要学这个,毕竟:程序 = 数据结构 + 算法 + 程序设计语言
数据结构和算法是程序的灵魂啊,失去灵魂的程序肯定是没精神气的(臃肿,速度慢,消耗资源多)
装逼!强行装逼!!强行一起吹水!!!这点很重要,其实下面的才是重点:
总之,很重要!很重要!!真的很重要!!!
数据结构就是把数据组织起来,为了更方便地使用数据我们为了解决问题,需要将数据保存下来,然后根据数据的存储方式来设计算法实现进行处理,那么数据的存储方式不同就会导致需要不同的算法进行处理。我们希望算法解决问题的效率越快越好,于是我们就需要考虑数据究竟如何保存的问题,这就是数据结构。
数据结构可分为:线性结构和非线性结构。
线性结构:
非线性结构:
非线性结构包括:二维数组,多维数组,广义表,树结构,图结构
非线性结构可以继续分:集合、树形结构、图状结构
存储结构表示数据在计算机中的表现形式:
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。----算法百度百科
算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。算法是独立存在的一种解决问题的方法和思想。
其实算法就是解决问题的一种方法或者是思路,所以每个算法都有自己的应用场景,所以很多情况要根据实际情况选择合适的算法或者是设计算法。所以明白算法的原理,至少能够让你在面对不同的场景的时候能够正确的选择哪一种算法,提高效率,节约资源,这都是时间和白花花的银子啊,所以好好学习算法很重要。
算法的五大特性:
时间复杂度:
算法的时间复杂度是指执行算法所需要的计算工作量。一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做。T(n)=Ο(f(n)),因此,问题的规模n 越大,算法执行的时间的增长率与f(n) 的增长率正相关,称作渐进时间复杂度(Asymptotic Time Complexity)。
常见的时间复杂度:
执行次数函数举例 | 阶 | 非正式术语 |
12 | O(1) | 常数阶 |
2n+3 | O(n) | 线性阶 |
3n^2+2n+1 | O(n^2) | 平方阶 |
5log2n+20 | O(logn) | 对数阶 |
2n+3nlog2n+19 | O(nlogn) | nlogn阶 |
6n^3+2n^2+3n+4 | O(n^3) | 立方阶 |
2^n | O(2^n) | 指数阶 |
常见时间复杂度之间的关系,所消耗的时间从小到达:O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
空间复杂度:
算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多.
算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。记为S(n)=O(f(n))
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地\"进行的,是节省存储的算法,有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元。
当然评价算法的好坏不仅仅是算法的时间复杂度和空间复杂度,比如还有正确性,可读性,键值性等,明白了时间复杂度和空间复杂度,就知道什么情况下什么场景可以考虑时间换空间,或者空间换时间了,这些都是根据实际情况而定的,没有最好的算法,只有更适合的某些场景的算法。
算法中常用的分析方法:递推法、递归法、穷举法、贪心算法、分治法、动态规划法、迭代法、分支界限法、回溯法。
算法的分类:
算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法,厄米变形模型,随机森林算法。算法可以宏泛的分为三类:
比如常见的一些数据结构和算法:
数据结构和算法知识结构思维导图(引用优秀博文,见参考文章):
参考:
https://www.cnblogs.com/54chensongxia/p/11448695.html
https://www.cnblogs.com/chjxbt/p/10967968.html
https://baike.baidu.com/item/%E7%AE%97%E6%B3%95/209025
https://www.cnblogs.com/songQQ/archive/2009/10/20/1587122.html