数据结构与算法:初识
目录
1. 数据结构与算法
1.1 数据结构
数据结构按照存储方式进行分类,如下所示:
- 逻辑结构:数据存储在虚拟逻辑的方式;
- 集合
- 线性
- 树型
- 图型
- 物理结构:数据存储在物理介质的方式;
- 物理介质有硬盘、内存等
按照逻辑结构与物理结构的异同
- 顺序存储结构:逻辑结构与物理结构一致
- 链式存储结构:逻辑结构与物理结构不同
1.2 算法
算法设计的基本准则
- 确定性
- 可行性
- 可读性
- 健壮性
算法效率的评估方式
- 时间效率
- 存储容量
时间算法 | 名称 |
---|---|
O(1) | 常数 |
O(n) | 线性 |
O(log(2)n) | 对数 |
O(nlog(2)n) | nlog(2)n |
O(n^2) | 平方 |
O(n^3) | 立方 |
对数时间复杂度的代码示例以及计算过程
function calc(n) {
let i = 1;
while(i * 2 <= n) { /*执行操作*/ }
}
// 执行次数:2^x = n,即:x=log(2)N
2. 线性表
2.1 数组
时间复杂度
- 查询(retireve):O(1)
- 更新(update):O(1)
- 插入(insert):O(n)
- 删除(delete):O(n)
2.2 链表
时间复杂度
- 查询(retireve):O(n)
- 更新(update):O(n)
- 插入(insert):O(1)
- 删除(delete):O(1)