第八周总结
数据结构
时间复杂度
并不是计算程序具体运行的时间，而是算法执行语句的次数。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度
空间复杂度
一个算法在运行过程中临时占用存储空间大小的量度
O(n)表示需要临时存储n个数据
数组
创建数组必须要内存中一块连续的空间。
数组中必须存放相同的数据类型。
随机快速读写是数组的一个重要特性，根据数组的下标访问数据，时间复杂度为O(1)。
删除数组元素和插入数组元素的时间复杂度为O(n)
链表
链表可以使用零散的内存空间存储数据。 所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。
要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是O(N)
删除链表元素和插入链表元素的时间复杂度为O(1)
hash表
根据key值计算hashCode
通过hash函数计算整个key-value对象在hash表中的地址
根据地址取到key-value对象
栈
栈就是在线性表的基础上加了这样的操作限制条件：后面添加的数据，在删除的时候必须先删除，即通常所说的“后进先出”。
队列
队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。
二叉树
二叉排序树：左子树上所有结点的值均小于或等于它的根结点的值。 右子树上所有结点的值均大于或等于它的根结点的值。 左、右子树也分别为二叉排序树
平衡二叉树：从任何一个节点出发，左右子树深度之差的绝对值不超过1。 左右子树仍然为平衡二叉树
红黑树：非严格平衡二叉树
每个节点只有两种颜色：红色和黑色。 根节点是黑色的。
每个叶子节点（NIL）都是黑色的空节点。
从根节点到叶子节点，不会出现两个连续的红色节点。
从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。
红黑树VS平衡二叉树
红黑树多只需3次旋转就会重新达成红黑平衡，时间复杂度O(1)。
在大量增删的情况下，红黑树的效率更高。
红黑树的平衡性不如平衡二叉树，查找效率要差一些。
跳表
跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。
算法
穷举算法
穷举法又称穷举搜索法，是一种在问题域的解空间中对所有可能的解穷举搜索，并根据条件选择最优解的方法的总称。数学上也把穷举法称为枚举法，就是在一个由有限个元素构成的集合中，把所有元素一一枚举研究的方法。
使用穷举法解决问题，基本上就是以下两个步骤：
• 确定问题的解（或状态）的定义、解空间的范围以及正确解的判定条件；
• 根据解空间的特点来选择搜索策略，逐个检验解空间中的候选解是否正确；
递归算法
递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。特别地，在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这也正是递归的定义所在。格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况
数学归纳法适用于将解决的原问题转化为解决它的子问题，而它的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。
归纳法主要包含以下三个关键要素：
步进表达式：问题蜕变成子问题的表达式
结束条件：什么时候可以不再使用步进表达式
直接求解表达式：在结束条件下能够直接计算返回值的表达式
事实上，这也正是某些数学中的数列问题在利用编程的方式去解决时可以使用递归的原因，比如著名的斐波那契数列问题
递归三要素
1). 明确递归终止条件
递归就是有去有回，既然这样，那么必然应该有一个明确的临界点，程序一旦到达了这个临界点，就不用继续往下递去而是开始实实在在的归来。换句话说，该临界点就是一种简单情境，可以防止无限递归。
2). 给出递归终止时的处理办法
在递归的临界点存在一种简单情境，在这种简单情境下，我们应该直接给出问题的解决方案。一般地，在这种情境下，问题的解决方案是直观的、容易的。
3). 提取重复的逻辑，缩小问题规模*
递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。从程序实现的角度而言，我们需要抽象出一个干净利落的重复的逻辑，以便使用相同的方式解决子问题。
贪心算法
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。
贪心算法的思路
建立数学模型来描述问题
把求解的问题分成若干个子问题
对每个子问题求解，得到子问题的局部最优解
把子问题的解局部最优解合成原来问题的一个解
动态规划算法
1.最优子结构
最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2.无后效性
无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
3.子问题重叠
子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率
还未添加个人签名 2019.05.09 加入
还未添加个人简介
评论