Tag: 算法分析

摊销分析:基于财务模型的记账法

摘要: 记账法的摊销分析 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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

渐进分析的一些例子

摘要: 渐进分析的一些经典问题 【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】我的网站:潮汐朝夕的生活实验室我的公众号:算法题刷刷我的知乎:潮汐朝夕我的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 年图灵奖。我们熟知的快速排序

算法导论第四版

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

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

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

具体数学

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

二叉堆

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

隐式图搜索的概念与例子

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

素数筛

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