0%

算法图解

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算法