算法
一个算法应该是问题求解步骤的描述
Algorithm by definition is precise steps that describes the solution of a certain task or a problem.
算法（algorithm）是对特定问题求解步骤的一种描述，是指令的有序序列，其中每一条指令表示一个或多个操作。
算法具有5个基本特征：
- 有穷性
- 确定性
- 可行性
- 输入（$\geq 0$）
- 输出（$\geq 1$）
查找方法
排序方法
图相关
相关内容暂时隐藏
-
Post not found: Algo-BFS 广度优先搜索
- 用于在非加权图中查找最短路径
-
Post not found: Algo-狄克斯特拉算法 狄克斯特拉算法
- Dijkstra’s Algorithm
- 用于在加权图中查找最短路径
- 不能用于包含负权边的图
- Dijkstra’s Algorithm
-
Post not found: Algo-贝尔曼-福德算法 贝尔曼-福德算法
- 用于含负权边的加权图查找最短路径
- Post not found: Algo-贪婪算法 贪婪算法
算法
数据结构
通用知识
运行时间
- 算法运行时间并不以秒为单位
- 算法运行时间是从其增速的角度度量的
- 算法运行时间用大O表示法表示
大O表示法
- 指出了算法运行时间的增速
表示的并非是以秒为单位的速度
- 指出了最糟情况下的运行时间
常见的大O运行时间：
- $O(\log{n})$：对数时间
- 二分查找
- $O(n)$：线性时间
- 简单查找
- $O(n\log{n})$
- 快速排序
- $O(n^2)$
- 选择排序
- $O(n!)$
- 旅行商问题
算法的运行时间通常有个常量$c$，表示算法所需的固定时间
如：简单查找的运行时间为10ms$*n$，二分查找的运行时间为1s$*\log{n}$。其中，10ms和1s都是常量
- 通常情况下，常量几乎没什么影响
- 但有时候，常量的影响可能很大
如：运行时间都为$O(n\log{n})$的快速排序和合并排序，快速排序将会快很多
常见的数组和链表操作的运行时间：
| 数组 | 链表 | |
|---|---|---|
| 读取 | $O(1)$[1] | $O(n)$[2] |
| 插入 | $O(n)$[3] | $O(1)$[4] |
| 删除 | $O(n)$[5] | $O(1)$[6] |
- 数组擅长随机访问
- 链表擅长插入和删除
