理解数据结构-绪论

理解数据结构-绪论

工作两年了,想从更多应用和数学的角度上来理解数据结构。

程序设计=数据结构+算法

关键概念

数据项:组成数据元素,是数据不可分割的最小单位

数据元素:组成数据的,有一定意义的基本单位

数据对象:性质相同的数据元素的集合

数据结构:相互之间存在一种或多种特定关系的数据元素的集合(研究数据的组成结构以及数据对象之间相互关系的一门学科)

数据:首先是用来描述客观事物的符号,并且是能被计算机识别并操作的对象,是符号集合。

数据结构分类

由于数据结构是研究数据对象之间的关系的,从视点不同,可以把这种关系分为逻辑结构和物理结构。

逻辑结构:

  • 集合结构
  • 线性结构
  • 树结构
  • 图结构

物理结构:

  • 顺序存储
  • 链式存储

抽象数据类型

包括数据类型及一系列基于其上的操作

原子类型:不可再分解的基本类型,整型、字符型
结构类型;由若干个类型组成,可以再分解

算法

算法的特性

  • 输入输出
  • 有穷性
  • 确定性
  • 可行性

估算算法

事前分析方法:

  • 算法采用的策略方法
  • 编译产生的代码质量(软件支持)
  • 问题的输入规模
  • 机器执行指令的速度(硬件支持)

可控:策略方法,输入规模(特别注意)

事前分析估算方法

进行事前分析估算一般通过计算算法复杂度,算法复杂度包含时间复杂度空间复杂度,这两者很难都做到极致,一般是在两者之间做出权衡,或者根据场景需求不同,来决定两者的优先级。

同时还要注意的是,一定要考虑问题的输入规模,如果将算法的执行操作次数用函数表达出来的话,我们是知道函数

时间复杂度

时间复杂度全称叫做渐近时间复杂度。

我们用T(n)表示关于问题规模n的关键语句执行次数的函数,但T(n)用精确的多项式来表示不易代表算法的效率。如T(n)=2n2+3n+1,但随着n值不断增大,我们会发现,函数中的3n+1的值在总的结果中占得比重越来越少,所以在n趋近于无穷大时,完全可以将函数中的次要项以及常数项忽略。这样我们可以得出结论,T(n)的数量级是由函数中最高项决定的。所以我们得出T(n)=O(f(n))。

其中f(n)表示,随着n增大,T(n)与f(n)的增长率相同,O(f(n))也就是算法的时间复杂度。

常见O阶

  • 常数阶:无论n为多少,T(n)总是一个定值,记为O(1)
  • 线型阶:记为O(n)
  • 对数阶:记为O(logn)
  • 平方阶:记为O(n2)

比较方法

如何比较各个O阶的大小呢,这就要用到高等数学的知识了。

通过前面的概念我们知道,算法的时间复杂度实际上是要找到一个与T(n)函数增长率相同的,相对结构简单的函数f(n)表示,那么比较O阶的大小,就需要比较f(n)的增长速度。

证明不等式主要通过以下几种方法:

  • 两个函数式相减
  • 两个函数式相除
  • 函数单调性
  • 求导

对于幂函数,对数函数以及指数函数之间的比较,要多利用导数与单调性结合。

如O(2n)与O(n3)比较时间复杂度

总结

学习一种数据结构,要从以下几个方面来彻底理解它:

  • 数学定义
  • 抽象数据类型:该结构包含的数据类型,以及定义在其上的一系列操作
  • 数据结构分类:逻辑结构和物理结构两个方面
  • 基于该数据结构的算法操作及复杂度