数据结构知识点-基础部分

数据结构的基本概念

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

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

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

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

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

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

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

存储结构（物理结构）：数据及其逻辑结构在计算机中的表示（映像）。

数据的存储方式：顺序存储、链式存储、索引存储（附加索引表）、散列存储。

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

算法的特性：1. 有穷性；2. 确定性；3. 可行性

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

$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)$

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