Ofnoname

摘要： 动态数组扩容问题是均摊复杂度分析最经典的应用： 动态数组的尾插 push_back，有时会触发扩容； 一旦扩容，就要申请更大的内存、搬运旧元素、再插入新元素。某一次操作的代价完全可能是 \(O(n)\) 但是，动态数组尾插的复杂度是均摊 \(O(1)\) 类似的现象其实非常多：单看某一次操作，它们都 阅读全文

摘要： 之前我们讲了主定理，用来解决： \( T(n)=aT(n/b)+f(n) \) 的复杂度 但现实里的递归，往往没有这么整齐。比如每个子问题的规模不同： \[T(n)=T(n/2)+T(n/3)+n \]这时候，主定理就不能直接用了。这篇我们讲一个更强的工具：Akra–Bazzi 定理。 主定理的扩展 阅读全文

摘要： “求数组中第 k 大的元素”是一个非常经典的问题。 最直接的做法是先排序，再取排序后的第 k 个元素。但排序的时间复杂度是 O(n log n)。能不能做到 O(n)？ 问题定义 给定一个长度为 n 的数组 nums，求其中第 k 大的元素。 例如： nums = [3, 2, 1, 5, 6, 4 阅读全文

摘要： 很多人第一次接触动态规划，都是从“走格子”开始的：在一个二维网格上，从起点走到终点，每次只能做有限几种移动，问方案数、最小代价，或者最大收益。 第一题：最小路径和 给定一个 \(n \times m\) 的非负整数网格 \(a\)，从左上角出发走到右下角，每次只能向右或向下走一步，路径上的数字都要累 阅读全文

摘要： “五个海盗，100 枚金币，怎么分才能让自己活下来，还拿到最多的钱？” 作为最流行的博弈论题目之一，这道题存在多种规则： 投票门槛怎么定：过半就行，还是必须严格多数？ 海盗的偏好顺序是什么：先保命，再要钱，最后是喜欢杀人，还是讨厌死人？ 经典版：半数及以上通过 这是流传最广的版本，也是大家最熟悉的 阅读全文

摘要： 在东汉的数学著作《数术记遗》中，“兆”就已经作为大数单位出现了。但有趣的是，当时并存着三种完全不同的进位体系： 体系 进位规则 “兆”的具体数值 下数 十进（十万为亿，十亿为兆） 10⁶（一百万） 中数 万进（万万为亿，万万亿为兆） 10¹²（一万亿） 上数 自乘（亿亿为兆） 10¹⁶（一亿亿） “ 阅读全文

摘要： 第一次学算法时，大多数人都会觉得课本里的定义有点“严格过头”： 为什么一定要有有限条指令？ 为什么一定要求对每个输入都终止？ 难道一个“很像算法”的过程，只要偶尔不结束，就不算算法了吗？最短路，并查集，排序，难道还有终止不了的算法？ 其实，这些要求不是为了咬文嚼字，而是为了把“算法”这个概念和一般的 阅读全文

摘要： 为什么有的课程叫“算法”，有的叫“数据结构”，还有的干脆叫“算法与数据结构”？ 如果只看名字，它们像是三门不同的课。但学着学着你就会发现，这几个词几乎总是一起出现。学排序时会碰到数组、堆、树；学图论时会碰到队列、优先队列、并查集；做题时更常常不是单独考“会不会某个算法”，而是考你能不能选对数据结构， 阅读全文

摘要： 这篇文章不谈价格涨跌和投资讨论。只做一件事：把比特币的基本原理讲清楚。读完你应该能看懂区块浏览器里一笔交易的“输入/输出”，能理解为什么在没有银行的情况下，比特币也能维护余额和支付。 需要的前置知识不多，你只需要了解三件基础概念即可：公钥/私钥与数字签名（私钥像“签名章”，用来证明你有权花钱）、哈希 阅读全文

摘要： 在终端里跑脚本的可能写法： ./main.sh source main.sh（或 . main.sh） bash main.sh / sh main.sh 甚至 exec ./main.sh、nohup ./main.sh & 它们看起来都“能跑”，但性质上有差异。讲清楚避免经典踩坑。 差异的核心只 阅读全文