一、数据结构的作用对大规模数据进行合理的规划提高数据的增、删、查、改等操作效率。二、时间复杂度时间复杂度是衡量算法效率的核心指标用于描述操作次数随数据规模n增长的趋势。1. 基本概念设数据总量为xx是足够大的数据算法为了达到某个目的执行的核心操作次数为y时间复杂度用O()表示忽略常数项和低阶项看大头yaxb --→yx O(n)yax^2bxc --→yx^2 O(n^2)ya --→ y1 O(1)ylogax --→ylogx O(logn01、O(1)操作次数与n无关如数学公式计算02、O(n)操作次数与n成正比如遍历数组03、O(n²)操作次数与n的平方成正比如嵌套循环04、O(log n)操作次数随n增长呈对数级如每次缩小一半范围的二分查找。2.大小关系O(1)O(log n)O(n)O(n²)3.举例算法名称算法描述操作次数推导过程时间复杂度无序数组查找遍历数组逐个比对目标值。平均操作次数y ≈ n/2。O(n)等差数列求和算法1遍历累加循环n次。O(n)算法2利用求和公式直接计算。O(1)算法1y n → O(n)算法21次操作 → O(1)。O(n)、O(1)冒泡排序相邻元素两两比较大值后移小值往前走一轮结束最大的数据到达正确的位置。操作次数y (n-1) (n-2) ... 1 n(n-1)/2。O(n²)二分查找数据有序每次将查找范围减半左/右区间。操作次数第k轮后范围为n/2^k直到范围为1时k ≈ log₂n。O(log n)直接和数据总量有关 On例如数组的从前到后遍历k层循环 On^k循环减半 O(log n) 例如二分法每次减半4.降低时间复杂度优化方法描述时间复杂度优化过程适用场景与限制利用排序优化无序数组转化为有序数组后可使用二分查找等方法。排序O(n²) / O(n log n)查找O(log n)排序算法的选择冒泡排序、快速排序等以及后续查找操作适用于有序数组。数组下标直接访问通过数组下标直接获取数据。O(1)已知下标或数组中数据分布规律明确的场景。哈希算法与哈希表利用哈希算法构建哈希表进行查找。平均O(1)最坏O(n)快速查找需解决哈希冲突如拉链法当链表过长时性能会下降。三、常见数据结构详解1.哈希表哈希表是一种基于哈希函数实现的用于存储键值对的数据结构。其核心思想是通过哈希函数将键映射到表中的位置从而快速地插入和查找数据。基本原理①哈希函数将键转换为数组下标哈希值的函数。常见的哈希函数有除法取余、乘法取整等。②数组用于存储数据的底层结构。哈希函数计算出的哈希值直接决定了数据在数组中的存储位置。优势:通过 “左小右大” 的规则使查找操作可以快速缩小范围类似二分法思想。例如查找一个值时只需与当前节点比较若小则去左子树若大则去右子树无需遍历全部节点。2. 树和二叉树树都分为二叉树或者多叉树左边节点的值小于当前节点右边节点的值大于当前节点3. 有序二叉树特点左子树节点的值 当前节点的值右子树节点的值 当前节点的值。优势通过 “左小右大” 的规则使查找操作可以快速缩小范围类似二分法思想。例如查找一个值时只需与当前节点比较若小则去左子树若大则去右子树无需遍历全部节点。局限若插入数据有序如从小到大插入可能退化为链表左子树为空或右子树为空此时查找效率降为O(n)。4. 平衡二叉树定义在有序二叉树基础上左子树与右子树的高度差不超过1平衡调整当插入或删除数据导致不平衡时通过旋转操作LL、RR、LR、RL 四种类型恢复平衡左左 LL 型左子树的左子树过高向右旋转RR 型右子树的右子树过高向左旋转左右 LR/RL 型需先调整子树方向再整体旋转。时间复杂度稳定在O(log n)n为节点数因每次操作都能保证树的高度与log n成正比。缺点频繁的平衡检测和旋转操作会消耗额外性能适合对查询效率要求极高的场景。5. 2-3-4 树简化版本四阶闭树简介一种多路平衡查找树是平衡二叉树的扩展允许一个节点存储多个元素。特点节点可存储 2-4 个元素对应 2-3-4 个孩子所有叶子节点在同一层保证树的平衡插入、删除时通过分裂或合并节点维持平衡。二节点存一个数值分两个叉三节点存两个数值分三个叉四节点存三个数值分四个叉6. 红黑树最优二叉树核心特点保证近似平衡1、根节点永远为黑色2、叶子节点为黑色且值为null哨兵节点3、红色节点的子节点必为黑色避免连续红节点4、从根节点到任意叶子节点路径上的黑色节点数量相同“黑高” 一致。在红黑树里没有一条路径比其他路径超过了两倍最多两倍时间复杂度稳定在Ologn优势相比平衡二叉树红黑树通过 “近似平衡” 降低了维护成本旋转次数更少插入、删除效率更高是实际工程中应用最广的平衡树如 Java 的TreeMap、HashMap在链表长度超过 8 时转为红黑树。
