Leo Technology Stack
Leo
2021-04-13

数据结构基础

# 算法的复杂度

# 时间复杂度

算法运行后对时间需求量的定性描述

# 大O表示法

  • 算法效率严重依赖于操作（operation）数量
  • 操作数量的估算可以作为时间复杂度的估算
  • 在判断时首先关注操作数量的最高次项
O(5) = O(1)
O(2n+1) = O(2n) = O(n)
O(n^2+n+1) = O(n^2)
O(3n^3+1) = O(3n^3)=O(n^3)
1
2
3
4

# 常见的时间复杂度

//线性阶时间复杂度: O(n)
for(int i=0;i<n;i++>){
    //复杂度为O(1)的程序语句
}
//循环次数: n
1
2
3
4
5
//对数阶时间复杂度: O(logn)
int i = 1;
while(i<n){
  //复杂度为O(1)的程序语句
  i*=2;
}
//循环次数: log_2^N
1
2
3
4
5
6
7
//平方阶时间复杂度: O(n)
for(int i=0;i<n;i++>){
  for(int i=0;i<n;i++>){
    //复杂度为O(1)的程序语句
  }
}
//循环次数: n2
1
2
3
4
5
6
7

# 算法效率的度量

从上到下效率依次递减

操作数量 大O表示法 术语
15 O(1) 常数阶
2log_2(n) O(log_2(n)) 对数阶
3n+5 O(n) 线性阶
3nlog_2(n)+4n+2 O(n*logn) nlogn阶
3n^2+2n+1 O(n^2) 平方阶
6n3+n2+2n+1 O(n^3) 立方阶级
2^n+1 O(2^n) 指数阶
n!+4 O(n!) 阶乘阶

O(1) < O(log_2(n)) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

# 总结

  • 时间复杂度是算法运行时对时间的需求量
  • 大O表示法用于描述算法的时间复杂度
  • 大O表示法只关注操作数量的最高次项
  • 常见的时间复杂度为，线性阶、平方阶和对数阶

# 空间复杂度

算法运行后对空间需求量的定性描述

面试题：当两个算法的大O表示法相同时，是否意味着两个算法的效率完全相同？

当算法的大O表示法相同时，意味着这两个算法的效率是在同一个级别的，但不意味着这两个算法效率完全相同。

  • 一般而言，工程中使用的算法，时间复杂度不超过O(n^3)
  • 算法分析与设计时，重点考虑最坏情况下的时间复杂度
  • 数据结构课程中重点关注算法的时间复杂度
  • 大O表示法同样适用于算法的空间复杂度
  • 空间换时间是工程开发中常用的策略

# 线性表

# 线性表的表现形式

  • 零个或多个数据元素组成的集合
  • 数据元素在位置上是有序排列的
  • 数据元素的个数是有限的
  • 数据元素的类型必须一样

# 线性表的抽象定义

  • 线性表是具有相同类型的n(n>=0)个数据元素的有限序列

ai是表项(数据元素)，n是表长
1

# 线性表的性质

  • a0为线性表第一个元素，只有一个后继
  • a(n-1)为线性表的最后一个元素，只有一个前驱
  • 除了a0、a(n-1)的其他元素ai,既有前驱也有后继
  • 直接支持逐项访问和顺序存取

# 线性表的常用操作

操作 说明
(增)将元素插入到线性表 bool insert(int position, ElemType value)
(删)将元素从线性表中删除 bool remove(int position)
(改)设置目标位置的元素的值 bool set(int i, ElemType value)
(查)获取目标位置的元素的值 bool get(int i,ElemType value)
获取线性表的长度 int length()
清空线性表 bool clear()

# 线性表的抽象的实现

# 小结

  • 线性表是数据元素的有序并且有限的集合
  • 线性表中的数据元素必须是相同类型
  • 线性表可用于描述排队关系的问题
  • 线性表在程序中表现是一种特殊的数据类型
  • 线性表在C++中表象为一个抽象类

# 顺序存储线性表

# 顺序存储的定义

线性表的顺序存储结构指的是用一段连续地址的存储单元一次存储线性表中的数据元素

# 设计思路

# 静态StaticList

  • 使用原生数组作为顺序存储空间
  • 使用模板参数决定数组大小

# 动态数组DynamicList

  • 申请连续堆空间作为顺序存储空间
  • 动态设置顺序存储空间的大小
  • 保证重置顺序存储空间时的异常安全性

# 数组

# 栈

# 顺序栈

# 共享栈

# 链栈

# 队列

# 顺序队

# 循环队列

# 链队

# 双端队列

# 树

  • 度
  • 树的度
  • 分支节点
  • 叶子节点
  • 节点层次
  • 节点高度
  • 节点深度
  • 树的高(深)度
  • 有序树
  • 无序树
  • 路径
  • 路径长度
  • 森林

# 二叉树

# 满二叉树

# 完全二叉树

# 二叉排序树

# 二叉搜索树

# 红黑树

# 平衡二叉树(AVL)

# B树(B-tree)

# B+树

# B*树

# 哈夫曼树（最优二叉树）

# 字典树

# 堆

# 并查集

# 布隆过滤器

# 图

# 无向图

# 有向图

# 广度优先搜索算法

# 深度优先搜索算法

# 排序

  • 插入排序
  • 折半插入排序
  • 希尔排序（缩小增量排序）
  • 交换排序
  • 冒泡排序
  • 快速排序
  • 选择排序
  • 堆排序
  • 拓扑排序

# 复杂度 (opens new window)

编辑此页 (opens new window)
上次更新: 2022-04-28, 11:21:32
Theme by Leo | Copyright © 2016-2022 Leo | MIT License