数据结构与算法 知识体系

复杂度

有时间复杂度和空间复杂度

时间复杂度

• O(1) 常数时间算法 (按下标访问数组某个位置的值)
• O(n) 线性时间算法 (求数组的和)
• O($logn$) 对数时间算法 (二分查找)
• O($n^2$) 平方级时间算法 (冒泡排序)
• O($2^n$) 指数级时间算法

计算 1 到 n 的和

O(1) 常数时间算法

sum = n*(n+1) / 2;

O(n) 线性时间算法

for(int i = 1; i <= n; i++){
    sum += i;
}

计算 1 到 n 任意两数乘积之和

O($n^2$) 平方级时间算法

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

复杂度排序

选择准则

• 根据具体需求选择数据结构
• 运行时间很重要, 时间复杂度优先于空间复杂度
• 运行时间取决于选择的数据结构和算法
• 问题规模较小时, 区别不大
• 问题规模较大时, 不同的时间复杂度差异很大

场景

搜索引擎

索引: 选择数据结构
搜索: 选择算法

数据结构

物理结构

• 顺序存储 —— 连续空间
• 离散存储 —— 非连续空间

逻辑结构

• 线性表 (ArrayList、LinkedList)
• 数组 (矩阵)
• 栈、队列、集合
• 串
• 哈希表
• 树（树、二叉树、线段树）、堆
• 图（有向图、无向图）