数据结构与算法 理论笔记

衡量程序运行的效率——复杂度

时间复杂度

定义：定性描述该算法的运行时间
主要影响关系：代码结构

常用经验

1. 顺序结构的代码，时间复杂度为 O(1)
2. 一层for/while循环遍历，时间复杂度 O(n)
3. 有限个顺序执行的循环遍历，时间复杂度 O(n)
4. k个循环嵌套，时间复杂度 O(n^k)

图的遍历：时间复杂度是 O(n)
二维矩阵：一个排好序的二维矩阵中进行二分查找，时间复杂度是 O(n)
二叉树的遍历-前序、中序、后序：时间复杂度是 O(n)，但二叉查找树，时间复杂度就是O(logn)，因为有序
二分查找：采用分治思想的二分策略，时间复杂度 O(logn)
归并排序：时间复杂度就是O(nlogn)
搜索算法：DFS(深度优先)、BFS(广度优先)时间复杂度 O(n)

斐波拉契数列的第n项，递归求解，时间复杂度 O(2^n) ，包含大量重复计算，因此建议使用HashMap缓存已经计算出的节点

主定理.png

常见的算法时间复杂度由小到大依次为：

常数阶Ο(1)＜对数阶Ο(logn)＜线性阶Ο(n)＜线性对数阶Ο(nlogn)＜平方Ο(n^{2)＜立方阶Ο(n}3)＜…＜指数阶Ο(2^n)＜阶乘阶Ο(n!)。

空间复杂度

定义：一个算法在运行过程中临时占用存储空间大小的量度

常用经验

1. 使用有限个变量存储，即可完成功能，空间复杂度 O(1)
2. 一维的数组/链表，空间复杂度就是 O(n)
3. k维的数组，空间复杂度就是 O(n^k)
4. 如果是有递归的话，那么它递归最深的深度，就是你空间复杂度的最大值。如果你的程序里边递归中又开了数组，那么空间复杂度就是两者的最大值

数据结构基础

栈

先进后出，单调栈，常用来解决浏览器消除匹配问题

队列

先进先出，适用于数据对处理顺序敏感的问题，如约瑟夫环问题

数组

内存连续存储，基于索引查询，时间复杂度O(1)，添加/删除元素，时间复杂度上升至O(n)

树

满足递归特性，处理数据分层和一对多场景，常用的树有：二叉树，红黑二叉树

哈希表

核心思想：函数映射，将记录的存储位置与记录的关键字关联起来。
插入、删除、查找仅需 O(1) 时间复杂度
设计哈希函数方法：

1. 直接定义关键字和地址之间的线性函数：H(key) = a*key + b，a和b为常数
2. 数字分析法：手机号，身份证号
3. 平方取中法：key重复较多，平方后扩大差异
4. 折叠法：key位数较多，分割等长部分后求和合并（忽略进位）
5. 除留余数法：H(key) = key mod p，p为预先设置的数
   常用处理哈希冲突方法：
6. 开放地址法：常用的为线性探测法
7. 链地址法：相同hash地址链表存储

算法思维

递归

将规模大的问题转换为规模小的相同子问题。
步骤：

1. 确定递推公式
2. 找出终止条件

分治

使用分治的先决条件

1. 原问题的解决难度随数据量的减少而降低
2. 原问题可拆分为相互独立的若干小问题
3. 小问题解决完成的解合并后就是大问题的解

例如：
处理 海量 有序 数据的查找问题，预期复杂度与O(logn)相关

排序

排序算法的时间复杂度，空间复杂度，稳定性决定了使用场景。
动画演示各种排序原理：神器：https://visualgo.net/zh

1. 冒泡排序：数据规模较小，时间复杂度O(n) -> O(n^2)，空间复杂度O(1)，稳定
2. 插入排序：，时间复杂度O(n) -> O(n^2)，空间复杂度O(1)，稳定
3. 归并排序：优点速度快且稳定，缺点空间消耗大，时间复杂度O(nlogn)，空间复杂度O(n)，稳定
4. 快速排序：时间复杂度O(nlogn) -> O(n^2)，空间复杂度O(1)，不稳定

排序算法的稳定性：相同元素在不同次排序后的顺序是否严格不变。如：[1, 2, 2, 3]，其中这两个2每次的结果顺序不变即该排序算法是稳定的。

动态规划

常用于解决：最优子结构，无后效性，有重叠子问题（区别于分治的最大特点）

步骤：
分阶段 -> 找状态 -> 做决策 -> 状态转移方程 -> 定目标 -> 终止条件

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。