数据结构笔记——数据结构与时间复杂度
一、数据结构与算法复杂度基础
本节分为两大模块：数据结构存在的意义、算法效率评判标准（时间复杂度 + 大 O 表示法）。
1. 数据结构的存在意义
（1）核心作用：解决大规模数据管理问题
类比图书馆书籍分类： 无规则乱序存放书籍，找书需要一本一本遍历；分类编号存放后，可快速定位。 数据结构同理：对海量数据做规范化存储组织，优化查找、插入、删除、修改操作效率。
（2）适用场景边界
数据结构性能差距只体现在大规模数据场景（海量磁盘数据、百万级内存数据）； 少量数据（仅 10 条以内）计算机硬件性能充足，不同数据结构的效率差异可以忽略。
2. 算法效率评估标准：时间复杂度
（1）时间复杂度定义
不依赖电脑 CPU、内存等硬件性能，抛弃 “实际运行毫秒数”； 以代码执行次数为衡量标准，描述算法执行耗时随数据量n增长的变化趋势。
（2）大 O 表示法（复杂度分析核心规则）
只保留函数最高阶项，直接忽略常数、低次项：
- 常数项全部删掉，如
2n+100→ 只保留n - 低阶项全部删掉，如
n²+3n→ 只保留n²
常见阶释义：
O(1)：常数阶，执行次数固定，和数据量无关O(log n)：对数阶，数据量翻倍，执行次数仅 + 1O(n)：线性阶，数据量扩大几倍，执行次数同步扩大几倍O(n²)：平方阶，数据量翻倍，耗时成倍暴涨
（3）复杂度优劣排序（效率从高到低）
O(1) > O(log n) > O(n) > O(n²)O(1)为最优复杂度，是开发中优先追求的性能标准。
二、核心数据结构查找操作时间复杂度汇总
1. 线性结构：数组 & 单链表
无序数组
无任何排序规则，查找目标只能从头遍历到尾，平均遍历一半元素
查找复杂度：
O(n)
有序数组
数据升序 / 降序排列，可使用二分查找，每次过滤一半数据
查找复杂度：
O(log n)
单链表
内存地址不连续，依靠指针串联节点； 无论链表是否有序，都必须从头节点逐个向后遍历，无法使用二分查找。
查找复杂度：
O(n)
2. 哈希表 HashTable
底层结构
数组 + 链表 / 红黑树结合；通过哈希函数（取模、哈希算法）把 key 映射为数组下标，理论上一步定位。
理想无冲突时存取复杂度：
O(1)
哈希冲突解决方案
不同 key 算出相同下标，产生冲突：
- 拉链法：下标位置挂载链表存放冲突数据
- JDK8 优化：链表长度超过阈值自动转为红黑树，保证冲突场景下查找效率稳定
O(log n)
3. 树形结构：二叉搜索树 & 平衡树
普通二叉搜索树 BST
规则：左子树全部小于根节点，右子树全部大于根节点。 树完全平衡时，查找层数为 logn
理想平衡：
O(log n)
缺陷：如果插入有序数据，二叉树会退化成单链，复杂度直接退化至O(n)。
平衡二叉树（AVL 树、红黑树）
通过左旋、右旋等平衡操作，强制维持树左右高度差稳定； 杜绝退化成链表的问题，增删查操作复杂度稳定O(log n)。
三、经典算法复杂度数学推导实例
1. 二分查找 O (log n) 推导
假设总数据量为n，每次二分后数据减半； 经过k次二分后剩余 1 个元素，公式： 2kn=1 变形得：2k=n，转换对数 k=log2n 循环执行次数等于k，因此时间复杂度：O(log n)
2. 平衡二叉树查找 O (log n) 推导
满二叉树规律：第 k 层最多存放 2k−1 个节点； 整棵树总节点总数： n=2k−1 数据量大时常数 1 可忽略，简化为 n≈2k 变形：k=log2n 查找最多遍历树的全部层数 k，因此复杂度：O(log n)