VC维理论
VC维与泛化误差上界的深度解析一、VC维（Vapnik-Chervonenkis Dimension）1. 定义VC维是衡量模型复杂度的核心指标，表示一个分类模型能够“完美拟合”（即打散）的最大样本集的大小。
打散（Shatter）：如果模型能对一组样本的所有可能标签组合（(2^n)种）进行分类，则称该样本被“打散”。
VC维：模型能打散的最大样本数( h )。若存在至少一组( h )个样本能被模型打散，但不存在( h+1 )个样本能被打散，则VC维为( h )。
2. 直观理解
简单模型：VC维低（如线性分类器在二维空间的VC维=3）。
（二维中，线性分类器最多能打散3个点，无法打散4个点）
复杂模型：VC维高（如深度神经网络可打散极多样本）。
3. 计算示例
线性分类器：在( d )维空间的VC维为( d+1 )。
决策树：VC维与树深度和叶子节点数相关。
二、泛化误差上界公式[R(f) \leq R_{\text{emp}}(f) + \sqrt{\frac{h \left( \log(2n/h) + 1 \right) - \log(\eta& ...
动态规划
14.3 DP 解题思路 - Hello 算法
如何判断一个问题是不是动态规划问题？
求解动态规划问题该从何处入手，完整步骤是什么？
如何判断动态规划问题？
[!NOTE] DP三大特征如果一个问题包含重叠子问题、最优子结构，并满足无后效性，那么它通常适合用动态规划求解。然而，我们很难从问题描述中直接提取出这些特性。因此我们通常会放宽条件，具体如下
先验条件：是否能用回溯（决策树）、DFS 暴力穷举？
加分项：
问题目标是最优解（最大值/最小值）。
状态转移可被公式化（如 dp[i] = dp[i-1] + ...）。
减分项：
需要输出所有解（而非最优解）。动态规划通常会在求解过程中”压缩”或”丢弃”次优解，只保留最优解用于后续计算，保存所有解需要指数级空间
明显属于排列组合问题（例如全排列）。
通过分析这三个特征，可以系统化判断一个问题是否适合动态规划。
动态规划的三个核心特征是重叠子问题、最优子结构和无后效性。以下通过具体例子和通俗解释说明它们的含义和区别：
1. 重叠子问题（Overlapping Subproblems）
定义：在求解过程中， ...
关系数据库管理系统（RDBMS）中的游标（Cursor）
关系数据库管理系统（RDBMS）中存在游标（Cursor）的概念。游标是数据库查询结果集的抽象表示，允许开发者逐行处理查询结果。以下是关键要点：
游标的核心特性
结果集导航
游标提供在查询结果中逐行移动的能力（类似程序中的指针）
数据操作
支持通过游标定位更新或删除当前行（定位更新/删除）12UPDATE employees SET salary = salary * 1.1WHERE CURRENT OF employee_cursor;
作用域控制
显式声明生命周期：DECLARE → OPEN → FETCH → CLOSE → DEALLOCATE
游标类型对比
类型
特点
适用场景
静态游标
结果集快照（打开时不反映后续数据变化）
需要数据一致性
动态游标
实时反映其他事务的修改（插入/更新/删除）
高并发实时系统
键集驱动游标
仅跟踪键值变化（不反映新增行）
平衡性能与实时性
只进游标
仅支持单向遍历（最高效）
简单遍历（最常用）
游标使用场景
复杂业务逻辑处理
12345678910111 ...
sql having
SQL HAVING 子句使用详解HAVING 是 SQL 中用于过滤分组结果的关键字，它与 WHERE 类似但作用于聚合后的数据。以下是全面指南：
基本语法1234SELECT 列1, 聚合函数(列2)FROM 表名GROUP BY 列1HAVING 聚合函数(列2) 条件;
与 WHERE 的区别
特性
WHERE
HAVING
执行时机
在分组前过滤原始数据
在分组后过滤聚合结果
可用字段
原始列
聚合列或GROUP BY列
性能
更高效（减少处理量）
相对较低
使用场景1. 过滤聚合结果12345-- 查找平均分数大于80的班级SELECT class, AVG(score) as avg_scoreFROM studentsGROUP BY classHAVING AVG(score) > 80;
2. 结合多个聚合条件12345678-- 找出总销售额超过1万且订单数大于50的销售员SELECT salesperson,SUM(amount) as total_sales,COUNT(*) as order_countFROM ordersG ...
堆
推荐直接看网页和本页的heapq库：8.1 堆 - Hello 算法
基于堆更加高效地解决 Top-k 问题，流程
堆化（Heapify），即建堆操作：如何从一个无序数组或不符合堆性质的完全二叉树构建堆堆化的核心操作是 heapify_down（下沉） 或 heapify_up（上浮），这两个都是强调修复和单个元素，通过递归或迭代调整节点位置，最终使整个数据结构满足堆性质。
Top-k 问题问题：给定一个长度为n的无序数组 nums ，请返回数组中最大的k个元素。步骤：
初始化一个小顶堆，其堆顶元素最小。
先将数组的前k个元素依次入堆。
从第k个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆(最小元素出堆)。
遍历完成后，堆中保存的就是最大的k个元素。复杂度： n轮入堆和出堆，堆的最大长度为 k，因此时间复杂度为nlogk
python的heapq（堆队列）库用法：注意，heapq借助原生的数组实现！！而不是heapq()！
Python 的 heapq 模块提供了基于堆的优先队列实现，支持最小堆（Min Heap）操作。以下是 heapq 的核心用 ...
堆排序
井号层序遍历序列表示的树你提供的 {5,4,#,3,#,2,#,1} 是一种用井号（#）表示空节点的层序遍历序列表示的二叉树。这种表示方法也称为序列化二叉树，常用于LeetCode等编程题中。
具体解释：这个序列按层序遍历（广度优先）的顺序列出节点，用 # 表示空节点（即无子节点）。构建树时，我们需要逐层填充节点，遇到 # 则表示该位置没有节点。
你的例子：{5,4,#,3,#,2,#,1}
根节点：第一个元素 5 是根节点。15
第二层：接下来的两个元素 4 和 # 是根节点的左右孩子。
4 是左孩子。
# 表示右孩子为空。1235/4
第三层：4 的左右孩子是接下来的两个元素 3 和 #。
3 是左孩子。
# 表示右孩子为空。123455/4/3
第四层：3 的左右孩子是 2 和 #。
2 是左孩子。
# 表示右孩子为空。12345675/4/3/2
第五层：2 的左右孩子是 1 和 #。
1 是左孩子。
# 表示右孩子为空。1234567895/4/3/2/1
最终树的结构：1234567895/4/3/2/1 ...
希尔排序
希尔排序是插入排序的优化版本，通过分组插入排序逐步减少逆序对，最终完成全局排序。
希尔排序（Shell Sort）详解1. 基本步骤希尔排序是插入排序的优化版本，通过分组插入排序逐步减少逆序对，最终完成全局排序。具体步骤：
选择增量序列（gap）：通常初始取 gap = n/2，之后每次减半（gap = gap/2），直到 gap = 1。
分组插入排序：
对每个 gap 值，将数组分为 gap 组，每组包含间隔为 gap 的元素。
对每组进行插入排序（组内元素较少，排序效率高）。
逐步缩小 gap：重复上述过程，直到 gap = 1 时完成最后一次插入排序，此时数组已基本有序，插入排序效率极高。
示例（数组 [8, 3, 6, 2, 5, 9, 1, 7, 4]）：
gap = 4：分组 [8,5,4], [3,9], [6,1], [2,7] → 组内排序 → [4,3,1,2,5,9,6,7,8]
gap = 2：分组 [4,1,5,6,8], [3,2,9,7] → 组内排序 → [1,2,4,3,5,7,6,9,8]
gap = 1：全局插入排序 → [1,2, ...
生成式模型VS判别式模型
生成式模型的核心是学习数据的联合概率分布 P(X,Y)（监督学习）或 P(X)（无监督学习）。逻辑回归建模 P(Y∣X)，但它是判别式模型，因为它不关心 P(X)或生成 XX。
关键区分：生成式模型 vs 判别式模型
生成式模型（Generative Model）
学习数据的联合概率分布 $P(X, Y)$，然后通过贝叶斯定理计算后验概率 $$P(Y \mid X) $$进行分类。
特点：可以生成新的样本数据（如模拟输入$X$的分布）。
例子：朴素贝叶斯、高斯混合模型（GMM）、隐马尔可夫模型（HMM）、生成对抗网络（GAN）。
判别式模型（Discriminative Model）
直接学习条件概率 $P(Y \mid X)$ 或决策边界。
特点：专注于分类/回归任务，无法生成数据。
例子：逻辑回归、支持向量机（SVM）、神经网络、决策树。
为什么朴素贝叶斯是生成式模型？朴素贝叶斯的分类过程分为两步：
学习联合概率分布：
假设特征之间条件独立（“朴素”假设），计算 ( P(X \mid Y) ) 和先验概率 ( P(Y) )。
例如，在文本分类中，统计 ...
网络号
网络号(包括子网号),需要将IP地址和子网掩码进行按位与运算。
scanf %3d 指的是最多3位十进制整数，- 未处理的输入： 会留在输入缓冲区中，但不会被本次 scanf 读取。
1234567#include<stdio.h>int main(){ int x; float y; scanf("%3d%f", &x, &y); return 0;} 输入数据：12345M678＜CR＞后
**%3d 读取 x**：
从输入 12345M678 中截取前3位数字 123（因为 %3d 限制长度为3）。
x 被赋值为 123，剩余未处理的输入为 45M678。
%f 会尝试从剩余输入 45M678 中读取浮点数：
解析 45 为数字部分。
遇到字符 M 时停止（M 不是浮点数的有效字符）。
关键点
%3d 的 长度限制：确保只读取前3位数字，不受后续字符影响。
%f 的 终止条件：遇到非数字字符（如字母、符号）时停止解析。
未处理的输入：M678 会留在输入缓冲区中，但不会被本 ...
Boosting 算法对比
以下是GBM、LightGBM、AdaBoost、XGBoost和CatBoost的核心特点与适用性对比，重点突出差异点和应用场景：
1. AdaBoost (Adaptive Boosting)
核心思想：通过迭代调整样本权重，让后续弱学习器（如决策树桩）聚焦被前序模型分错的样本。
特点：
早期Boosting算法：对噪声和异常值敏感，易过拟合。
弱学习器简单：常用单层决策树（树桩）。
加权投票：最终模型为弱学习器的加权组合。
适用场景：
基础分类任务（如二分类）。
数据质量高、噪声少的场景。
局限性：对复杂非线性关系拟合能力弱于后续梯度提升算法。
2. GBM (Gradient Boosting Machine)
核心思想：用梯度下降优化任意可导损失函数，逐步添加弱学习器（树）拟合残差。
特点：
通用性强：支持自定义损失函数（回归：MSE；分类：LogLoss）。
易过拟合：需精细调参（学习率、树深度、树数量）。
顺序训练：难以并行，大规模数据效率低。
适用场景：
中小规模结构化数据。
需要模型可解释性的场景（浅层树）。
代表实现：sklearn ...