数据结构——基本概念

1. 数据元素(data element)是数据的基本单位。

2. 数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。

3. 通常有4种基本结构：
   (1)集合
   　　只有“同属于一个集合”的关系
   (2)线性结构
   　　结构中的元素之间存在一对一的关系
   (3)树状结构
   　　结构中的元素存在一对多的关系
   (4)图状结构或网状结构
   　　结构中的元素存在多对多的关系

4. 逻辑结构：数据元素之间的相互关系称为逻辑结构。

5. 物理结构： 数据结构在计算机中的表示（又称映像）称为数据的物理结构，又称存储结构。

6. 算法的五个特性：
   (1)有穷性
   　　一个算法总是在有穷步之后结束，每一步都可以在有穷时间内完成
   (2)确定性
   　　每一条指令都必须有确切的含义，读者理解时不会产生二义性，任何条件下，相同的输入只能得出相同的输出
   (3)可行性
   　　算法中的所有操作都是可以通过已经实现的基本操作执行有限次得到
   (4)输入
   　　一个算法有零个输入或多个输入
   (5)输出
   　　一个算法有一个或多个输出

7. 时间复杂度：它是一个关于问题规模n的函数，用来衡量算法的执行时间，它不依赖于计算机硬件和软件的性能，只与问题的规模有关。一般只考虑一个算法中最基本的操作的执行次数，并选取函数中关于n增长速度最快的项，将其系数置为1，作为该算法的时间复杂度。
   比如：

for i in range(n):
      a = a + i

上面的代码的时间复杂度记作O(n)，因为最基本的操作是
a = a + i
这个操作一共执行了n次。
再比如：

for i in range(2n):
      for j in range(n):
          a = a + j

这个算法的基础语句一共执行了2n×n次，也就是2n^{2次，该算法的时间复杂度记作O(n}2)

7. 空间复杂度：与时间复杂度类似的定义，只不过是用来衡量算法使用的存储空间的规模的函数。通常也记作O。