算法(algorithm)
常用设计模式
-
分治法
把一个问题分区称互相独立的付哦个部分分别求解的思路 -
动态规划法
当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。 -
贪婪算法
常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。 - 线性规划
- 简并法
常用实现方式
时间复杂度
在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。函数：代表算法输入值的字符串的长度的函数。
big-O表示法
时间复杂度常用大O符号表述(big-O表示法)，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被成为是渐近的，亦即考察输入值大小趋近无穷时的情况。
例如：如果一个算法对于任何大小为n（必须比n0大）的输入，它至多需要5n^3 + 3n的时间运行完毕，那么它的渐近时间复杂度是O(n^3)
big-T表示法
为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。
相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为T(n)，定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以用函数T(n)的自然特性加以分类，
例如：T(n) = O(n)的算法被称作“线性时间算法”；而T(n)=O(M^n)和M^n=O(T(n))，其中M ≥ n > 1的算法被称作“指数时间算法”
常见时间复杂度列表
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多
二叉树
二叉树是由根节点，左子树，右子树组成，左子树和右子树分别是一个二叉树。
二叉树每个节点不允许超过两个。通过将子节点的个数限定为2，可以写出高效的程序在树中插入、查找和删除数据。
因为树的定义本身就是递归定义， 因此采用递归的方法实现树的三种遍历容易理解而且代码比较简洁。
二叉树的遍历思想主要有这四种：
- 广度遍历：按照层次一层层遍历;
- 前序遍历：访问根–>遍历左子树–>遍历右子树;
- 中序遍历：遍历左子树–>访问根–>遍历右子树;
- 后序遍历：遍历左子树–>遍历右子树–>访问根;
二叉查找树（BST）
二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。这一特性使得查找的效率很高，对于数值型和非数值型的数据，比如单词和字符串，都是如此。每一个节点都有一个与之相关的值，该值有时被称为键。
BST先要有一个insert()方法，用来向树中加入新节点。具体算法如下：
- 设根节点为当前节点(current)。
- 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反之，执行第4步。
- 如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。
- 设新的当前节点为原节点的右节点。
- 如果当前节点的右节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。
利用引用类型的值共享和while判断循环的insert()方法
if(root == null){
root = n
}else {
var current = root
while(true){
if(current.value > data){
if(current.left == null){
current.left = n
break; //<a href="/tag/tuichu/" target="_blank" class="keywords">退出</a>循环
}else {
current = current.left //重新定义三分钟（当前节点）
}
}else {
if(current.right == null){
current.right = n
break;
}else {
current = current.right
}
}
}
}
}
var root = null
insert(1)
insert(2)</code></pre>深度优先搜索
访问体格没有访问过的顶点，将它标记为已访问，再递归地去访问在初始顶点的邻接表中其他没有访问过的定点。
算法导论
插入排序 INSERTION_SORT
var a = [4,7,2,8,1,3,5]
//思路：
//纸牌是一张一张得拿，此时数组表示这堆纸牌我们还没拿
//拿上第一张
//拿上第二张，与第一张对比，比第一张大就不动，比第一张小就往前排
//拿上第三张，与前一张比，大就不动，小就往前移动一格再与前一张比（此时前一张已经变成刚刚移动之前得前两张）
for(let i=0;i=0&&key 最坏情况
对于算法，往往只求于最坏情况运行时间，即对规模为n的任何输入，算法的最长运行时间。下面给出这样做的两点理由：
- 运行时间上限，不会比这个运行时间更长了
- 对某些算法，最坏情况经常出现。例如，当在数据库中检索一条特定信息时，若该信息不在数据库中出现。对于缺失信息的检索可能是频繁的。
