本文探讨了学习数据结构与算法的重要性，指出它们是高效编程的基础，影响着程序性能。数据结构如B+树能优化数据库查询，算法如时间复杂度分析有助于优化程序。同时介绍了数据结构的逻辑和物理结构，以及算法的时间复杂度和空间复杂度概念，强调了线性结构和非线性结构在编程中的应用。
专栏地址：【大厂算法系列】
专栏内容： 数组，列表，栈，队列，树，哈希表，字符串，堆，查找，排序，DFS,BFS，回溯，贪心，动态规划等+力扣大厂真题
算法交流： V 【yopa66】
为什么要学习数据结构与算法，学完到底有没有用？
- 我们学习的很多东西，究根结底在底层都用到了很多的数据结构与算法。
- 这些东西经过层层封装。我们在使用的时候就可以不用去关注那些低层的东西了，而是直接调用实现好的即可。
- 学习数据结构与算法是非常有用的，它能帮助我们更有效地解决问题，提高程序的性能。数据结构与算法能够帮助我们更好地理解计算机系统的内部原理，提供编程思想，更好地分析和解决问题，从而提高编程能力。
举例说明：
- B+树结构 能够帮mysql高效的获取数据
- 数据库的索引数据结构： 二叉树 红黑树 Hash表 B-Tree 。这些索引数据结构可以增加数据的查找搜索效率
所以说，掌握数据结构与算法可以让你在计算机的路上走的更远，甚至可以说数据结构可以决定一个程序员的上限。
现在的互联网大厂往往对数据结构与算法有着较高的要求。扎实的数据结构算法基础往往是大厂的敲门砖。
关于数据结构与算法的概念你了解多少？
什么是数据结构
-
数据结构指的是相互之间有一种或者是多种特定的关系数据元素集合。
-
用大白话来说就是：计算机在对数据进行存储时候并不是杂乱没有顺序的，而是具有一定的规则。
-
数据结构可以分成逻辑结构跟物理结构
逻辑结构：抽象意义上的结构，按照对象中元素的关系分类
物理结构：又叫存储结构，主要有顺序存储跟链式存储
什么是算法
-
算法是被计算机使用来解决问题的方法，就对于程序而言，算法就是程序的灵魂，优秀的程序可以在面对大量数据计算时，依旧能够保持高速的计算。
-
对于小型的程序来说，就算这个算法差劲，解决的问题步骤比较繁琐，这样不会有很大的关系。但是如果对数据量大的程序（如何从海量数据千万级别的数据中快速找到自己想要的一条数据），我们就需要对时间和空间有要有效的利用，也就是设计一个高效的算法，在同样的硬件设备的情况下，有时候会把速度提高十倍甚至上百倍。
-
**用大白话来说就是：**在一定的条件下，对数据进行计算，经过不断的优化，选择是最适合的一种计算方式，以最快的方式得到需要的结果
-
程序 = 数据结构 + 算法
- 在计算机里来说，如果把单独的数据结构和算法拿出来讨论其实意义不大，就像鱼离不开水，算法也离不开数据结构。如果数据之间没有任何结构的话，算法也就无法实现了，毫无意义了。当然即使数据之间有关系，但是不对这些数据进行操作的话也没啥意义。
算法分析之时间复杂度
-
算法分析
- 前面也说过了，研究的算法的最终的目的就是怎么样花费更少的时间与内存来完成需求，不同的算法之间消耗的时间和空间会存在差异。
- 当你想要从千万级别的数据中找到一条自己需要的数据。
- 关于对算法时间耗费分析，我们称为时间复杂度分析。
-
对程序的执行时间的分析有两种方法
-
事后统计法
- 就是把程序运行起来，把所消耗的时间统计起来进行比较。这一些方法是可行的，但是会有一些问题：
- 第一，要对设计的算法性能来进行评测的话需要运行该程序。
- 第二，就是所得的时间统计会依赖硬件、软件等等环境因素导致的。这一种方式，需要在相同计算机下相同状态运行，这样才能够比较那个一个算法快
-
事前估算法
- 通过时间复杂度来判断哪一个算法优
-
-
时间频度 T(n)
- 一个算法所花费的时间跟算法里语句的执行次数是成正比例。
- 算法里的语句执行次数越多，说明所耗的时间就越多。
- 一个算法的语句执行的次数被称为时间频度T(n)。
//计算1-10000的和 public static void main(String[] args) { // 开始时间 //计算1-10000的和 int sum=0; for(int i=1;i<=10000;i++){ sum+=i; } System.out.println("1-10000的和为"+sum); int sum2; sum2=(1+10000)*10000/2; System.out.println("1-10000的和为"+sum2); }
- 使用for循环来进行计算，可以得出例1的时间频度是T(n)=n+1;n就为执行次数，1为最后面还需要判断一次
- 直接进行计算，这次是时间频度是T(n)=1；
- 当n的规模变大，也就是程序的时间频度变大了
- 注意：算法函数中的**常数项、低次项、系数可以忽略。**
- ```Java
T(n)=n+10
T(n)=n
可以省略常数10
T(n)=n^2+2n+10
T(n)=n^2
可以忽略低次项和常数项
大O计数法来表示算法时间复杂度的效率
对于算法的时间复杂度的效率分析，我们可以使用**“大O计数法”**来表示
-
大O计数法
- 算法的时间复杂度通常用大O符号来表示表述，定义的形式为T[n] = O(f(n))，称T(n)受限于f(n)。
- 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，T(n)是关于问题规模n的函数
- T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时，时间复杂度的极限情形称为算法的“渐近时间复杂度”。
-
常见的时间复杂度 - 使用大O阶表示
- 常数阶O(1)
public static void main(String[] args) { int a= 0; ++a; int c =a+1; }这个代码不管是执行了多少行，只要没有循环等这种复杂的结构，那时间复杂度就是O(1)
- 线性阶O(n)
public static void main(String[] args) { int sum= 0; for(int i =1;i<=100;i++){ sum+=i; } }这段代码for循环里面的代码会执行n次，因为随着n的变化所消耗的时间也随之变化，这类的代码都可以使用O(n)来表示
- 平方阶O(n²)
public static void main(String[] args) { int sum= 0; int n=10; for(int j = 1;j<=n;j++){ for(int i =1;i<n;i++){ sum+=i; } } System.out.println(sum); }这段代码n是10，外层会循环执行10次，内层会循环指向10次，总共指向10*10=100次，也就是n的平方次，使用O(n2)来表示。同理，如果使用了三层循环那么时间复杂度就是O(n3)立方阶
- 对数阶O(Logn)
public static void main(String[] args) { int i=1 int sum=100 while(i<sum){ i=i*2 } }这里的while循环，每经过一轮，也就是每经过一次i*2的运算，结果就会里sum的值越近 2^x=n，时间复杂度就是O(Logn)
- 常见的算法时间复杂度由小到大排序
-
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(nk)<O(2n)，可以看出随着规模n的不断变大，执行的效率就越低。
-
平均时间复杂度与最坏时间复杂度
- 平均时间复杂度说的是任何的算法时间复杂度都是O(n²)
- 最坏情况时间复杂度每次都是查到到最后一个才是期望数字O(n²)
- 时间复杂度大小比较 O(1)<O(logN)<O(nlogN)<O(n^2)
空间复杂度
-
空间复杂度类似于时间复杂度，一个算法的空间复杂度定义是该算法所消耗的存储空间。
-
空间复杂度主要是对一个算法在运行时占用存储空间的量度。在做算法分析时，主要是讨论时间复杂度，因为从用户使用来看，更看重的是程序的速度。
-
一般做java开发的，基本都是服务器开发，一般不存在这样的问题
线性结构与非线性结构
- 什么是线性结构
- 线性结构是最常用的数据结构，它的特点是数据元素之间是一对一的关系，如数组a[0]=1，那么数组下标为0的时候就等于了1，这就是一对一的关系。
- 线性结构的储存结构有两种，一个是顺序存储结构（以数组方式），一种是链式存储结构（链表）。顺序存储结构的线性表又被称作为顺序表，顺序表里存储的元素是连续的，分配的地址也是连续的。
- 链式存储的线性表又被称为链表，链表里存储的元素不一样是连续的，一般所储存的数据作为一个节点，每个节点分配一个指针来找到下一个节点的位置获取相关信息。
- 线性结构常见的有：数组、队列、栈、链表 后面的章节会逐一带大家手写这些数据结构。
- 什么是非线性结构
- 非线性结构里的各个数据元素不保持在一个线性的序列当中，每一个数据元素都可能会与0个或者是多个其他的数据元素发生联系的。
- 常见的非线性结构有：二维（多维）数组，广义表，树结构，图结构
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
