概述
算法的两个关键指标 时间和空间 , 核心就是衡量这两个指标的平衡,根据需求 ,用空间换时间,或者时间换空间,它有5个基本特征: 输入 输出 有穷性 确定性 可行性
定义 就是用一条接一条的指令解决给定的问题
算法分析 用来帮助我们确定时间和空间开销方面哪一种算法有效
客观的比较算法 : 给定 一个算法 的函数 f(n) 比较不同函数的 在n的输出规模下的 运算时间,空间
增长率: 随输入规模的增加 ,所增加的运行时间 ,它是输入规模的函数
一般用O表示最坏情况 上界
常用的增长率有
空间复杂度就是看可能要分配的内存 数量级
排序
| 排序算法 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n) | O(n) | O(1) | 数组不稳定、链表稳定 |
| 插入排序 | O(n) | O(n) | O(1) | 稳定 |
| 快速排序 | O(n*logn) | O(n) | O(logn) | 不稳定 |
| 堆排序 | O(n*logn) | O(n*logn) | O(1) | 不稳定 |
| 归并排序 | O(n*logn) | O(n*logn) | O(n) | 稳定 |
| 希尔排序 | O(n*logn) | O(n) | O(1) | 不稳定 |
| 计数排序 | O(n+m) | O(n+m) | O(n+m) | 稳定 |
| 桶排序 | O(n) | O(n) | O(m) | 稳定 |
| 基数排序 | O(k*n) | O(n) | 稳定 |
- 均按从小到大排列
- k：代表数值中的 “数位” 个数
- n：代表数据规模
- m：代表数据的最大值减最小值
- 来自：wikipedia . 排序算法
查找
| 查找算法 | 平均时间复杂度 | 空间复杂度 | 查找条件 |
|---|---|---|---|
| 顺序查找 | O(n) | O(1) | 无序或有序 |
| 二分查找（折半查找） | O(logn) | O(1) | 有序 |
| 插值查找 | O(log(logn)) | O(1) | 有序 |
| 斐波那契查找 | O(logn) | O(1) | 有序 |
| 哈希查找 | O(1) | O(n) | 无序或有序 |
| 二叉查找树（二叉搜索树查找） | O(logn) | ||
| 红黑树 | O(logn) | ||
| 2-3树 | O(logn - logn) | ||
| B树/B+树 | O(logn) |
图搜索算法
| 图搜索算法 | 数据结构 | 遍历时间复杂度 | 空间复杂度 |
|---|---|---|---|
| BFS广度优先搜索 | 邻接矩阵 邻接链表 |
O(|v|) O(|v|+|E|) |
O(|v|) O(|v|+|E|) |
| DFS深度优先搜索 | 邻接矩阵 邻接链表 |
O(|v|) O(|v|+|E|) |
O(|v|) O(|v|+|E|) |
其他算法
| 算法 | 思想 | 应用 |
|---|---|---|
| 分治法 | 把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并 | 循环赛日程安排问题、排序算法（快速排序、归并排序） |
| 动态规划 | 通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法，适用于有重叠子问题和最优子结构性质的问题 | 背包问题、斐波那契数列 |
| 贪心法 | 一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法 | 旅行推销员问题（最短路径问题）、最小生成树、哈夫曼编码 |
若有收获，就点个赞吧
0 人点赞
