【重学计算机】数据结构与算法

以你之姓@ 2021-12-21 06:59 238阅读 0赞

## 一、复杂度分析 ##

*  **时间复杂度：**
    
     *  **表示方式**：大O表示法，表示代码执行时间随数据增长的趋势，也叫**渐进时间复杂度**
     *  **计算方法：**加法法则，乘法法则
     *  **常见量级**：O(1)、O(logn)、O(n)、O(nlogn)、O(n2) ... O(nk)、O(2n)、O(n!）
     *  **常见分类**：最好、最坏、平均、摊还
 *  **空间复杂度**：略
 *  **其他：**
    
     *  递归树分析复杂度

## 二、线性表 ##

*  **数组**：连续内存空间
 *  **链表**：不连续的内存空间
    
     *  **分类**：单链表、双链表、循环链表
     *  **tips**：
        
         *  LRU缓存淘汰策略可用**有序单链表**实现
         *  可用增加**散列表**的方式，提高查询链表的效率，降为O(1)
         *  利用**哨兵**简化链表实现
 *  **栈**：先近后出，一种操作受限的线性表
    
     *  **分类**：顺序栈（数组实现）、链式栈（链表实现）
     *  **应用**：函数调用、表达式求解、括号匹配
     *  **tips**：支持动态扩容的顺序栈，摊还分析复杂度还是O(1)
 *  **队列**：先进先出
    
     *  **分类**：顺序队列、链式队列、循环队列、阻塞队列、并发队列

## 三、散列表 ##

*  **应用**：加密、数据校验、负载均衡、分片、分布式（一致性哈希）

## 四、树 ##

*  **概念**：跟节点、叶子结点、父节点、子节点、兄弟节点；高度、深度、层
 *  **分类**：二叉树、完全二叉树、满二叉树、二叉查找树、平衡二叉树、B树
 *  **遍历**：前序、中序、后序、层序
 *  **经典实现：**
    
     *  **平衡二叉查找树**：AVL树、红黑树、伸展树、树堆
 *  **堆：**
    
     *  **定义**：
        
         *  堆是一个完全二叉树；
         *  堆中每一个节点的值都必须大于等于子树中每一个节点
     *  **操作：**
        
         *  **插入**：上浮堆化
         *  **删除**：下滤堆化
         *  **排序**：建堆、排序

## 五、图 ##

## 六、基本算法思想 ##

*  **递归**：

第一步：找到递推公式和终止条件
    f(1) = 1;
    f(2) = 2;
    f(n) = f(n-1)+f(n-2)
    
    第二步：翻译成代码
    int f(int n) {
        
    　　if (n == 1) return 1;
    　　if (n == 2) return 2;
    　　return f(n-1) + f(n-2);
    }

*  **贪心算法**：
    
     *  **分糖果（满足最多孩子）**：从需求小的孩子开始，将最小能满足他的糖果先分给他。依次类推
     *  **钱币找零（用最少纸币）**：先用最大纸币，再依次递减，最后用1元补齐
     *  **区间覆盖（最多选出多少个区间）**：从左到右选，每次选和左面不重合，右端点右尽量靠左的区间，依次类推
 *  **分治算法**：分解、解决、合并
    
     *  **求逆序对**：
     *  **10G订单金额排序**：1-100元，101-200元... 分别排序
 *  **回溯算法**：
    
     *  8皇后问题
     *  0-1背包问题
     *  正则表达式
 *  **动态规划**：
    
     *  0-1背包问题：
     *  **问题特征：**
        
         *  **最优子结构**：最优解中包含子问题最优解
         *  **无后效性**：后面的决策不会影响前面已经确定的决策
         *  **重复子问题**：相同阶段不同决策，含有重复的状态
         *  ![1096103-20190424120859355-531744847.png][]

## 七、排序 ##

*  插入排序
 *  冒泡排序
 *  选择排序
 *  归并排序
 *  快速排序
 *  桶排序
 *  堆排序

## 八、搜索 ##

## 九、查找 ##

*  二分查找
 *  跳表查找

## 十、字符串匹配 ##

*  **单模式匹配：**
    
     *  **BF算法**：暴力匹配
     *  **RK算法**：通过哈希优化
     *  **BM算法**：根据坏字符和好后缀，一次性向右移动多位

## 十一、其他 ##

转载于:https://www.cnblogs.com/flashsun/p/10695000.html

[1096103-20190424120859355-531744847.png]: /images/20211221/a43ef07c1f5a4a9d92d8264edb1dc5c5.png