数据结构与算法 知识体系

image

复杂度

有时间复杂度和空间复杂度

时间复杂度

  • O(1) 常数时间算法 (按下标访问数组某个位置的值)
  • O(n) 线性时间算法 (求数组的和)
  • O() 对数时间算法 (二分查找)
  • O() 平方级时间算法 (冒泡排序)
  • O() 指数级时间算法

计算 1 到 n 的和

O(1) 常数时间算法

1
sum = n*(n+1) / 2;

O(n) 线性时间算法
1
2
3
for(int i = 1; i <= n; i++){
sum += i;
}

计算 1 到 n 任意两数乘积之和

O() 平方级时间算法

1
2
3
4
5
for(int i = 1; i <= n; i++){
for(int j = i+1; j <= n; j++){
sum += i*j;
}
}

复杂度排序

complexity

选择准则

  • 根据具体需求选择数据结构
  • 运行时间很重要, 时间复杂度优先于空间复杂度
  • 运行时间取决于选择的数据结构和算法
  • 问题规模较小时, 区别不大
  • 问题规模较大时, 不同的时间复杂度差异很大

场景

搜索引擎

索引: 选择数据结构
搜索: 选择算法

数据结构

物理结构

  • 顺序存储 —— 连续空间
  • 离散存储 —— 非连续空间

逻辑结构

  • 线性表 (ArrayList、LinkedList)
  • 数组 (矩阵)
  • 栈、队列、集合
  • 哈希表
  • 树(树、二叉树、线段树)、堆
  • 图(有向图、无向图)