导图社区 数据结构和算法总览
算法和数据结构整体的一个思维导图
该导图为 iOS 下内存管理相关的原理和问题。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
数据结构和算法总览
数据结构
data structure 是数据的组织、管理和存储个数，其使用目的是为了高效地访问和修改数据
线性结构
包括数组、链表，以及由它衍生出来的栈、队列、哈希表
树
比较有代表性的是二叉树，由它又衍生出了二叉树之类的数据结构
图
其他数据结构
由基本数据结构变形而来，用于解决某些特定问题
跳表、哈希链表、位图等
算法
在计算机领域，算法是一系列程序指令，用于处理特定的运算和逻辑问题
算法优劣的评判
时间复杂度
时间复杂度的比较
空间复杂度
常见空间复杂度
常量空间
O(1)
线性空间
O(n)
二维空间
O(n^2)
递归空间
递归是一个比较特殊的场景。 虽然递归代码中并没有显示地声明变量或集合，但是计算机 在执行程序时，会专门分配一块内存，用来存储“方法调用”。
“方法调用栈” 包括进栈和出栈两个行为
执行递归操作所需要的内存空间和递归的深度成正比
纯粹的递归操作的空间复杂度也是线性的，如果递归 的深度是 n，那么空间复杂度就是 O(n)
渐进表示法
如果是常数量级，用常数 1 表示
只保留函数中的最高阶项
如果最高阶项存在，则省去最高阶项前面的系数
例如
时间与空间的取舍
在绝大多数时候，时间复杂度更为重要一些，我们宁可多分配一些内存空间，也要提升程序的执行速度。
算法设计的经典思想
贪婪算法
理解
类似于日常生活中的找零，每次选出最大面值的，并且和已选出的纸币金额加起来不超过应付金额的纸币找给对方。这种方法就叫作贪婪算法。
解决问题的特征
该问题至少有一个最优的解决方案。 只有这样，才可能为解决问题构造候选方案集合。
随着问题的求解，将建立另外两个集合，一个集合（假设为集合 a ），由已经被选出并符合问题要求的候选解组成，另一个集合（假设为集合 b ）由已经被选出但并不符合问题要求的候选解组成。
集合 a 最终要包含问题的解答。在集合 a 中未出现解答时，问题的候选解集合中至少还要剩余一个候选解。
可解决的经典问题
图的最小生成树问题（克鲁斯卡尔算法及普里姆算法）
图的最短路径问题（狄克斯特拉算法）
最小任化务执行的平均时间问题
背包问题
分治法
在计算乘法时并不是用两个数直接相乘，而是把其中的一个乘数进行 “分解”，这种分解求解的方法叫作分治法。
是一种自顶向下的算法
把问题划分成一个一个的子问题，通过对子问题的求解实现对原问题的求解
整个问题可以分解为两个或多个较小的子问题
对每个子问题的求解，类似于对整个问题的求解
如果子问题的规模仍相当大而不便于对子问题的求解，那么再对子问题运用分治法
传染病问题
二分搜索及快速排序
矩阵乘法
汉诺塔问题
动态规划
思想方法
避免对同样的问题进行二次求解
是一种自底向上的设计方法
算法要解决大量重复的工作，计算大量重复的数据
至少有一些新的数值可以通过已经计算出的数值组合出来
问题要具有一定的规模，这样动态规划算法的好处才可以凸显出来
使用分治法划分子问题时，子问题之间的关系界限不清，相互交叉。一个子问题的求解与多个已经解决的子问题有关
快速傅里叶问题
多边形的最优分割
找零钱问题
最短路径问题
链式矩阵乘法
回溯法
是一种优化的穷举法
问题可以划分为几个不相关的子问题
几个子问题有类似的求解方式
如果子问题还可以划分，边继续对子问题进行划分
迷宫问题
八皇后问题
骑士周游问题
图的深度优先遍历
概率算法
实质
是算法对于同样的输入产生不同的结果
蒲丰投针问题
验证矩阵乘法
素数性测验
大整数分解因式
