预备知识

1. 逻辑结构

• 集合结构：数据元素构成了一个无序且无重复元素的集体；各个数据元素同属于一个集合，但它们之间不存在任何直接关系；
• 线性结构（又称线性表）：数据元素按照某种线性顺序进行排列，形成一对一的关系链；除首尾元素外，每个数据元素都有一个唯一的前驱和后继；
• 树形结构：在树形结构中，数据元素组织成一种层次关系，表现为一对多的父子关系；每一个数据元素（称为节点）可能有零个、一个或多个子节点；除根节点外，每个节点都恰好有一个父节点；
• 图形结构：图形结构的数据元素间形成了一个多对多的关系网，任意两个元素之间都可以存在直接联系；在这种结构中，任意节点可以拥有任意数量的邻接节点，体现了复杂系统中各元素之间的多重并行关联特性；

2. 物理结构

物理结构	特征	优点	缺点
顺序存储	一段连续的内存空间	随机访问	插入、删除效率低，大小固定
链式存储	不连续的内存空间	大小动态扩展，插入、删除效率高	不能随机访问
索引存储	整体无序，索引块间有序	是对顺序表的改进，查找效率高	需额外空间存储索引表
散列存储	数据元素存储位置与散列值存在对应关系	查找位置基于数据本身，查找存储效率高	存储随机，不便于顺序查找

3. 时间复杂度

算法的时间复杂度记为：T(n) = O(f(n))；

a)加法规则

T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n))) 

b)乘法规则

T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n)) 

c)常见时间复杂度

O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

例：下列程序段的时间复杂度是O(n)

int sum = 0;
for(int i = 1; i < n; i*=2){
    for(int j = 0; j < i; ++j){
        ++sum;
    }
}

4. 空间复杂度

算法的时间复杂度记为：S(n) = O(g(n))；

算法原地工作是指算法所需辅助空间为常量，即O(1)；

例：下列程序段的空间复杂度是O(2ⁿ)

long getFib(int n){
    if(n < 2){
        return n;
    }
    return getFib(n-1) + getFib(n-2);
}