算法 相关数学内容 学习 2025年6月16日13:03:25
概率与统计
- 随机化
一种利用 随机性 来解决问题的方法，广泛应用于 算法设计、模拟实验、数据采样 等领域。它的核心思想是：通过引入随机性，降低问题复杂度或提高算法效率。
1. 随机化基本概念
随机变量（Random Variable）
定义：表示随机试验结果的变量（如掷骰子的点数 X∈{1,2,3,4,5,6}X∈{1,2,3,4,5,6})。
分类：
离散型（如二项分布、泊松分布）。
连续型（如正态分布、均匀分布）。
期望（Expectation）
定义：随机变量的长期平均值，记作 E[X]E[X]。
线性性质：
E[aX+bY]=aE[X]+bE[Y]E[aX+bY]=aE[X]+bE[Y]方差（Variance）
定义：衡量随机变量的波动程度，记作 Var(X)=E[(X−E[X])2]Var(X)=E[(X−E[X])2]。
计算：
Var(X)=E[X2]−(E[X])2Var(X)=E[X2]−(E[X])2
随机化方法
蒙特卡洛方法（Monte Carlo）
-
思想：通过 随机采样 近似计算复杂概率或数值。
-
应用：
-
计算积分 ∫abf(x)dx∫abf(x)dx。
-
估计圆周率 ππ（随机撒点求比例）。
-
-
示例代码（估算 ππ）：
-
import random def estimate_pi(n): inside = 0 for _ in range(n): x, y = random.random(), random.random() if x**2 + y**2 <= 1: inside += 1 return 4 * inside / n print(estimate_pi(1000000)) # 输出接近 3.141592...拉斯维加斯算法（Las Vegas）
-
思想：随机化决策，但结果 一定正确（可能运行时间不确定）。
-
应用：
-
快速排序（随机选择基准点）。
-
随机化素数测试（Miller-Rabin算法）。
-
-
示例代码（随机化快速排序）：
-
import random def quicksort(arr): if len(arr) <= 1: return arr pivot = random.choice(arr) # 随机选择基准 left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quicksort(left) + middle + quicksort(right)随机游走（Random Walk）
-
思想：通过 随机步骤 模拟复杂系统（如股票价格、分子运动）。
-
应用：
-
PageRank 算法（网页排名）。
-
马尔可夫链蒙特卡洛（MCMC）采样。
-
统计中的随机化
自助法（Bootstrap）
-
思想：通过 有放回抽样 估计统计量（如均值、方差）。
-
步骤：
-
从原始数据中 随机抽取 nn 个样本（可重复）。
-
计算统计量（如均值）。
-
重复多次，得到统计量的分布。
-
-
示例代码（计算均值的置信区间）：
-
import numpy as np data = np.random.normal(0, 1, 100) # 原始数据 bootstrap_means = [] for _ in range(1000): sample = np.random.choice(data, size=100, replace=True) bootstrap_means.append(np.mean(sample)) print("95% 置信区间:", np.percentile(bootstrap_means, [2.5, 97.5]))假设检验（Hypothesis Testing）
-
思想：通过 随机排列 判断观测结果是否显著。
-
示例（A/B 测试）：
-
零假设 H0H0：A组和B组无差异。
-
方法：
-
随机打乱两组标签。
-
计算统计量（如均值差）。
-
重复多次，计算 pp-值。
-
-
位运算
直接对 二进制位（bit） 进行操作，比加减乘除更快，常用于 底层优化、算法优化、状态压缩 等场景。
假设 A = 60（二进制 0011 1100），B = 13（二进制 0000 1101）：
| 运算符 | 符号 | 描述 | 示例（A=60, B=13） | 运算结果（二进制） | |||
|---|---|---|---|---|---|---|---|
| 位与 | & | 两个位都为1，结果才为1 | A & B | 0000 1100（12） | |||
| 位或 | | | 只要有一个位是 1，结果就是 1 | A|B |
| |||
| 异或 | ^ | 两个位不同，结果才为1 | A ^ B | 0011 0001（49） | |||
| 取反 | ~ | 所有位取反（0变1，1变0） | ~A | 1100 0011（-61） | |||
| 左移 | << | 所有位左移，低位补0 | A << 2 | 1111 0000（240） | |||
| 右移 | >> | 所有位右移，高位补符号位（算术右移） | A >> 2 | 0000 1111（15） |
几何
- 计算几何
核心思想：用 计算机算法 高效解决几何问题，避免浮点数误差。
关键工具：向量叉积、点积、凸包、扫描线算法。
典型问题：判断点是否在多边形内（射线法）。
求凸包（Graham Scan）。
最近点对（分治法）。
示例（向量叉积判断方向）：
叉积=(Bx−Ax)(Cy−Ay)−(By−Ay)(Cx−Ax)
给定点A(x1,y1),B(x2,y2),C(x3,y3)计算叉积：叉积 >0：C 在 AB 左侧。
叉积 =0：三点共线。
叉积 <0:C 在 AB右侧。
struct Point { double x, y; }; double cross(Point A, Point B, Point C) { return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x); } // 用法：判断C在AB的哪一侧 if (cross(A, B, C) > 0) cout << "左侧"; 向量叉积（判断方向）
- 解析几何
核心思想：用 坐标系 + 代数方程 研究几何问题。
关键工具：笛卡尔坐标系（x, y, z）、向量、方程（直线、圆、曲线）。
典型问题：
求两条直线的交点。
判断点是否在圆内。
计算多边形面积。
示例（求直线交点）：
给定两条直线：
{L1:y=2x+1 {L2:y=−x+4联立方程解得交点：
2x+1=−x+4⟹x=1, y=3
#include
#include
#include
// 定义点结构体
typedef struct {
double x;
double y;
} Point;
// 定义直线结构体（一般式：Ax + By + C = 0）
typedef struct {
double A;
double B;
double C;
} Line;
// 定义圆结构体
typedef struct {
Point center;
double radius;
} Circle;
//两点确定直线
Line line_from_points(Point p1, Point p2) {
Line L;
L.A = p2.y - p1.y;
L.B = p1.x - p2.x;
L.C = p2.x * p1.y - p1.x * p2.y;
return L;
}
//示例调用
Point p1 = {1.0, 2.0};
Point p2 = {3.0, 4.0};
Line L = line_from_points(p1, p2);
printf("直线方程: %.2fx + %.2fy + %.2f = 0
", L.A, L.B, L.C);
// 输出: 直线方程: 2.00x + -2.00y + 2.00 = 0
组合数学 计数与存在性，两者常结合使用（如先证明存在性，再计数具体方案）
- 容斥原理 用于精确计算，需处理交集/并集的复杂关系
计算多个集合的并集时，通过“加加减减”避免重复计数。
公式：
对于集合 A1,A2,…,An:
代码参考
代码实现（计算并集大小）：
def inclusion_exclusion(sets):
n = len(sets)
total = 0
for k in range(1, n + 1):
from itertools import combinations
for subset in combinations(sets, k):
intersection = set.intersection(*subset)
total += (-1) ** (k + 1) * len(intersection)
return total
- 鸽巢原理 用于证明必然性，简单但威力强大
核心思想：如果有 n+1 只鸽子飞进 n 个鸽巢，至少有一个鸽巢有至少 2 只鸽子。
扩展形式：
若 m 只鸽子放入 n个鸽巢，则至少有一个鸽巢有 ⌈m/n⌉ 只鸽子。经典应用：
重复元素：任意 n+1个正整数中必有两个数的差是 n的倍数。
生日问题：23 人中至少有两人同一天生日的概率 > 50%。
代码参考
代码实现（判断是否存在重复）：
def has_duplicate(nums):
return len(nums) > len(set(nums))
数论
数论是数学的一个分支，研究整数的性质及其相互关系。它在密码学、计算机科学、算法设计等领域有重要应用。
1. 基础概念
(1) 整除与素数
-
整除：若 a=b×q，则称 b 整除 a，记作 b∣a。
-
素数：大于1的自然数，除了1和自身外无其他约数（如2, 3, 5, 7）。
-
合数：非素数且大于1的自然数（如4, 6, 8）。
代码实现（判断素数）：
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
