最新内容
文章与资讯，登录与否均可阅读
归并排序要额外空间：它为什么不是原地排序
每次合并需长度 O(n) 的辅助数组，总空间 Θ(n)，这是不原地的代价。
归并排序 O(n log n)：主定理情况 2 一步出
T(n)=2T(n/2)+Θ(n) 落在主定理情况 2，直接得到 Θ(n log n)，且最坏成立。
为什么归并排序稳定：相等键不换位
合并时相等取左侧，原序靠前的相等键先出，稳定性由此而来。
合并过程详解：双指针把两个有序数组合并
merge 的核心：双指针 i、j 每次取较小者写入结果，相等取左侧保证稳定。
归并排序递归树：分与合一眼看懂
用递归树拆解归并排序：每层代价恒为 n，叠 log₂n 层得 Θ(n log n)。
递归为什么会爆栈：主定理之外的工程现实
主定理只算"时间"，不算"栈"。深层递归每层都要压一个调用帧，过深就栈溢出。本文讲清递归 vs 迭代的栈代价，以及如何用尾递归/迭代改写规避。
分治思想：从归并排序到最近点对
分治不只会排序。最近点对、Strassen 矩阵乘法、FFT 都是"分解—解决—合并"的同一套骨架。本文用一张图说明分治为什么是算法设计的通用范式。
主定理管不到的情况：这些递推式别硬套
主定理只认"除法型" aT(n/b)+f(n)。减法型、根号型、临界处负指数（如 n/log n）都会让它失效。本文列三类典型，并给出正确解法。
三种解递推式的武器：递归树、代入法、主定理
分析递归式有三件套：递归树给直觉、代入法做严格证明、主定理是分治情形的速查。本文讲清三者如何配合，避免只会背公式。
二分查找与主定理：为什么 log n 是分治的标准答案
二分查找 20 行代码，复杂度却是 O(log n)。把它写成递推式 T(n)=T(n/2)+1，主定理情况2 一眼给出 Θ(log n)——分治把"线性扫描"压成了"对数查找"。
归并排序为什么稳：分治 + 合并的 O(n log n)
归并排序是最经典的分治：先分到底，再合并两个有序段。它稳定、最坏也是 O(n log n)，代价是多占 O(n) 额外空间。用递归树一看就懂。
为什么快排平均 O(n log n)：主定理情况3与随机化
快速排序最坏 O(n²)，但平均却是 O(n log n)。用主定理的"期望"视角 + 随机化基准，能说清为什么"平均"就是分治的标准答案。
主定理到底在算什么：递归树一眼看懂
主定理常被当成"背公式"，其实它只是递归树求和的速查版。本文用一张递归树讲清：把每层代价加起来，看哪一层主导总复杂度，三种情况自然浮现。
从跳表到内存池：链表思想的现代延展
链表不只是课本里的单/双/循环。它的"节点 + 指针"思想，衍生出跳表（Redis 有序集合）、内存池、邻接表等现代基础设施。今天把链表思想的上限拉到工业级。
哨兵节点（dummy head）：让链表代码干净一半的技巧
链表代码最烦人的就是"头节点要特殊处理"。哨兵节点（dummy head）——一个不存数据的假头——能把这个边界彻底抹平。今天讲清它为什么是工程必修课。
快慢指针：链表里的"龟兔赛跑"能解哪些题
让一个指针走两步、另一个走一步，这个简单的"龟兔赛跑"技巧，能判环、找中点、找倒数第 k 个节点。今天盘点快慢指针的几大经典用法，看它如何用 O(1) 空间办成大事。
链表反转：面试出现率最高的算法题，为什么
如果算法面试只能押一道链表题，十有八九是"反转链表"。它代码不过十行，却能把"指针走向"的功底考个底朝天。今天拆穿它为什么是试金石，以及如何一次写对。
循环链表与约瑟夫环：一个古老问题的现代解法
公元 1 世纪的犹太历史学家约瑟夫斯留下一道生死题：n 个人围成一圈，每数到 m 就出圈，最后谁活下来？今天用循环链表，把这道两千年前的题讲成一行优雅的代码。
双向链表如何撑起浏览器的前进后退
你每次点"后退""前进"，背后是一张双向链表在默默记录历史。今天用浏览器历史这个人人都用过的例子，讲清双向链表"正反都能走、且能 O(1) 自删"的独特价值。
LRU 缓存：链表与哈希的完美联姻
LRU（最近最少使用）是面试与工程的高频考点。它的优雅解法只用两种结构：哈希表负责"秒查"，双向链表负责"按访问顺序排布并能 O(1) 摘除"。今天拆开这个教科书级组合。