sha3算法_【CS】Python算法概念篇

目录

1. 大O表示法
2. 递归
3. 分而治之D&C
4. 最短路径算法
5. 贪婪算法
6. 动态规划
7. K邻近算法
8. 其他

1.大O表示法

• O(logn)对数时间&＃xff0c;如二分查找
• O(n)线性时间&＃xff0c;如顺序查找
• O(nlogn) 如快速排序、归并排序
• O(n^2) 如冒泡、选择、插入、谢尔排序
• O(n!) 如旅行商问题

2.递归

3.分而治之D&C

• 找出基线条件(尽可能简单)&＃xff0c;问题分解缩小规模直到符合基线条件

4.最短路径算法

• 正数加权无环图:Dijkstra算法
• 非加权图:广度优先BFS

广度优先搜索BFS
用处:A到B是否有路径/哪条路最短
应用:国际跳棋/拼写检查器/找关系最近的医生

• 负权边图:Bellman-Ford算法

5.贪婪算法

• 定义:每步都采取最优(局部最优->全局最优)找到近似解
• 应用

NP完全问题(Non-deterministic Polynomial Complete)
定义: 涉及组合/不能拆为小问题有各种情况/序列难解决/集合难解决/集合覆盖/旅行商
(1)旅行商问题
(2)集合覆盖问题:选广播台覆盖州/选球员技能覆盖
(3)背包问题
(4)卡车装箱
(5)教室调度

6.动态规划

• 简介:涉及网格&＃xff0c;各单元格为子问题&＃xff0c;优化条件下优化某种指标
• 应用:背包问题/最长公共子串/最长公共子序列/DNA链/gitdiff/断字/编辑距离(Levenshtein distance)

7.K邻近算法

• 分类时看距离它最近的三个邻居
• 应用:推荐系统(用户分类/面包预测销量(天气/日期/活动))

8.其他

• 机器学习

应用: OCR:线段、点、曲线/语言识别、人脸识别/垃圾邮件过滤器:朴素贝叶斯分类器/预测股票市场

• 二叉树相关

应用: B树/红黑树/堆/伸展树

• 反向索引

应用: 单词映射页面

• 傅里叶变换

应用:处理信号(压缩音乐/压缩图片/地震监测/DNA分析)

• 并行算法

简介: 速度非线性提升(有管理开销&＃43;负载均衡)

• 分布式算法

简介: MapReduce&＃43;Hadoop

• 布隆过滤器/Hyperloglog

简介: 概率型数据结构(会错搜不会漏搜)
Hyperloglog判断搜索是否在日志中&＃xff0c;近似计算集合中不同元素数

• SHA算法

应用: 比较文件/检查密码(SHA-2/SHA3/bcrypt)

• 局部敏感的散列算法(simhash)

应用: 检查相似程度(判断网页是否已收集/判断论文是否抄袭)

• Diffle-Hellman密钥交换(公钥&＃43;私钥)

应用: 双方无需知道加密算法&＃43;难以破解

• 线性规划

定义: 给约束条件最大程度下改善指标
应用: 原材料数量约束下利润最大/时间预算约束下支持票数最大