Yuchen You

随机变量 Random Variable (RV) 一个变量，可以被赋予一个 sample space 中的值，常常用 XXX 表示 可以被分为 连续的或者 离散的（也可能是混合） 离散 表示可能的值是有限的或者 countable 的 分布 distribution 表示选中的值随着概率的变化 概率质量函数 probability mass function (pmf) 离散变量的独有特性，符号一般为 p, 公式 p(x)=P(X=x)p(x) = P(X = x) p(x)=P(X=x) 性质 ∑p(x)=1\sum p(x) = 1∑p(x)=1 p(x)≥0p(x) \ge 0p(x)≥0 累计分布函数 cumulative distribution function (cdf) 可以是离散或者连续变量的函数，符号 FFF, 表示小于等于 xxx 值的可能性积累量 F(x)=P(X≤x)F(x) = P(X \le x) F(x)=P(X≤x) 离散的cdf 是一个 step function 均值 mean 一般用 μ\muμ 表示 population mean, 用 ...

尾递归 Tail Recursion 我们称递归调用在函数最后一步的递归方式为 尾递归 例如我们在计算阶乘的时候，如果我们这样写： 1234def factorial(n, acc=1): if n == 0: return acc return factorial(n-1, acc*n) 那么调用自身的步骤在最后，就是尾递归，这种递归形式由于和 正向递推没有很大的区别，有一些编译器会将其变成 iteration 的形式进行执行，从而避免 stack-overflow 的问题，其占用的时间和空间都会比一般的递归小很多 递归与压栈操作 在函数被调用的时候，我们称一个本地变量存储在名为 program stack 的栈结构中 在调用函数之后，其arguments 会被 push onto program stack 在函数执行完之后，arguments 就会被 pop 出栈 在函数中执行 return, 返回值会被push 到 prog stack 中 如果 return 的值被收到，那么返回值会被 pop 走，且本地变量会被重新存储 函数栈可以被嵌套 (nes ...

时间的测量 1234567891011#include <chrono>int main(){ Timer t; t.start(); t.stop(); cout << t.seconds() << endl; t.reset(); t.start(); t.stop();} 但是多次查看系统时间会导致程序明显变慢 常用的工具 profiling tools perf 指令会显示某些节点花费的时间、cpu占用等性能 或者在linux 下，可以考虑使用 time prog 指令，该指令会在命令行输出一行 后面的prog 内容加上 各个部分占用的时间以及cpu占用量 11.60s user 0.03s system 95% cpu 1.711 total user: 程序占用时间 system: 系统执行该程序使用的额外时间 elapsed: 从开始打表到结束打表所经过的时间差，会包含期间其他进程占用的时间 cpu: 程序的 cpu 占用量，计算公式 user+system/elapseduser + system / elaps ...

在分治算法中，我们已经知道要将一个问题分裂成不同的子问题来解决，但是，如果有些时候子问题之间存在覆盖问题，那么再利用 分治算法得到的时间复杂度就会非常大，所以，我们往往使用制表法来解决这个问题，中文名“动态规划”。 动态规划的解 （ OP, optimal）往往有很多个, 但是我们会用 value 进行标注这个 解，即我们可以通过比较 value 来找到最优解 (OTV, optimal value)。 从斐波那契讲起 如果我们要求解斐波那契数列中第 n 个数，那么我们可以用递归 (Top-Down) 的方法： 123456def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) 但是这个方法的时间复杂度是 O(2n)O(2^n)O(2n)，时间表达式 T(n)=T(n−1)+T(n−2)+O(1)T(n) = T(n-1) + T(n -2)+ O(1)T(n)=T(n−1)+T(n−2)+O(1) 因为我们会重复计算很多次 fib(n- ...

分治思想 将一个输入变成多个 sub-inputs 将一个 subinput 通过递归找到子解决方法 结合 (combine, or conquer) 子解决方法得到最终解决方法 归并排序 将一个线性数组分割成两个等长的数组，长度 n/2 对左右子数组分别执行归并排序（递归）复杂度 将左右数组进行合并， 复杂度 O(n)O(n)O(n) 递归部分复杂度分析 首先我们明确这是一个类似二叉树的结构，所以，从层数上来讲，一共有 log⁡2n\log_2 nlog2​n 层，每一层的复杂度是 O(n)O(n)O(n) (每一层都有合并)，所以递归部分的复杂度是 O(nlog⁡n)O(n \log n)O(nlogn) 注意区分一般的二叉遍历 比如对分查找，我们想找到有序数组中最靠近 k 的位置，那么用对分查找，相比归并排序少了一个合并 (O(n)) 的步骤，时间复杂度是 O(log⁡n)O(\log n)O(logn) 又或者是将一个数不断的用 ⌊x/2⌋\lfloor x/2\rfloor⌊x/2⌋ 和 x−⌊x/2⌋x - \lfloor x / 2\rfloorx−⌊x/2⌋ 来 ...

基本概念 population: 一个实验中所有数据的综合 sample: population 的一个子集，包含了一些已经被观察过的元素 outlier: 一个样本中与其他数据相差较大的数据 简单随机样本 SRS 尺寸为 n 是一个每个元素都相同可能性下被挑选出来的sample 常见计算公式 样本均值 sample mean 即样本的平均值 xˉ=∑i=1nxin\bar{x} = \frac{\sum_{i=1}^{n} x_i}{n} xˉ=n∑i=1n​xi​​ 偏差 deviation 一个样本值到平均值的距离 xi−xˉx_i - \bar{x} xi​−xˉ 样本方差 sample variance 样本值到平均值的距离的平方和 s2=∑i=1n(xi−xˉ)2n−1s^2 = \frac{\sum_{i=1}^{n} (x_i - \bar{x})^2}{n-1} s2=n−1∑i=1n​(xi​−xˉ)2​ 为什么是 n - 1? slides 上说实测效果更好，用 n 作为分母会 underestimate the population variance ...

位操作 Bit Manipulation 如果我们要将一个十六进制数 0x2020 取出从低到高第二位的值，我们最直接的方法就是使用 mask, 即 12a = 0x2020;a = a & 0x00F0; 如果要将这几位输出，我们就要 a = a >> 4; 就可以将数据向右 bit shift 4 位，然后我们就可以得到 0x0002 的值 为什么不能用 (a << 8) >> 12? 对于向右位移，我们可能会将超过长度的内容赋值 0, 但是向左位移则不是这样，向左的位移会被认为是 直接扩大数字 如果是 int 数据类型向左位移 100 位，这个等价于 << 100 % 32 因为 int 长 4 字节 32 位，编译器会将这一步截断到 4 位从而不为 0 编译器对于补码的理解 如果输入的数字是一个负数，对其进行 >> 操作得到的结果会和正数情况下不同，编译器会按照补码与否来进行操作，如果是 负数，就会填充 F; 如果是 正数，就会填充 0，因此如果要用循环来进行位提取，负数的终点是 0xFF⋯0\text{x}F ...

三门问题 游戏规则 有三个门，只有一个门后面有车，另外两扇门后面是羊，主持人知道哪扇门后面是车或者羊，参赛者不知道。参赛者先选择一扇门，然后主持人打开一扇门，露出一只羊。参赛者可以选择是否换门，然后打开最终选择的门，如果是车则获胜。 问题 参赛者是否应该换门？ 解答 如果不改变决策，那么我们看不看到新的信息对于结果没有影响，所以中奖的概率是 1/31/31/3 如果改变决策，我们就会有几种可能 枚举之后，我们会发现在三种情况中，有两种情况是中奖的，所以中奖的概率是 2/32/32/3 因此我们应该换门 解释 在不知道条件之前，我们选中车的概率是 1/3, 但是在打开一扇门之后，其实我们换门如果成功说明本来就是羊, 这个概率是 2/3 这个例子说明了 信息的获取是可以改变概率空间的结果的 条件约束 Condition 很多随机事件的发生是需要一定条件作为背景的，比如我们讨论 eStar 作为A2获得夏季赛总冠军的概率和 eStar 在夏季赛决赛中获得总冠军的概率必然是不同的，后者多了一个条件: eStar 进入到夏季赛决赛 我们令事件 A:=A: =A:= eStar 获得夏季赛总冠 ...

getopt家族: 命令行解码 getopt 能处理短选项，即那些以单个短划线开头的单字符选项（例如 -a 或 -b） 使用一个字符串来定义所有有效的选项，其中每个有效的选项字符后面可以跟随一个冒号（:）来表示该选项需要一个参数 所需参数 argc argv optstring: 用一个字符串来描述每个flag是否需要额外参数 : 表示必须要额外参数 :: 表示额外参数可选 使用与返回值 一般我们用 while 进行判断是否完成读取，即 while ((opt = getopt(argc, argv, "ab:c:")) != -1) 从这里我们可以看出，getopt 函数返回一个 int，这个值是当前选项的 ASCII 码值，如果没有选项了，就返回 -1；且后续往往接一个 switch 语句，根据返回值进行不同的操作 对于额外输入的参数 会有一个全局变量optarg 进行标记, 当然如果是可选的参数，不输入会得到 optarg 指向 NULL 空地址；但是输入的参数是 char* 形式，我们如果要转换成string，需要 string arg
...