数据结构与算法:初识

目录

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)

3. 排序