Tag: 算法分析

2024
算法字符串

暴力算法更实用：字符串匹配平均比较次数

摘要: 字符串匹配的暴力算法平均情况时间复杂度 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 KMP算法与代码模板 中，我们介绍了字符串精确匹配的 KMP 算法，这应该也是名声最大的算法，它

算法算法分析

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

摘要: 通过概率方法讨论上下界的方式 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的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 各位好，前面几篇文章我们讨论了一些数据结构。根据实际需求设计的一个数据结构，往往支持很多操作。当我们谈这个数据结构的效率怎么样的

算法搜索

回溯法的搜索树规模的上界估计

摘要: 暴力算法怎样实现评估可不可行 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 此前我们系统了解过回溯法，并解决了很多问题，参考文章 回溯法的思想、设计与分析。回溯法其实就是一种暴力方法，因此在

算法大数据算法

随机数的可信性：事前理论论证，事中算法流程，事后统计验证

摘要: 随机数的可信性。参考：计算机程序设计艺术 第三章 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 大老板面临的随机公平性问题 最近新晋网红周鸿祎在各短视频平台上高调卖他9

算法算法分析

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

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

算法算法分析

沃利斯积分的分段渐近估阶：拉普拉斯方法的思想启蒙

摘要: 分段渐近估阶的例子，与实践中的注意事项 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 冒泡排序平均需要跑多少趟：拉马努金Q函数初探 和 插入多少次发生哈希冲突：拉马努金Q分布与二元渐

算法算法分析

插入多少次发生哈希冲突：拉马努金Q分布与二元渐近分析

摘要: 拉马努金 Q 函数及其在算法分析中的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们继续讨论算法分析中的问题。 在哈希算法的分析中，哈希冲突是最受关注的问题。考虑有一个长

算法算法分析

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

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

算法算法分析

n节点的无序标号树有多少种：拉格朗日反演的应用

摘要: 拉格朗日反演的应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们继续来讨论算法分析的问题。 对于图论中的很多算法，其时间复杂度的分析经常需要基于 n 节点的无序标号树共有多

算法算法分析

二叉树的计数：直接方法与间接方法

摘要: 通过二叉树计数的基础问题，了解生成函数计数的直接方法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在对与二叉树相关的算法进行算法分析时，一个非常基本的问题是：给定一些条件，问满足这些条件的

算法算法分析

生成函数的性质速查

摘要: 生成函数的性质 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 生成函数即母函数，有时也叫形式幂级数。是组合数学中的一个重要理论和工具。 生成函数的一个重要线索来自于 18

算法算法分析

算法分析中的欧拉方程：基于三数中值法的快速排序

摘要: 三数中值法的快速排序，欧拉方程的求解 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在大学高等数学或考研高等数学中，我们学过几类容易求解的常微分方程的解法，特别地对于常系数

算法算法分析

渐近估阶的威力：欧拉-麦克劳林公式的应用

摘要: 用欧拉-麦克劳林公式对调和级数估阶 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文我们来讨论一下算法分析中的问题。 由于递归和迭代是最常见的两种程序结构。因此时间复杂度 $T(n

2023
算法算法分析

渐进分析的一些例子

摘要: 渐进分析的一些经典问题 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 函数增长与渐进分析入门 中我们学习了函数增长的阶和渐进分析的一些基础知识。本文我们看一些渐进分析中的一些经典问题

算法算法分析

在归并排序中对小数组采用插入排序

摘要: 使递归的叶子变粗 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 分治算法的设计与分析-归并排序 中，我们了解了分治算法的设计和分析方法，并且得出了归并排序算法的最坏情况运行时间为 $

算法算法分析

函数增长与渐进分析入门

摘要: 函数增长与渐进分析入门 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 在文章 基于随机访问机模型分析算法 中我们了解了算法分析确定算法精确运行时间的方法论。 当输入规模足够大，精确运行时间中

算法基础算法

分治算法的设计与分析-归并排序

摘要: 以归并排序为例来看分治算法的设计与分析 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 分治法的设计思路一些算法在结构上是递归的，为了解决一个给定的问题，算法一次或多次递归地调用自身以解决相关

算法算法分析

基于随机访问机模型分析算法

摘要: 分析算法的方法论 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 分析算法，也就是预测算法需要的时间和资源。我们关心的资源问题包括内存、通信带宽、计算机硬件等。但我们往往更关

算法算法分析

霍尔三元组、循环不变式与程序正确性

摘要: 循环不变式 【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：潮汐朝夕我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 托尼·霍尔 (Hoare) 是 20 世纪非常有影响力的一位计算机科学家，1980 年图灵奖。我们熟知的快速排序

2022
算法疑难杂症

算法导论第四版

摘要: 算法导论第四版介绍 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文介绍一下算法导论第四版。本书的第四版是去年出来的，新增了机器学习算法等内容，还是有不少更新的。本书完整下载链接如下

算法疑难杂症

二分/手撕平衡树/分治/stable_sort

摘要: 综合题：二分、平衡树、分治、stable_sort 四种解法 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们看一个排序的变种问题。跟排序一样，本题的解法也非常多，并且每个算法都是主流

算法算法分析

具体数学

摘要: 《具体数学》，算法分析的数学基础 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 书名《具体数学》 豆瓣链接: 具体数学 : 计算机科学基础 时间: 2013 具体数学 递归问题

2020
算法数据结构

二叉堆

摘要: 经典的二叉堆的实现，附代码模板和应用 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们串讲一下经典的二叉堆的原理、实现，代码模板和应用。 $1 二叉堆原理堆是一种支持插入key，删除

算法搜索

隐式图搜索的概念与例子

摘要: 隐式图搜索的概念，以单词接龙为例 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 本文我们首先介绍隐式图搜索的相关概念，然后解决一个非常经典的用 BFS 解决的隐式图搜索问题，用建图和不建图的

数数论

素数筛

摘要: 本文介绍素数筛的算法原理和代码模板、以及几道相关题目 【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】我的网站：潮汐朝夕的生活实验室我的公众号：算法题刷刷我的知乎：潮汐朝夕我的github：FennelDumplings我的leetcode：FennelDumplings 各位好，本文详细研究素数筛。首先以力扣第 204 题为模板题学习埃氏筛和线性筛，然后讨论素