《算法图解》笔记简单整理

《算法图解》

其实读着《大话数据结构》便觉得 这样子挺麻烦的……试试吧还是

不过这样搭配cal Newport的摩斯密码法其实挺有意思

算法图解这本书还是很不错的 简单易懂

1 算法简介

• 二分查找

• 大O表示法

  • 展示最糟情况下的所需时间

• 旅行商问题

  旅行商将前往n个城市 从某处到某处都需要不同的里程 试找出最少的路程方法

  解决这个问题 如若直接遍历 复杂度为O(n)=n!

  ’

2 选择排序

• 元素的位置称为__索引__

属性	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

• 选择排序

3 递归

• 基线条件
• 递归条件

4 快速排序

• 分而治之
  • 找出基线条件
  • 缩小问题 直至符合基线条件
  • （涉及数组的递归 其基线条件一般为数组为空或只含一个元素
• 快速排序
• 平均情况 vs 最糟情况

5 散列表

• 散列函数
• 散列表
  • 模拟映射
  • 防止重复
  • 缓存数据
• 冲突（解决方法
  • 较低的填装因子
  • 良好的散列函数

6 广度优先搜索

• 图的代码实现
• 用deque实现广度优先搜索
  • 设立flag标记有无检查过
• 拓扑排序

7 狄克斯特拉算法

计算网的最小路径

要求：

• 不能有负权边

• 不能构成环

  （否则：弗洛伊德算法

8 贪婪算法

• 近似算法
• 差集
• NP完全问题（只能遍历 而没有一种好的算法

9 动态规划

必须每个子问题都是__离散__的才能有效

• 最长公共子串

• 最长公共子序列

10 K最近邻算法

• 余弦相似度
• 分类（大数据推送hhh
• 回归（预测你对此视频的评分hhh

11 other

• 树
• 反向索引
• 傅里叶变换
• 并行算法
• MapReduce
  • 映射函数
  • 归并函数
• 布隆过滤器
• SHA算法（局部不敏感
• 局部敏感的散列算法
• 线性规划（一生之敌