首页 > 编程语言 >浅谈根号算法

浅谈根号算法

时间:2025-01-23 11:21:36浏览次数:1  
标签:浅谈 复杂度 sqrt 算法 mathcal 根号 暴力

前言

本人在 HL 集训时爱上了根号算法,遂开此坑。

所有根号算法都有一个共性:与暴力算法息息相关。但它们并不是拙劣的暴力,而是优美的暴力。所以根号算法也被称之为“暴力美学”。

根号分治就是一个典型的根号算法。当题目性质与 \(x\) 和 \(\frac{n}{x}\) 都有关时,我们可以找到一个分界点 \(B = \sqrt{n}\) 进行分治,一部分直接暴力,另一种部分利用上述性质使用某种方式来处理,这样我们就达到了一种微妙的平衡。

通过上面的例子,我们知道了大部分根号算法的另一个特点:在两个信息之间寻找平衡。分块思想也是如此。它将区间 \([1, n]\) 分为若干个长度为 \(\sqrt{n}\) 的块,每次区间操作(或询问)时,没有完全覆盖一个块的“边角料”可以暴力,而完全覆盖它的部分可以直接对整个块进行打标记等操作。前者虽然理论复杂度是 \(\mathcal{O}(n)\),但是需要暴力的“边角料”只有 \(\mathcal{O}(\sqrt{n})\) 个点,所以它的实际复杂度是 \(\mathcal{O}(\sqrt{n})\)。后者虽然理论复杂度较低(一般为 \(\mathcal{O}(\text{ploy}{\log n})\),为了方便,这里看做 \(\mathcal{O}(1)\)),但是它需要对 \(\mathcal{O}(\sqrt{n})\) 个块进行操作,所以它的实际复杂度也是 \(\mathcal{O}(\sqrt{n})\)。可以看到,分块在块长和块的数量中找到了平衡,它也将单次操作复杂度维持在了 \(\mathcal{O}(\sqrt{n})\)。

莫队是一种特殊的根号算法,它将操作(或询问)离线,由上次的结果进行暴力修改移动,得到了这次的结果。这种算法还将操作(或询问)按照某种方式排序,使得每次暴力修改移动的次数不超过 \(\mathcal{O}(\sqrt{n})\)(有的是 \(\mathcal{O}(n ^ {\frac{3}{2}})\)),进而保障了复杂度。

当然,根号算法也可以和其他算法(比如二分)结合,这样会使得复杂度在根号内或外带若干支 \(\log\)。

总体来说,根号算法避免了使用递归数据结构,使得程序常数较小。当然,根号的复杂度不够优秀并且较难优化,这也是它最大的问题。所以,熟练掌握根号算法并不是你放弃学习其他数据结构的理由。

(其实还有整除分块,但是它属于数学内容,所以就不放在这里啦。)

1. 分块

标签:浅谈,复杂度,sqrt,算法,mathcal,根号,暴力
From: https://www.cnblogs.com/Eliauk-FP/p/18687392

相关文章

  • 基于协同过滤算法的微信小程序文章推荐系统的设计与实现【高分毕设】
    目录资源链接论文链接后端系统链接微信端系统链接答辩PPT1.绪论1.1课题背景1.2研究目的和意义1.3文献回顾2.关键技术介绍2.1前端技术2.2协同过滤3.需求分析3.1可行性分析3.2功能需求分析3.2.1用户管理3.2.2文集管理3.2.3图书管理3.2.4文集和图书分类3.2.5......
  • 基于深度学习的高效非极大值抑制算法改进:从理论到实践
    非极大值抑制(Non-MaximumSuppression,NMS)是目标检测算法中的关键步骤,用于从多个重叠的候选框中筛选出最佳框。然而,传统的NMS算法在处理高密度目标场景或复杂背景时,可能会导致部分目标漏检或误检。本文探讨了基于深度学习的高效NMS算法改进,从理论分析到实际实现,为进一步优化目标......
  • 【优选算法篇】2----复写零
    ---------------------------------------begin---------------------------------------这道算法题相对于移动零,就上了一点点强度咯,不过还是很容易理解的啦~题目解析:这道题如果没理解好题目,是很难的,但理解题目就容易啦讲解算法原理:意思就是:一个数组长度是固定的,里面的......
  • 数组+贪心算法
    Problem:你可以获得的最大硬币数目思路用贪心思想考虑,在每一轮操作中,把最大的给Alice,如何把当前数组中次大的给自己,如何把最小的给Bob。以此类推,把数组的最小的三分之一给Bob即可,然后把剩下的交叉给Alice和自己。CodeclassSolution{publicintmaxCoins(int[]piles)......
  • 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素、977.有序数组的平方
    LeetCode7042025-01-2218:30:38星期三代码随想录视频内容简记梳理一下三个比较重要的部分首先是对于整个代码的循环条件,这个很重要判断middle位置在我看来初学也是比较重要一步注意:所有的middle位置判断都是if语句实现的,固定的大于和小于。这个不用纠结一不一样更......
  • 故障诊断 | DBO蜣螂优化算法LightGBM故障诊断(Matlab&Python)
    目录效果一览文章概述DBO蜣螂优化算法LightGBM故障诊断(Matlab&Python)DBO蜣螂优化算法LightGBM故障诊断研究一、引言1.1、研究背景及意义1.2、研究现状二、DBO蜣螂优化算法2.1、蜣螂优化算法的基本原理2.2、DBO算法的优化机制三、LightGBM模型......
  • 14 常用的负载均衡算法
    基于nginx的代理1.轮询算法例如我们在nginx服务器中代理了3台服务器,再每次客户端发起请求的时候按照顺序请求挨次的发送到代理的三台服务器上。该算法比较适合每台服务器性能差不多的场景,如果部分服务器性能比较差,可能会造成性能好的服务器资源的浪费或者性能比较差的服......
  • DL00461-深度学习算法变压器红外测温过热缺陷检测
    完整gou买链接:https://item.taobao.com/item.htm?ft=t&id=881079880820本系统以Dji指定型号无人机拍摄的红外图像作为原始输入,基于YOLOv9算法训练红外套管目标检测与分割模型。结合Dji测温SDK,系统实时获取目标区域的最大温度值,从而实现红外套管与接线端区域的最大温度测定。该......
  • 改进果蝇优化算法之二:基于极坐标变换的果蝇优化算法(PCT-FOA)
            基于极坐标变换的果蝇优化算法(PolarCoordinateTransformation-basedFruitFlyOptimizationAlgorithm,PCT-FOA)是对传统果蝇优化算法的一种改进,旨在通过引入极坐标变换来增强算法的搜索能力和稳定性。一、算法背景        果蝇优化算法(FOA)是一......
  • 路径规划之启发式算法之二十七:果蝇优化算法(Fruit Fly Optimization Algorithm,FOA)
            果蝇优化算法(FruitFlyOptimizationAlgorithm,FOA)是一种基于果蝇觅食行为的仿生学原理而提出的新兴群体智能优化算法。是众多群体智能算法之一,可看我的文章:仿生的群体智能算法总结之二(十种)_群体仿生智能-CSDN博客仿生的群体智能算法总结之二(十种)_群体仿生智......