Stanley's Blog

渐近符号总结 在学习算法的时候，一个很重要的部分就是复杂度分析，或者说是叫做渐进分析，本文简单总结了相应的符号的意思。 1. Big O - O(g(n))O(g(n))O(g(n)) - 上界 (Upper Bound) 定义: f(n)=O(g(n))f(n) = O(g(n))f(n)=O(g(n)) 当且仅当存在常数 c>0c > 0c>0 和 n0n_0n0​，使得对于所有 n≥n0n \geq n_0n≥n0​： f(n)≤c⋅g(n)f(n) \leq c \cdot g(n) f(n)≤c⋅g(n) 含义: f(n)f(n)f(n) 的增长不会超过 g(n)g(n)g(n)（最坏情况） 例子: 3n2+5n=O(n2)3n^2 + 5n = O(n^2)3n2+5n=O(n2)，也可以说 =O(n3)= O(n^3)=O(n3)（但不够紧） 2. Big Omega - Ω(g(n))\Omega(g(n))Ω(g(n)) - 下界 (Lower Bound) 定义: f(n)=Ω(g(n))f(n) =...

本文讲解简单讲解一下 Amortized Analysis 里的 Accounting Method。 1. 基本概念 均摊分析关注的是**一系列操作（Sequence of operations）**的总成本，而不是单次操作的最坏情况。 直觉 (Intuition)：将运行时间类比为金钱（Credits），即 Time = Money。 核心思想 (Key Idea)： 廉价操作：支付高于实际成本的费用，将多余部分存入“口袋（Pocket/Credits）”中。 昂贵操作：利用之前存储的信用额度（Credits）来支付其高昂的实际成本，而不需要额外拨款。 2. 记账逻辑：银行与口袋 在记账法中，我们通过设定“均摊成本（Amortized Cost/Bank Loan）”来平衡预算。 概念 含义 作用 实际成本 (Actual Cost) 算法操作真正消耗的时间。 真实支出的钱。 均摊成本 (Bank Loan) 我们为每次操作预设的固定预算。 我们的“最坏打算”，用来覆盖昂贵操作。 存款...

你是否曾遇到过两个函数相乘，然后需要对它们积分的难题？当你发现熟悉的 u-substitution 换元法无能为力时，千万不要灰心。今天，我们将一起深入探讨微积分中一个极其强大的工具——分部积分法 (Integration by Parts)。 Integration by Parts 可以说是一个非常非常常用的 trick，但是他又相对来讲比较复杂，比如说我就经常性会忘记。本篇指南将带你从最核心的公式与思想出发，掌握选择 u 和 dv 的黄金法则，最后再介绍一个能极大提升计算速度的“表格法”技巧。不管是从头学起，还是回顾一下风尘已久的记忆，这篇 Blog 都非常合适。让我们开始吧！ 核心思想与公式推导 分部积分法的本质，其实就是微分乘法法则 (Product Rule) 的逆运算。它的目标很明确：将一个棘手的积分，通过一次“变换”，转换成一个我们更容易解决的积分。 公式 它的标准形式简洁而优美： ∫u dv=uv−∫v du\begin{equation} \int u \, dv = uv - \int v \,...

在处理离散型随机变量（尤其是马尔可夫链中的“首达时间”、“等待步数”等非负整数变量）时，我们经常会遇到一个痛点：精确计算某件事在“恰好第 kkk 步”发生的概率 P(T=k)P(T=k)P(T=k) 极其困难，但计算这件事“撑过第 nnn 步还没发生”的概率 P(T>n)P(T>n)P(T>n) 却非常容易。 这时候，概率论中一个极其优美的公式就派上用场了——尾概率求和公式 (Tail Sum Formula)，或者形象地称之为千层饼表示法 (Layer Cake Representation)。 核心公式 对于任意取值为非负整数的随机变量 TTT（即 T∈{0,1,2,… }T \in \{0, 1, 2, \dots\}T∈{0,1,2,…}），其期望值 E[T]\mathbb{E}[T]E[T] 可以表示为所有“尾概率”的无穷级数求和： E[T]=∑n=0∞P(T>n)\mathbb{E}[T] = \sum_{n=0}^{\infty} P(T >...

这个 blog 来讲一下克拉默-拉奥下限（Cramér-Rao Lower Bound, CRLB），主要是根据《Mathematical Statistics and Data Analysis, 3rd Ed.》中的内容做的整理。 1. 核心思想与目的 在统计学中，我们常常有多种方法来估计同一个未知参数 θ\thetaθ。CRLB 为我们提供了一个客观的基准来判断哪种估计方法更好。它的核心思想是，对于任何无偏估计量 (unbiased estimator)，其方差不可能无限小，它必须大于或等于一个特定的理论最小值。这个最小值就是克拉默-拉奥下限。 主要作用： 提供一个 benchmark：我们可以将不同无偏估计量的方差与这个下限进行比较。 定义“最优”估计量：如果一个无偏估计量的方差能够达到这个下限，我们就称它为有效估计量 (efficient estimator)，这意味着在所有无偏估计中，没有比它更精确的了。 2. 克拉默-拉奥不等式 (Cramér-Rao Inequality) 书中第 8.7 节的定理 A 给出了这个不等式的正式表述。 假设...

可以说是非常夸张，运气非常好了，timeline 如下： 2026.1.15 开始背单词的第一天 2026.2.5 开始看填空的第一天，大概看网课+做题 2 h 2026.2.6 学习填空的第二天，大概看网课+做题 2 h 2026.2.7 滑雪 8 h，40 道数学（老版一套），1.5 h 2026.2.8 滑雪 8 h，开始学习阅读，大概学了 1.5 h 2026.2.9 继续学习阅读，大概 2 h 2026.2.10 继续学习阅读，大概 2 h 2026.2.11 继续学习阅读，大概 3 h 2026.2.12 继续学习阅读，大概 2 h 2026.2.13 刷题 1.5h verbal，1.5h 数学，0.5 h 写作 2026.2.14 0.5 h 写作，考试 2026.2.22 出分 总结：我大概背单词花了 30 h，其他的看课做题花了 20 h，一共 50 小时，满打满算也只算是真正备考了 9 天，还是不脱产，我要在同时赶很多作业（19 学分 overload 的含金量）。真的没想到分数能这么高，远超预期，只能说真的纯靠运气了。

CS 537 ESL 117 STAT 305 STAT 310 STAT 424 STAT 453

这里就是最后一部分啦～，persistence，讲了一些像什么 I/O devices，然后什么 file system，distributed system 这种东西。 Chapter 36: I/O Devices 这一部分首先讲的是 I/O devices，which is a very important part of computers。 三种 bus：memory bus，general I/O bus 和 peripheral I/O bus。 不过上面这个并不是真的现代计算机系统的架构，一个真的现在计算机的系统架构大概会像 Figure 36.2。 现在我们讲一讲 canonical device。意思就是所有 devices 的抽象，所有 devices 都要有以下的 feature。 所有的 device 都需要提够接口，也就是 interface，这样我们的系统，或者其他组件才能够“用”这个硬件。 其次所有的 device 都有其内部结构，这个就大家各不相同了，只要你提供了好的 abstraction，好的...

今天已经是 12.5 号了，最近可以说是非常非常之忙碌，一堆 final project 没做，还有很多课马上考试还没复习，以及一堆的申请 DDL，以及 PhD 的面试。不过这两天感觉终于可以喘口气了，因为所有的期末考试前的 interview 都面完了，然后现在也不想学习，所以就来写一个 26 Fall graduate school 的小总结吧。 Background 因为现在还在申请，有点担心掉马甲，所以我就非常模糊的说一下我的 bg。 985 中外合办，国内 GPA: 3.94/4.0 (ranking: 10/110)，国外 GPA: 3.96/4.0 (国外大学没有 ranking 这一套，不过 3.96 我个人感觉也算是比较高了)。 有一段 internship (个人感觉没用)，以及一段科研（有一篇一作 paper 产出，但是 under review）。 所以其实我的 bg 绝对不算强，经常刷到什么本科好几篇顶会的同学，或者 3、5 段实习/科研经历，我只能甘拜下风。 Which schools did I choose? 因为我自觉我的 bg...