Tag: 证明

2024
算法算法分析

一个算法分析的证明：概率方法证明上下界的范式

摘要: 通过概率方法讨论上下界的方式 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们来看一个算法分析中的不起眼的问题，证明过程很简单，但是体现了一种证明的范式，这种范式跟香农信息论中

算法算法分析

斐波那契数的一个渐近下界 | Dijkstra算法+斐波那契堆的基础

摘要: 斐波那契堆时间复杂度推导的基础 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，关注算法的学生和工程师最近可能刷到了一篇关于 Dijkstra 算法的文章。我是在量子位上首先刷到的，后

算法算法分析

可清空表的摊销分析

摘要: 摊销分析的例子 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，前面几篇文章我们讨论了一些数据结构。根据实际需求设计的一个数据结构，往往支持很多操作。当我们谈这个数据结构的效率怎么样的

数统计

数据直觉：至少一条数据偏离均值至少一倍标准差

摘要: 对任意数据集，至少有一条数据偏离均值至少一倍标准差 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在上一篇文章 数据直觉：任意数据集都很难有偏离均值多倍标准差的数据 中，我们简要介绍了数据集

数统计

数据直觉：任意数据集都很难有偏离均值多倍标准差的数据

摘要: 对任意数据集，很难有偏离均值多倍标准差的数据 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 新拿到一份业务数据，在分析这份数据的时候，我们往往从均值和标准差入手。本文我们推导均值和标准差的两

数博弈

博弈论：二元函数的鞍点定理

摘要: 二元函数的鞍点 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 minimax算法初探以及若干例子 中，我们介绍了博弈算法中最重要的 minimax 算法，其背后是二人有限零和博

数分析

夹逼定理加放缩法，将和式放缩为最值

摘要: 夹逼定理+放缩法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 由p范数诱导的距离，当p趋于无穷时为切比雪夫距离 中，我们主要证明了 p 范数诱导的距离当 $p \rightarro

数几何

由p范数诱导的距离，当p趋于无穷时为切比雪夫距离

摘要: 切比雪夫距离与闵可夫斯基距离的关系 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 此前我们解决过很多几何问题。这些几何问题都是在欧式空间的框架下的。在文章 几何题汇总 中我们总结了几何问题相

算法基础算法

范围缩放法证明贪心的正确性

摘要: 范围缩放法例子 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文看一个比较简单的贪心算法的问题，思路和算法很好想。这个题值得分享的亮点是这是使用范围缩放法证明贪心正确性的例子。 范围缩放法

数分析

一个有概率背景的抽象不等式，积分中值定理的应用

摘要: 积分中值定理主线梳理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们来看一个抽象不等式。该不等式描述了一类随机变量 $X$ 的期望的一个下界：如果 $X$ 的取值范围为 $[a, b

数概率

概率方法的威力：由数学期望的性质推导出不等式

摘要: 概率方法在不等式证明中的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，今天我们继续看一个概率方法在证明不等式时的威力，整体上的方法与 一个微分不等式，概率方法的威力 中类似，只

数概率

一个微分不等式，概率方法的威力

摘要: 概率方法证明微分不等式一例 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 我们大学以及考研的时候都学过微分中值定理。书上给出的形式是 $f(b) - f(a) = f’(\xi)(b - a

数概率

Schweitzer不等式，概率方法的威力

摘要: 概率方法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 概率方法证明不等式：构造随机变量，将不等式中的项解释为事件的概率 中，我们介绍了证明不等式的概率方法，在文章 Weier

数概率

Weierstrass不等式，概率方法的威力

摘要: 概率方法在证明不等式中的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 概率方法证明不等式：构造随机变量，将不等式中的项解释为事件的概率 中，我们介绍了证明不等式的概率方法并解决

数数论

完全数，因子之和函数

摘要: 完全数 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们介绍一下最早由古希腊人提出的完全数，也称完美数。对于一个正整数 $n$，如果除它自身以外所有的正因子之和等于该正整数 $n$ 自

算法字符串

字符串的循环同构与最小表示法

摘要: 循环同构字符串中哪个字典序最小 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 问题背景给定一个字符串 s，如果不断把最后一个字符放在开头，最终会得到 $n$ 个字符串，称这 $n$ 个字符串

数优化

一元函数的单调性、凸性与单峰性

摘要: 一元函数的单调性、极值、凸性 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文介绍一元连续函数的单调性、凸性、极值相关的概念以及主要定理。这些是二分算法的基础。 在单调性

算法动态规划

使得乘积最大的整数分拆：基于数学性质对决策空间剪枝

摘要: 动态规划解决数列第 n 项问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings \max\limits_{\substack{2 \leq k \leq x \\ \sum_{i=1}^{k

算法数学算法

通过不等式优化的算法问题

摘要: 不等式在算法优化中的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，不等式经常在解决优化或最值问题时有所应用，例如均值不等式是我们高中时接触过的重要不等式，经常用于解决一些比较简

算法动态规划

剪枝优化DP：基于数学性质排除大量无效决策

摘要: 剪枝策略减少最优决策候选集中的无效决策 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在基于动态规划解决最优性问题时，状态转移方程中，一个状态对应着很多决策。常规的方式是把这些决策都遍历一遍

数概率

概率方法证明不等式：构造随机变量，将不等式中的项解释为事件的概率

摘要: 构造随机变量，然后组装事件，凑出不等式的项中的概率 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个不等式的证明，涉及到构造随机变量通过概率方法证明的思路，还是很巧妙的。 其过程

算法动态规划

通过离散化处理状态表示中的稀疏维度

摘要: 状态表示中的附加信息要素非常稀疏时，可以用离散化的方式来处理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 对于动态规划问题，有时仅仅把阶段要素放到 DP 状态中，不足以执行转移。也就是说

算法算法分析

N节点二叉树种类数的渐近估阶：复变函数的奇点与幂级数的收敛半径

摘要: 复变函数的奇点与幂级数的收敛半径 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们继续讨论算法分析相关的问题。 在文章 二叉树的计数：直接方法与间接方法 中，我们通过生成函数推

算法算法分析

冒泡排序平均需要跑多少趟：拉马努金Q函数初探

摘要: 拉马努金Q函数在算法分析中的应用，初步体验 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们继续来讨论算法分析中的问题。 很多数组上的算法都与 $1 \sim n$ 的排列有关

2023
数图论

图的自同构群与对称性、可迁图

摘要: 图的群表示 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 图的同构点同构定义：$D = (V(D), E(D), \psi_{D})$ 和 $H = (V(H), E(H), \psi_{H

数图论

n维超立方体

摘要: n维超立方体的基础性质 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings n 维超立方体可以简单理解为 n 维空间中边长为 1 的正方体。它有很多非常好的性质，因此是大规模互联

数图论

k部图与图兰定理

摘要: k部图的应用 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 二部图是应用非常广泛的一类图。相关的理论研究的非常多，很多业务场景可以抽象为二部图上的匹配问题。而 k 部图在定

数组合数学

鸽巢原理及其加强形式

摘要: 鸽巢原理 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 鸽巢原理是组合数学中最古老的原理之一，也称为抽屉原理或Dirichlet原理。Dirichlet 在 1834 年提

数图论

伴随二部图、图论第一定理

摘要: 图论第一定理 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 二部图是一类结构简单又非常重要的图。在文章 二分图判定定理与算法 中我们介绍过二部图判定定理及算法。 对于任意有

算法leetcode

【搜索难题】力扣2258-逃离火灾

摘要: 搜索题，思路简单，细节复杂 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们来看一个搜索题。思路比较清晰，不过细节很复杂。需要针对人和火搜索两次。第二次既可以 BFS 也可以

数组合数学

SJT算法：沿哈密顿路径枚举全排列

摘要: 枚举全排列与哈密顿路径 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 回溯法的思想、设计与分析 中，我们系统学习了回溯法。回溯法将解空间看做树形结构，称为状态空间树，在文章 回溯法三

算法疑难杂症

均分纸牌问题

摘要: 贪心算法经典问题：均分纸牌 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们来看一下贪心算法的经典问题：均分纸牌问题。该问题在移牌规则上有两个比较常见的变种，一个是允许环形移牌，一个是

数分析

广义二项式定理的现代分析学证明，一元函数微分与泰勒定理复习

摘要: 广义二项式定理的现代分析学证明 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 广义二项式定理的推导 中，我们串讲了一下二项式定理的发展史，重点学习了牛顿发现广义二项

数组合数学

卢卡斯定理

摘要: 求组合数的代码模板和例题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 卢卡斯定理是由法国数学家爱德华·卢卡斯在1878年提出的，涉及到组合数和模运算，广泛应用于组合数学和数论中。 卢卡斯

数组合数学

形式幂级数的运算、性质、应用

摘要: 全面梳理形式幂级数的理论和应用 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 数学分析-级数论 中，我们系统学习过函数项级数，首先是收敛性、收敛半径以及各种判别法，

数组合数学

组合恒等式-基于六个基本组合恒等式

摘要: 六个基本组合恒等式 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 组合的定义： \binom{n}{k} = \frac{n!}{k!(n-k)!}二项式定理： (1 + x)^{n}

数组合数学

微积分方法证明组合恒等式

摘要: 组合恒等式：微积分方法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在组合数学、概率、分析中，经常会在推导中使用组合恒等式，很多组合恒等式事先不知道的话，是不容易看出来的。在文章 组合恒等

算法leetcode

力扣2389-和有限的最长子序列

摘要: 一个比较综合的简单题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们来看力扣上的一道我认为不错的题目，2389. 和有限的最长子序列，本题在力扣上标记为简单题，但该题综合了排

数方程

函数方程串讲、从零推导柯西方程的解

摘要: 最重要的一类函数方程：柯西方程 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 从零推导斯特林公式 中，我们严格证明了斯特林公式，它是信息论中推导取得最大熵的概率分布

2020
数组合数学

偏序集与Dilworth定理

摘要: 偏序集、Dilworth定理 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 此前我们系统第学习了组合数学，详细内容见下面这些文章： 组合数学1-排列组合 组合数学2-母函数,递推关系 组合

算法图算法

二部图判定定理与算法

摘要: 本文介绍二部图判定定理与二部图判定算法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 图论1-基本概念 中我了解了二部图的定义和一些性质。 本文我们以力扣第 785 题为模板题，看一

算法图算法

带权图最短路径算法与实现

摘要: 带权图单源最短路 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们以力扣 743 为模板题来看一下带权图的单源最短路问题的各种算法的原理以及实现。涉及到以下算法： dkijstra