算法+ 数据结构 = 程序
导读
1.1 为什么要学习数据结构与算法
很多人认为学习数据结构与算法只是为了应付面试，在日常的开发中基本上没有使用的机会，也有一些同学去刷题，但发现有时候这些题目一看就会一问就费的局面。甚至有一些的同学看到数据结构和算法这一词时内心直接就是抵触的。
这里很大的一部分原因是因为你没有真正的去了解数据结构，你有想过为什么大厂都要求数据结构与算法吗？为什么技术过关了但是总会挂在算法这一关？
学习数据结构与算法不仅仅是学习其中的数组，链表，队列，堆栈，树，图等经典的结构，也不仅仅是学习应付面试的算法。
其实数据结构是考验你的基本功是否扎实的重要环节之一，最重要的是你要学习一种思想：如何把现实问题转化为计算机语言的表示。
算法+ 数据结构 = 程序
本篇文章将介绍数据结构中的基础概念，了解基础概念之后会配套的做一些相关的练习题加深对其的理解。希望能对你得到一些帮助。
这个专题也会不断的向内添加内容，如有图片或者描述错误的地方或者讲解不清楚的地方还请各位同学及时指出，我加以改正。
目前已完成数据结构的基本概念 相关算法题会在编辑算法章节时陆续补充进来。感谢关注。
1.2 什么是数据结构与算法
[数据](https://baike.baidu.com/item/数据/5947370)结构是[计算机](https://baike.baidu.com/item/计算机/140338)存储、组织[数据](https://baike.baidu.com/item/数据)的方式。数据结构是指相互之间存在一种或多种特定关系的[数据元素](https://baike.baidu.com/item/数据元素/715313)的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储[效率](https://baike.baidu.com/item/效率/868847)。数据结构往往同高效的检索[算法](https://baike.baidu.com/item/算法/209025)和[索引](https://baike.baidu.com/item/索引/5716853)技术有关。
数据结构包括：
-
线性结构：线性表（数组、链表、队列、栈、哈希表）
-
树型结构：二叉树、AVL树、红黑树、B树、堆、Trie、哈夫曼树、并查集
-
图形结构：邻接矩阵、邻接表
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制
算法包括：递推法、递归法、穷举法、贪心算法、分治法、动态规划法、迭代法、分支界限法、回溯法
一. 算法基本概念
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
特征：
- 有穷性(Finiteness)：算法的有穷性是指算法必须能在执行有限个步骤之后终止。
- 确切性(Definiteness)： 算法的每一步骤必须有确切的定义。
- 输入项(Input):：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。
- 输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
- 可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。
1.1 时间复杂度
算法的时间复杂度是指执行算法所需要的计算工作量。也就是说程序需要执行的次数
大O表示法
一般用大O表示法来描述负责度，它表示的是数据规模为n对应的复杂度
-
忽略常数、系数、低阶
执行次数 复杂度 非正式术语 12 O(1) 常数阶 2n+3 O(n) 线性阶 4n^2+2n+6 O(n^2) 平方阶 4log2n+25 O(logn) 对数阶 3n+2nlog3n+15 O(nlogn) nlogn阶 4n3+3n2+n+12 O(n^3) 立方阶 2^n O(2^n) 指数阶
img
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
1.2 空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量)。
网友评论