# 1. 为什么需要逼近算法？ # 1.1 计算难度：NP-Hard 很多现实中的优化问题都是 NP-hard，即没有已知的多项式时间算法。 例如：Euclidean TSP（旅行商问题）、Quadratic Assignment（二次指派问题）等。 这些问题只能在小规模实例上通过精确算法解决。 # 1.2 运算成本高 即使问题不是 NP-hard，在高维空间或大规模数据下，精确算法也往往太慢。 举例： 2D 最小生成树：O(nlog⁡n)O(n \log n)O(nlogn) 高维 kkkD 最小生成树：O(n2)O(n^2)O(n2) 使用逼近算法可将其降至...

# 1. 问题定义：什么是 Planar Point Location？ 目标：给定一个平面细分（由线段将平面划分成多个不重叠区域），我们希望预处理它，使得对于任意查询点 qqq，可以快速判断它位于哪个区域（face）中。 输入：包含 nnn 条边的平面细分 SSS。 查询：给定一个点 qqq，返回包含它的面。 # 2. 第一种方法：暴力线性扫描 思路：遍历所有面，检查查询点 qqq 是否落在其中。 做法： 对每个面进行点在多边形内的判断（如射线法或环绕数方法）。 时间复杂度： 每个面 O(k)O(k)O(k)，总共...

# 1. 点线对偶（Point-Line Duality） 点线对偶是计算几何中的一种基本变换思想，它允许我们在平面上将点与线互相转换，并在保持几何关系的前提下，从不同的角度简化问题。 # 1.1 什么是点线对偶 点线对偶（也称为几何对偶）是一种函数或映射，将平面中的一个几何对象（如点）转换为另一种对象（如直线），并且可以保持或反映其之间的几何关系，如： 点与直线的交关系； 点在线的上下方位置关系； 共线性、共点性等结构性质。 这种变换是一一对应的，即每个点对应唯一的一条线，反之亦然（在限定条件下）。 # 1.2...

# 决策树 1234567891. SELECT DISTINCT store_id FROM Tx WHERE month = 5;2. SELECT DISTINCT c.name FROM Tx t JOIN Tx_Cakes tc ON t.tx_id = tc.tx_idJOIN Cake c ON tc.cake_id = c.cake_id WHERE t.month = 5;3. SELECT t.month,SUM(t.value) AS total_value,AVG(t.value) AS avg_value,COUNT(tc.cake_id) AS...

# Voronoi 图复杂度的欧拉公式证明 我们希望证明：对于 n>2n > 2n>2 个点的 Voronoi 图 V(P)V(P)V(P)，其复杂度是线性的： 顶点数 ≤2n−5\leq 2n - 5≤2n−5 边数 ≤3n−6\leq 3n - 6≤3n−6 # 📐 使用欧拉公式 欧拉公式是平面图中的基本定理： V−E+F=2V - E + F = 2 V−E+F=2 其中： VVV 是顶点数 EEE 是边数 FFF 是面数（Voronoi cell 数量，即原始点数 nnn） # 🔧 添加虚拟点使图封闭 由于...

# Lecture 9: Streaming and Sketching II - 内容总结 # Part1 引入流式算法以及解决方案 # 🧩 课程引入：流式算法的挑战 数据以流的形式连续到达，不能全部存储。 算法 A 读取前一部分数据后输出结果 21.5 。 结果还没来得及用，更多的数据又到达了。 再运行 A 得到新的结果 18.1 。 关键问题： 如何把两个结果合并成一个整体答案？ # 🧠 引入 Sketching 的概念 对每段数据 σ ，算法 A 生成一个摘要： S(σ) ，称为 sketch。 特性： S(σ) 是对数据的压缩表示； 可以从 S(σ)...

# 一、机器学习及分类 # 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...