# 一、机器学习及分类 # 1.1🔍 机器学习任务分类（Machine Learning Problems） Prediction（预测） 包括分类（Classification）和回归（Regression）, 是一种有监督学习 ✅ 例子： 分类问题（Classification）： 判断一封邮件是不是垃圾邮件（标签：垃圾 vs 正常） 预测一个肿瘤是良性还是恶性（标签：良性 / 恶性） 回归问题（Regression）： 根据房屋面积、地段等预测房价（标签是一个连续数值） Clustering / Segmentation / Association Rules（聚类 /...

# 生日悖论 # 🌟 问题设定 有 m 个人，每个人的生日是等概率地在 1 到 365 天之间。问：至少有两个人生日相同的概率是多少？ 我们设： n=365（即一年 365 天） m 是房间里的人数 p (m,n)：至少两人生日相同的概率 # 🧮 如何计算这个概率？ 我们可以通过 ** 反向思考（补集法）** 来计算。 # 1. 计算 “没有人生日相同” 的概率（记为 q (m,n)） 即，每个人的生日都不重复。 假设第一个人随便选生日（有 365 种选法）， 第二个人必须选一个 不一样的（有 364 个选择）， 第三个人有 363 个可选…… 直到第 m 个人，有...

# 🧪 一、统计研究类型以及一些概念 # 1. 研究的类型 观察性研究（Observational Study） 被动观察，不控制变量。 只能揭示相关性，不能说明因果。 例子：晒黑设备与皮肤癌、使用电脑时间与血压 简单的观察发生了什么，记录受试者的信息，不对受试者进行任何操作。 实验性研究（Experimental Study） 主动施加处理（treatment），设置对照组。 可以探究因果关系。 例子：限制计算机时间组 vs...

# 1. 线性规划基础 可以根据条件列出一个不等式区间，然后根据目标函数来判断极值位于哪里 比如 lec 中的例题 目标函数：最大化形式 f (x,y)=200,000x+250,000yf (x, y) = 200,000x + 250,000yf (x,y)=200,000x+250,000y。 约束条件来自资源限制（如砖块、门、窗）： 10,000x+8,000y≤168,000 4x+2y≤60 5x+10y≤150 x≥0,y≥0 示意图： 这个点通过平移 k=-0.8...

# 一、多边形的三角剖分（Polygon Triangulation） # 1. 算法 1 row123while 多边形 P 尚未被完全三角剖分: 找到一条有效对角线 (x,y) 输出对角线 (x,y) # 📌算法复杂度分析： 算法复杂度从以下三个方面分析： 对角线数量（Number of potential diagonals）： 一个多边形有 n 个顶点，每对顶点都有可能构成对角线，所以潜在对角线最多为 O (n2) O (n^2) O (n2)。 检查一条潜在的对角线是否合法（Testing one potential...

首先，这一门课的两个重要方法：反证法和数学归纳法 这两个方法在后续的正确性证明当中使用的相当频繁 然后引入这门课的第一个问题：艺术画廊问题 即 一个艺术画廊中需要放多少个守卫才能监视到整个画廊 每个守卫的视野距离无限，角度 360 度 然后引入上界与下界： 上界我们可以首先松弛一点，即一开始的上界定为 n-2，n 为边数，因为我们可以以最差的角度来考虑，即把整个多边形分成 n-2 个三角形，并且每个三角形都放一个守卫 #...

# 📘 哈希函数的定义与作用 # ✅ 什么是哈希函数？ 哈希函数是一个 将输入值映射到固定大小的输出空间 的函数。 输入：任意数据（整数、字符串、对象等） 输出：通常是一个固定范围的整数（例如 0 到 m−1m - 1m−1） 记作： h : \mathcal{U} \rightarrow \ 其中 U 是输入的全集 # 🧰 用途 / 作用 哈希函数被用于实现： 应用 说明 哈希表 高效的数据结构，实现 dict / map 快速查找 期望时间复杂度 O...

# 重要知识点梳理 # 五种重要的分布 # 1. 二项分布（Binomial Distribution） 定义 适用于独立重复伯努利试验（每次试验只有成功或失败两种情况）。 统计成功次数。 参数 X∼Bin(n,p)$$其中： - n是试验次数。 - p是单次试验成功的概率。 P(X=k)=(nk)pk(1−p)n−k,k=0,1,2,…,nP(X = k) = \binom{n}{k} p^k (1-p)^{n-k}, \quad k =...

这一节主要是入门。首先老师举了一个例子，即抽牌的问题，在 52 张牌中，连续抽到两个同样花色的牌的概率。 而在概率之后，就引入了期望的概念。 E(X + Y) = E(X) + E(Y) 然后讨论了期望的线性与否，计算了抽牌的过程的期望 # 算法的最坏时间 如上图我们可以知道，有两种计算的逻辑 由于随机算法会在算法中添加一个随机量 r，然后第一种是分别输入不同的 x，每一个 x 结合随即量 r 取一个平均值，最后将最差的 x 作为最坏期望时间 而第二种算法则是在最坏的情况下，还要将 r 设定为最差的值，即差中之差，将随机算法当作固定的看待。 # 随机算法的分类 这个分类有两类 Monte...

# 一、 为什么关心集中性（Concentration） 通常我们只能知道一个随机过程的期望值（比如算法的平均运行时间），但这远远不够。 我们希望了解：“实际结果通常不会离期望太远”，这就是集中性的概念。 举个例子： 一个算法的期望运行时间是 5 秒，但它可能大多数时候运行 1 秒，偶尔运行 1 分钟。那这 “平均值” 就不能准确反映真实体验。 所以我们需要知道：“它会不会很容易偏离期望？偏离的概率有多大？” # 二、几种重要的集中不等式（Concentration Inequalities） # ✅ 1. Markov 不等式 # ✅...