数据结构概念&&算法复杂度

数值问题->数学方程

非数值问题->数据结构

数据结构概念

数据结构

数据(data),能输入到计算机中并能被计算机识别处理的符号,分为:

  1. 数值数据

  2. 非数值数据

数据元素(data element),数据的基本单位

数据项(data item), 构成数据元素的最小单位

数据结构(data structure), 相互之间存在一定关系的数据元素的集合

数据的逻辑结构(logical structure), 数据元素之间的逻辑关系

数据的存储结构(storage structure), 数据及其逻辑结构在计算机内部的表示, 主要有顺序结构和链式结构

抽象数据类型(ADT)

数据类型(data type), 一组值的集合以及定义在这个值集合上的一组操作的总称

**抽象数据类型(abstract data type, ADT), **一个数据以及定义在该模型上的一组操作的总称

二者区别: dt是高级语言的基本数据类型,adt是用户指定的数据

算法概念

算法即解决问题的方法

性质:

  1. 有穷性

  2. 可行性

  3. 确定性

好的算法:

  1. 正确

  2. 健壮

  3. 容易理解

  4. 步骤不超过9个

  5. 高效

算法描述:

  1. 伪代码

算法分析

时间复杂度

使用事前分析估算– 渐进复杂度(asymptomatic complexity)

算法运行时间T是问题规模n的函数,T(n)

基本语句的执行次数是与整个算法的执行次数成正比的

算法的时间复杂度(time complexity): 当问题规模充分大时,基本语句执行次数在渐进意义下的阶,用O表示

非递归算法时间复杂度

1
2
3
for(int i=1;i<=n;i*=2)
  ++x;

**解: ** ++x;是基本语句设执行次数为T(n),则

2^{T(n)} \le n, T(n) \le log_2{n}

递归算法时间复杂度

递归算法通用递归式:

T(n)=\begin{cases}c& \text{n=1}\aT(n/b)+cn^k& \text{n>1}\end{cases}

结果:

MommyTalk1646224458244.png

空间复杂度

算法的空间复杂度(space complexity): 算法在执行过程中需要的辅助空间的数量