需要解决流式算法的问题，我们有两种思路，一种是乘法近似，一种是加法近似 ！[[Pasted image 20250614130820.png]] 接下来介绍第一个问题 # Majority 问题 这个问题需要解决的是，在一个流式输入的过程中，是否有哪个元素的出现次数 > m/2 或者是一个变量，比如 1/k 的 m 为了解决这个问题，我们可以用以下算法 Misra-Gries algorithm 这个算法的定义是，由于我们只有很小的一个空间用来存放数据，所以我们可以使用一种算法，例如我们只有 1/ε 的空间，所以，我们在每个元素流过时执行以下的操作： 1....

这一节主要是讲，比如有一个 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...