数据结构前言

数据结构与算法左侧问题列表如何高效存储和管理数据如何快速检索数据如何对数据进行排序如何在最短时间内做出决策如何优化问题求解的效率如何应对动态数据和在线问题如何处理复杂关系和网络问题如何在内存受限的情况下进行计算……学科支撑左下方离散数学线性代数概率论与数理统计图论应用领域中下方Web 信息处理数据库图像处理人工智能右侧知识体系分支1. 数据的逻辑结构线性结构树形结构图状结构2. 数据的物理存储结构顺序存储链式存储索引存储散列存储3. 数据涉及到的算法查找算法排序算法插入删除分治算法动态规划贪心算法链式存储链式存储是一种将数据元素存储在不连续的内存空间中并通过指针链接每个元素来保持元素间逻辑关系的存储方式。链式存储结构不要求数据存储在连续的空间中这使得其在动态数据操作如频繁的插入和删除方面具有较高的灵活性。算法效率的度量时间复杂度定义时间复杂度随问题规模 n 的增大算法执行时间的增长率和f(n)的增长率相同。公式T(n)O(f(n))大 O 符号大 O 阶推导规则用常数 1 取代运行时间中的所有基本操作。在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是 1则去除与这个项目相乘的常数。得到的结果就是大 O 阶。示例代码 1Func2c运行void Func2(int N) { int count 0; for (int k 0; k 2 * N; k) { count; } int M 10; while (M--) { count; } printf(%d\n, count); }示例代码 2Func3c运行void Func3(int N, int M) { int count 0; for (int k 0; k M; k) { count; } for (int k 0; k N; k) { count; } printf(%d\n, count); }空间复杂度定义空间复杂度对一个算法在运行过程中临时占用存储空间大小的量度公式S(n)O(f(n))大 O 符号示例代码 1incrementCounterjavascript运行function incrementCounter(int n) { int counter 0; counter counter n; }下方标注O(1)示例代码 2copyArrayjavascript运行function copyArray(arr) { let newArr new Array(arr.length); for (let i 0; i arr.length; i) { newArr[i] arr[i]; } }