数据结构与算法总结
数据结构与算法总结
一、常见数据结构
1.数组 (Array)：
特点：连续内存空间，元素通过索引访问。
时间复杂度：访问元素为O(1)，插入/删除元素平均为O(n)（需要移动元素）。
应用场景：随机访问频繁，数据大小已知的情况。
2.链表 (Linked List)：
特点：节点由数据和指向下一个节点的指针组成，内存不连续。
时间复杂度：访问元素为O(n)，插入/删除元素为O(1)（只需更改指针）。
类型：
单链表（Singly Linked List）
双向链表（Doubly Linked List）
循环链表（Circular Linked List）
应用场景：频繁插入和删除操作，数据动态变化。
3.栈 (Stack)：
特点：后进先出（LIFO），只允许在一端（栈顶）进行插入和删除操作。
时间复杂度：插入/删除操作为O(1)。
应用场景：递归问题、表达式求解、括号匹配等。
4.队列 (Queue)：
特点：先进先出（FIFO），在队尾插入元素，在队首删除元素。
类型：
普通队列（FIFO Queue）
双端队列（Deque）
优先队列（Priority Queue）
应用场景：任务调度、广度优先搜索（BFS）。
5.哈希表 (Hash Table)：
特点：通过哈希函数将关键字映射到数组下标，提供O(1)的查找、插入和删除效率。
应用场景：快速查找和去重操作，如字典、缓存实现。
6.树 (Tree)：
特点：层次结构，根节点、叶节点和非叶节点。
常见类型：
二叉树（Binary Tree）
二叉搜索树（Binary Search Tree，BST）
平衡树（如AVL树、红黑树）
堆（Heap）——用于实现优先队列
Trie（字典树）
应用场景：查找、排序、范围查询、表达式解析。
7.图 (Graph)：
特点：由顶点和边组成，顶点之间通过边连接，图可以是有向或无向的。
表示方法：
邻接矩阵（Adjacency Matrix）
邻接表（Adjacency List）
算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最短路径算法（Dijkstra、Floyd）、最小生成树（Kruskal、Prim）。
应用场景：社交网络、地图导航、网络通信等。
二、常见算法
1.排序算法：
冒泡排序 (Bubble Sort)：O(n²)
选择排序 (Selection Sort)：O(n²)
插入排序 (Insertion Sort)：O(n²)
归并排序 (Merge Sort)：O(n log n)
快速排序 (Quick Sort)：平均O(n log n)，最坏O(n²)
堆排序 (Heap Sort)：O(n log n)
2.查找算法：
线性查找 (Linear Search)：O(n)
二分查找 (Binary Search)：O(log n)，适用于已排序数组
插值查找 (Interpolation Search)：O(log log n)（数据均匀分布时）
3.分治算法 (Divide and Conquer)：
核心思想：将问题分解为规模更小的子问题，递归求解，再合并子问题的解。
应用：归并排序、快速排序、二分查找、矩阵乘法。
4.动态规划 (Dynamic Programming, DP)：
核心思想：通过将问题拆解成多个子问题，存储子问题的结果，避免重复计算。
常见问题：斐波那契数列、最长公共子序列（LCS）、背包问题、编辑距离。
时间复杂度：通常为O(n²)或更优。
5.贪心算法 (Greedy Algorithm)：
核心思想：每一步都选择当前状态下的最优解，期望得到全局最优解。
常见问题：最小生成树（MST）、活动选择问题、最短路径问题（Dijkstra算法）。
6.回溯算法 (Backtracking)：
核心思想：逐步构建解，遇到冲突时回退，尝试其他可能性。
常见问题：数独、八皇后、子集和问题。
7.分支限界 (Branch and Bound)：
核心思想：在解空间中探索可能的解，同时利用已知约束（界限）排除不可能的解。
常见问题：旅行商问题（TSP）、0-1背包问题。
8.图算法：
DFS和BFS：遍历图，寻找路径、连通性。
Dijkstra算法：单源最短路径，适用于正权图。
Floyd-Warshall算法：多源最短路径。
Kruskal和Prim算法：求最小生成树。
三、算法分析
1.时间复杂度 (Time Complexity)：
表示算法的执行时间随输入规模的变化情况，常用的渐进表示法包括：O(1)、O(log n)、O(n)、O(n log n)、O(n²)等。
2.空间复杂度 (Space Complexity)：
表示算法在运行过程中所需的额外内存空间。
3.常用的渐进记号：
大O记号（O-notation）：表示算法的上界。
大Ω记号（Ω-notation）：表示算法的下界。
大Θ记号（Θ-notation）：表示算法的准确界。
四、其他重要概念
1.递归 (Recursion)：
特点：函数直接或间接调用自身。
应用：分治法、树的遍历、回溯算法等。
2.迭代 (Iteration)：
特点：通过循环实现重复计算，与递归相比，通常更节省内存。
3.空间时间权衡 (Time-Space Tradeoff)：
一些算法在优化时间复杂度的同时可能会消耗更多的内存，反之亦然。例如，通过哈希表加快查找速度，代价是增加内存使用。
总结
数据结构决定了数据的存储方式和操作方式，算法决定了如何有效地操作这些数据。
常见的数据结构包括数组、链表、栈、队列、树、图、哈希表等，不同的结构适用于不同的场景。
算法则主要包括排序、查找、动态规划、贪心、图算法等，通过分析算法的时间和空间复杂度，选择合适的算法解决问题。