算法
[TOC]

斐波那契数列介绍?

别称:黄金分割数列
从第三位起,每个数字都是前两位数字之和
[3, 5, 8, 13, 21]
1
//迭代法生成斐波那契数列
2
function fib(n) {
3
var fib_n = function(curr, next, n) {
4
if (n == 0) {
5
return curr;
6
}
7
else {
8
return fib_n(next, curr+next, n-1);
9
}
10
}
11
return fib_n(0, 1, n);
12
}
13
alert(fib(40));
Copied!

常见的算法有哪些?

  • 排序算法:快速排序,归并排序 、计数排序(8大排序算法)
  • 搜索算法:回溯、递归、剪枝技巧
  • 图论:最短树、最小生成树、网络流建模
  • 动态规划:背包问题、最长子序列、计数问题
  • 基础技巧:分治、倍增、二分、贪心
参考资料:

分治算法?

适用情况:
  1. 1.
    规模缩小到一定程度就可以容易地解决
  2. 2.
    可以分解为若干个较小的相同问题,具有最优子结构性质
  3. 3.
    子问题的解可以合并为该问题的解
  4. 4.
    子问题相互独立,子问题不包含公共的子问题
实现流程:
类似数学归纳法,找到解决问题的求解方程公式,然后根据方程公式设计递归程序
  1. 1.
    【分解】原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
  2. 2.
    【解决】规模较小而容易则直接解决,否则递归解决子问题(考虑随着问题规模增大时的求解方法)
  3. 3.
    【合并】将子问题的解合并的为原问题的解,找到求解的递归函数(各种规模和因子),设计递归程序即可
使用案例:
  • 二分搜索
  • 快速排序
参考资料:

递归算法介绍?

函数中存着调用函数本身的情况,这种现象就叫递归
联想(汉诺塔):
把用木块(一共5块)叠起来的金字塔,转换到另一个柱子上,可以使用一个中间柱子,每次只能移动一个木块,大木块不能压在小木块上面,最小路径
通用解决思路(步骤):
  • 【实现相同函数】把一个问题分解成具有相同解决思路的子问题,能调用一个函数实现
  • 【终止条件】函数调用前判断终止条件
img
参考资料:

动态规划算法?

参考资料:

贪心算法介绍?

贪心算法(贪婪法),只考虑当下最优解,不考虑全局。希望从:局部最优解-> 全局最优解,并经常却不是
步骤:
  1. 1.
    【拆分】:把问题拆成若干步骤
  2. 2.
    【每步最优解】每一步都选取当前状态 最好/优的选择(局部最有利的选择)
  3. 3.
    【循环】堆叠出的结果也是最好/优的解
联想(找零钱,最少数量):找零钱:31块
核心思想:只考虑当下最优解,不考虑全局
  • 找出符合条件中(x≤31),最优选择:20元
  • 找出符合条件中(x≤11),最优选择:10元
  • 找出符合条件中(x≤1),最优选择:1元
缺点案例:找零钱41元
如果此时货币面值里有(25元,20元,10元,5元,1元)
  • 贪心算法的策略:25+10+5+1
  • 实际最优解策略: 20+20+1
优点:
  • 简单,高效,省去了为找最优解可能需要穷举操作,通常作为其他算法的辅助算法来使用
缺点:
  • 不考虑总体,每次选取局部最优解,不再进行回溯处理,所以很少情况下得到最优解
参考资料:

回溯算法介绍(属于深度优先搜索)?

回溯法(试探法):是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原来先把并不优或达不到目标,就退回一步重新先把,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态点称为“回溯点”
回溯法属性深度优先搜索,由于是全局搜索,复杂度相对高。
联想:
走迷宫,
  • 【试探性执行】先选择一条路,开始走
  • 【发现不通,准备返回】如果此路不通,再回到(回溯)上一个岔路口
  • 【在节点换条路走】再下一条路,直到找到目的地;
参考资料:

数组排序?

  1. 1.
    array的sort 方法
  2. 2.
    冒泡排序

常见的排序算法有哪些?

  1. 1.
    冒泡排序: :相邻数对大小互换位置,循环对比两层完成
  2. 2.
    选择排序:选择排序是最直观的排序,通过确认一个key最大或最小值,再和其他数中找到最大/小的值交换到对就位置
  3. 3.
    插入排序:
  4. 4.
    希尔排序
  5. 5.
    归并排序
  6. 6.
    快速排序:通过一趟排序将待排序记录分隔成独立的两部分,其中一部分记录的数据均比另一部分的数据小,则可分别对这两部分记录继续进行排序,以达到整个序列有序;
  7. 7.
    堆排序
  8. 8.
    计数排序:
  9. 9.
    桶排序
  10. 10.
    基数排序
参考资料(包含算法可视化动图):https://github.com/damonare/Sorts

冒泡排序

定义:相邻数对大小互换位置,循环对比两层完成
冒泡排序:
Could not load image
img

选择排序

定义:选择排序是最直观的排序,通过确认一个key最大或最小值,再和其他数中找到最大/小的值交换到对就位置
算法实现:
  • 确认比较值:默认第一个
  • 找到最小数:找到剩余数中比比较值小的数
  • 位置替换: 把找到的最小值替换到比较值的位置
  • 重复步骤: 二层循环
img

快速排序

定义:通过一趟排序将待排序记录分隔成独立的两部分,其中一部分记录的数据均比另一部分的数据小,则可分别对这两部分记录继续进行排序,以达到整个序列有序;
算法实现:
  • 确认基准:从数列中挑出一个元素,称为‘基准’(pivot)
  • 分区操作:小于基准放前,大于基于放后,完成后,基准就位于中间位置
  • 递归操作(确认基准->分区操作):重复上面操作步骤
img

插入排序

定义:通过构建有序序列,对于未排序数据,在已排序序列中,从后向前扫描,找到相应位置并插入(联想:打扑克牌摸牌过程)
实现:
  • 开始:先取第一个元素,默认为有序数列
  • 摸牌并比较:在已经排序的数列上找到,从后向前查找,发现比他小的数据,就插入在它的后面

希尔排序

是简单插入排序的改进版,它与插入排序的不同之处在于,它会优先比较距离较远的元素,别名缩小增量排序
定义:希尔排序的核心在于间隔序列(可提前设定好,也可动态定义间隔序列)的设定

常见的查找算法?

二分查找法

  • 使用范围:找查对象是一个有序的数据结构
  • 介绍:在一个有序数据中,将数据折中,每次折中的数据要和查找的数据进行比较,然后不断的缩小查找的范围,直到查到找或者区间为0为止;
  • 案例:
    • 判断一个字母,数据在数组中的索引;
    • 猜数字游戏

线性查找

  • 使用范围:不限
  • 特点:简单遍历,判断是否存在
  • 案例:判断一个目标对象,在数据中的索引

二叉树介绍?

二叉树是一种非常基础和重要的数据结构
运用:
  • 前序:显示目录
  • 中序:实现表达式,在编译器底层很用
  • 后序:计算目录内的文件及其信息
特点:
  • 每个结点的长度都不大于2
  • 每个结点的孩子结点次序不能任意颠倒
二叉结的遍历方法分类:(要使用到栈、队列、递归等)
  • 深度优先遍历
  • 广度优先遍历

深度优先遍历和广度优先遍历的区别?

二叉树的遍历概念。
深度优先遍历(DFS)
定义:从根节点出发,沿着左子树方向进行纵向遍历,直到找到叶子节点为 止。然后右子树节点遍历,直到遍历完所有可达节点为止。
分类:
  • 前序:
  • 中序:
  • 后序:
广度优先遍历(BFS)
定义:从根节点出发,在横向遍历二叉树的基础上,纵向遍历二叉树的层次;
遍历思想:递归
图示:
img
上图搜索顺序
DFS:ABDECFG
BFS:ABCDEFG
表达式用二叉树进行表示:
(a+bc)-d/*e
Could not load image
img