数据结构的基本概念

  • 数据结构
    • 逻辑结构
      • 线性结构
      • 非线性结构
    • 存储结构(物理结构)
    • 数据的运算

数据:能输入到计算机中,并能被计算机程序识别和处理的符号。

数据元素:数据的基本单位。

数据项:构成数据元素的最小单位。

数据结构:相互之间存在一定关系的数据元素的集合。

四类基本数据结构:集合、线性结构、树形结构、图形结构。

逻辑结构:数据元素以及它们之间的关系。

存储结构(物理结构):数据及其逻辑结构在计算机中的表示(映像)

数据的存储方式:顺序存储、链式存储、索引存储(附加索引表)、散列存储。

算法:对特定问题求解的一般步骤,是指令有限序列

算法的特性:1. 有穷性;2. 确定性;3. 可行性

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

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)O(1) < O(log_2 n) < O(n) < O(n log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

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