数据结构与算法:基础知识解析

发表时间: 2019-01-18 21:04

一、数据结构相关概念

1、数据元素、数据项

数据元素由若干数据项组成,数据项是最小的标识单位。

数据元素和数据项

2、数据对象

性质相同的数据元素的集合。

3、数据结构

1)、概念:相互之间存在一种或多种特定关系的数据元素的集合。包括逻辑结构和物理结构。

2)、逻辑结构:对数据关系的描述,包括:集合、线性、树形、图形。

数据逻辑结构示意图

3)、物理结构:存储结构,也就是用计算机语言实现数据的逻辑结构。包括:顺序存储,链式存储,索引存储,散列存储等。

4、数据类型

包括基本类型,结构类型和抽象数据类型ADT:

  • 基本类型:int, char, float等
  • 结构类型:数组等
  • 抽象数据类型ADT:包括数据对象(D)、数据关系(S)、基本操作(P)

二、算法相关概念

1、五个特征

有穷性、确定性、可行性、输入和输出

2、设计要求

正确性、可读性、健壮性、效率和低存储

3、时间和空间复杂度

1)时间复杂度:将算法中基本操作的执行次数作为时间复杂度的度量

2)关系:O(1)<O(logN)<O(N)<O(NlogN)<O(N2)<O(NK(k>2))<O(2N)<O(N!)<O(NN)

3)空间复杂度:算法在运行时临时占用的存储空间的大小