数据结构笔记——数据结构与时间复杂度

一、数据结构与算法复杂度基础本节分为两大模块数据结构存在的意义、算法效率评判标准时间复杂度 大 O 表示法。1. 数据结构的存在意义1核心作用解决大规模数据管理问题类比图书馆书籍分类 无规则乱序存放书籍找书需要一本一本遍历分类编号存放后可快速定位。 数据结构同理对海量数据做规范化存储组织优化查找、插入、删除、修改操作效率。2适用场景边界数据结构性能差距只体现在大规模数据场景海量磁盘数据、百万级内存数据 少量数据仅 10 条以内计算机硬件性能充足不同数据结构的效率差异可以忽略。2. 算法效率评估标准时间复杂度1时间复杂度定义不依赖电脑 CPU、内存等硬件性能抛弃 “实际运行毫秒数” 以代码执行次数为衡量标准描述算法执行耗时随数据量n增长的变化趋势。2大 O 表示法复杂度分析核心规则只保留函数最高阶项直接忽略常数、低次项常数项全部删掉如2n100→ 只保留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 变形得2kn转换对数 klog2​n 循环执行次数等于k因此时间复杂度O(log n)2. 平衡二叉树查找 O (log n) 推导满二叉树规律第 k 层最多存放 2k−1 个节点 整棵树总节点总数 n2k−1 数据量大时常数 1 可忽略简化为 n≈2k 变形klog2​n 查找最多遍历树的全部层数 k因此复杂度O(log n)