这一节主要是讲，比如有一个 99% 概率得到答案的随机算法，他会有一个 100% 成功的确定的 算法吗？ 有几种办法可以解决 1 PRNG 首先，这种方法是一种伪随机，例如摇一个骰子，他会伪装成骰子的结果，但是他并不是真的随机 2. 蛮力法 顾名思义，就是在随机元不是很多的时候，通过枚举所有的随即元的结果，来求到确定的结果 ！[[Pasted image 20250613204451.png]] 所以时间复杂度非常的高，这适用于所有的问题 那么类似于决策问题我们可以怎么做呢？ 我们可以用到之前提到过的概率放大方法，即通过多数投票和中位数法来代替这个过程

这一节着重讨论了线性规划的内容，并且通过线性规划重新讨论了第 5 节的 min-cut 问题。 首先讨论了普通的线性规划，然后提出了整数线性规划 由于有些问题，比如 0-1 背包问题，又或是 min-cut 问题，这些问题的参数并不能为连续的变量，只能是整数。但是由于 ILP (整数线性规划) 是一个 NP-hard 问题，有时候无法在多项式时间内求解，因此我们来讨论将 ILP 放松并界定的方式 比如说，我们将这个 min-cut 问题用 ILP 的方式列出来。 ![[Pasted image 20250613075501.png]] 但是他的求解是困难的，所以我们可以将他 relax 成...

引入概念：Global Minimum Cut 这节课我们需要解决的问题：在一个无向连通图中，我们想把这个图分成两个，要如何切断最少的边的数量完成这个行为 由于求解这个问题的复杂度较高，并且当我们使用常规算法时，面对粘稠图会非常的无力，所以说，我们可以放大一些范围，牺牲一些准确性来获得更高效的时间复杂度。 # Karger’s Contraction Algorithm 这个算法的原理就是，不断随机合并图上的一些点，直到只剩两个超级点，并且他们之间存在一堆线，这就是我们获得的...

# Voronoi Diagram 基础讲解 # 什么是 Voronoi Diagram? 给定一个点集 P={p1,p2,…,pn}P = \{p_1, p_2, \dots, p_n\}P={p1​,p2​,…,pn​}，Voronoi 图是将平面划分为 nnn 个区域（称为 Voronoi Cells），每个区域对应一个点 pip_ipi​，使得该区域中任意一点 qqq 满足： dist(q,pi)<dist(q,pj)∀j≠i\text{dist}(q, p_i) < \text{dist}(q, p_j)...

重点:kd-tree 和 range tree 首先，可以参考 ass2 的第一题，kd-tree 的绘制和 range-tree 的绘制。 其次，我们来一点点深入了解这几个知识点。 # kd-tree kd-tree 在后续的许多应用中都会有涉及。 首先，构建 kd-tree 需要 O (nlogn) 的构建时间和 O (n) 的构建空间 (具体推导过程可以去看 ppt) 🔹 方案一：使用排序方式找中位数 在每一层： 排序或选择中位点： O (n) 或 O (nlog⁡n)，具体取决于用排序还是选择算法。 划分左右子树： O(n) 递归调用左右子树： 每边是 n/2...

首先，讨论了一个现实问题，引入了线性规划相关的知识，即通过一系列的不等式规划出一个区域，然后将目标函数与目标区域的相交点结合，看哪个点最好 # 增量算法 可以首先添加一个简单的且很大的边界，然后将约束条件一次次加入这个区域中，如果最优点 v_i-1 仍然在最新的区域中，那么 v_i=v_i-1，否则重新计算 v_i 复杂度：O(n2)O(n^2)O(n2) 由于每一轮的遍历复杂度都为 O (i)，进行 n 个循环 这是最坏的情况，那么如果我们一开始就将最重要的两个限制加入，直接确定了最终的点 v，那么我们的复杂度会非常低，变成 O...

lec7 的内容主要在于 区分各种概念，例如机器学习，分类聚类等，然后有几个公式需要记，已经记在 cheatsheet 上了。 apriori 算法 通俗来讲，就是通过所有的频繁的组合都是由单一的频繁项来组成的。比如说，A,B,C,D 四个元素，首先构造一个 min_support , 然后进行迭代，先剪枝掉元素中 k< min_support 的元素，再对剩余元素进行排列组合，最终得到频率最高的组合。 Rule Generation 可以说是枚举法，对所有可能的组合都进行枚举，将组合的所有非空真子集列出来，并将这些候选进行区分。 Efficient Rule...

lec2 中学习的是如何把一个多边形切割开来；而这节课学习的就是，如何把一堆点给包起来 就像你在地上撒了一把钉子，然后用一根橡皮筋把它们围起来，拉紧之后那个形状就是 “凸包”。 所以，构造凸包的这个过程，我们还是从暴力解法开始 朴素暴力解法 我们可以假定一个结论：将点集 S 中的所有点遍历一遍，然后将这些三角形中包住的点都删除；最后剩余的这些没有被包围的点，一定是凸包的顶点。(作为三角形顶点或位于三角形边上的点不被删除) 那么我们就可以 #算法步骤（CH1）： 遍历 SSS 中所有可能的三元组 (x,y,z)(x, y, z)(x,y,z)：一共...

# 聚类（Clustering) # 一、聚类的概念 聚类是一种 无监督学习方法 目标是：将相似的数据点分在同一个 “簇”（cluster）中 没有预先的标签，完全基于数据之间的 “相似性” 划分 # 二、聚类的用途 文档分组、客户画像、基因数据分析、股票走势分群等 聚类可以帮助我们发现数据中的 “自然结构” # 三、相似性度量方法 用于计算两个数据点之间的 “相似程度”（或 “距离”）： 距离类型 定义 说明 曼哈顿距离（L1） ( d(i,j) = ∑\sum∑ x_i - x_j ) 抗异常值 欧几里得距离（L2） ( d(i,j)...