算法图解

Posted on Edited on In

1. 算法简介

1.1 二分

Why: 复杂度O(n)—>O(logn)

使用限制：有序数组

1.2 大O表示

指出算法运行时间的增速，算法需要做的就是把O(n^2)优化到O(n)等

2. 选择排序

2.1 数组 链表

数组：连续物理空间，可随机访问，增删数据复杂度高

链表：分散无力空间，不可随机访问（只能顺序），增删数据复杂度低

数组 链表
读改 O(1) O(n)
增删 O(n) O(1)

根据互相特性，选择合适的方式，如频繁增删用链表，反之用数组

2.2 选择排序

复杂度：O(n^2)

遍历n 个元素选择 最小/大的，遍历n-1个元素选择 最小/大的

3. 递归

类比：套娃 :call_me_hand:

性能和易读不可兼得

避免死循环！

尾递归可以解决部分性能问题

递归调用栈是性能降低的原因，遵循FIFO

4. 快排

核心：分而治之divide and conquer，快排只是其中的一个应用

思想：递归的一种应用

快排（递归）是一种函数式编程

快排通过基准值（可以选第一个元素）进行分而治之

5. 散列表

实现方式：数组，非链表，检索值key类似数组的下表，可直接访问value

应用：DNS，阻止重复数据(类set集)，作缓存（服务器端）

复杂度 散列平均 散列最糟 数组 链表
查找 1 n 1 n
插入删除 1 n n 1

装填因子（0.4）=散列元素（4）/位置总数（10）

避免冲突：1.良好的散列函数（均匀分布） 2.较低的装填因子（<0.7）

将满时候：1.申请两倍于原来的 新空间 2.hash所有元素到新空间

冲突解决：

  • 开放地址（最简单就是冲突顺延下一位，直到为空）
  • 拉链发（指在某个位子上再拉一条链表，非👖拉链）

6.BFS

广度优先搜索breadth first search，解决无加权最短路径问题之一

应用：国际跳棋，拼写检查，人际关系网络

7. Dijkstra

正加权有向无环图的解决算法

  1. 最短时间内到达的节点
  2. 更新该节点临接节点的开销
  3. 重复
  4. 计算最终路径

解决环：

负加权：bellman ford algorithm

8. Greedy

每步最优–>全局最优，得到近似正确的结果

9.DP

列出所有可能

10. K最邻近算法

11.next

树解决了二分查找中，插入删除O(n)降低到O(log n)，但是降低了随机访问能力

树包括：二叉树，平衡二叉树，B树 B+树，，红黑树

反向索引：散列表，用于创建搜索引擎—>应用：傅里叶变换

并行算法，单机并行or分布式，应用：mapreduce，map->映射 ，reduce->归并

布隆过滤器：庞大的散列表（如谷歌的上亿条），通常使用redis实现，是一种概率型数据结构（偶尔出错），使用理由，存储空间少

hyperLogLog：类似布隆，是个日志

SHA算法

  • 散列的一种应用
  • 判断两个（超大）文件是否相同（散列值相同）
  • SHA（用户输入密码）？== 数据库存储的SHA值，且拖库后无法还原密码
  • SHA是一系列算法的统称，包括SHA-0 ,SHA-1 SHA-2 SHA-3 bcrypt etc
  • SHA全局敏感（改动局部，整体全变），SIMhash局部敏感（局部改变，散列值局部改变），后者用于判断网页是否已经搜集，作业是否抄袭，相似度查询
  • diffie-hellman密钥交换
    • 双方无需知道加密算法，破解难度大
    • 公钥与私钥，client获取公钥后，1.使用公钥加密 2.服务器端使用私钥解密

线性规划：simplex算法