C++数据结构:快速幂
xsobi 2024-11-23 10:51 11 浏览
朴素的求幂算法
也就是平常使用pow函数,最简单的实现就是一直累乘,可以得到这样的代码:
可以看到,算法的时间复杂度是O(n)。为了降低时间复杂度,我们可以使用快速幂算法,将时间复杂度降低到O(logn),n是幂。
快速幂
关于快速幂,博主的理解是使用位运算。下面是数学证明:
关于a^b,举一个实际的例子——2^10。
那么对于6而言,如果我们将10变成二进制,那么就是:1010,如果变成加权的情况可以得到表达式:
0*2^0 + 1*2^1 + 0*2^2 + 1*2^3
代入原来的2^10可以得到表达式:
2^(0*2^0 + 1*2^1 + 0*2^2 + 1*2^3)
然后再拆开并化简这个表达式,可以得到:
2^(2^1) * 2^(2^3)
也就是说,我们在求解2^10的时候,可以考虑成根据二进制的权值来求解的。那么在关于位运算的部分,我们可以逐位获取b的位,碰到0,就累乘,碰到1,就将累乘的值乘到答案。由此可以得到代码:
关于位运算的部分,这里只简单提一下,更多详细内容请百度。if语句中的b & 1,也就是将b与1按位与,那么1的二进制是1,也就是说b除了最后一位,其他位都和0相与,那么得到的值一定都是0。而最后一位与上1,那么原来位实际上是不变的。这样我们就获得了b的最后一位的值。while循环中b >>= 1,是移位运算,将b向右移动1位。因为每次我们都是要获取最后一位,看是0还是1,那么每次移动1位,下一次在碰见if语句,就得到原来最后一位的前一位了。
核心代码是下面这一部分:
博主理解这里理解半天Orz,这里其实是对上面一句话的模拟:“2^(2^1) * 2^(2^3)”。实际操作一下吧:
可以看到,出现0的时候,我们就累乘,得到的是幂的累积值。出现1的时候,我们将累积的幂值进行累乘。或者说碰见一个1,就出现一次底数2。
如果仍然没有太理解,debug一下会有很多帮助。
快速幂取模
这一部分就跟数论关系很大了。取模也是数论问题中经常出现的。那么对于幂来取模,如果我们直接用模运算实际上是速度很慢的(因为试除法)。所以我们不妨在求快速幂的时候添加一些内容,从而得到结果。这个算法需要了解一下数论的一个定理:
(a*b) mod c = ((a mod c)*(b mod c)) mod c
那么根据上面的定理可以推导出另一个定理:
(a^b) mod c = (a mod c)^b mod c
具体的证明这里不再赘述,主要是看第二个定理,恰好符合我们的小标题——快速幂取模。我们可以在求快速幂的时候,通过对底数取模的方式,不断缩小底数的规模。那么我们在上面快速幂的基础上,添加取模,就可以完成整个操作。
如果能理解上面的快速幂算法,那么这个也会比较好理解了。定理里面,底数是要有一次取模运算的。这里我们在给base赋值的时候就运行了一次。那么对于后面的一次取模,我们实际上利用了分配率,即:
(a*b) mod c = ((a mod c)*(b mod c)) mod c
我们求幂的本质仍然是求积。所以每次我们对base或者ans进行运算的时候,都必须使用一次分配率,所以都要mod c。
总结
在这里为大家准备了做算法题时的代码模板,是yxc大佬的总结,希望对大家有帮助:
希望大家点赞三连[灵光一闪]
- 上一篇:集合框架知识
- 下一篇:《Java编程思想》第五版:第四章 运算符
相关推荐
- 高并发基础-一文带你了解Redis及其常见用法与应用场景
-
1.概述Redis是一个键值对存储的存储系统;一般用做缓存比较多,也可以将其作为数据库及消息中间件使用。传统应用中,数据存储在关系型数据库中,前端请求到来时通过SQL语句查询关系型数据库中的数据并返...
- Python中的函数注释:参数有冒号,声明后有-> 箭头
-
我在查看python的fixture源码时发现fixture的方法定义形式如下:deffixture(fixture_function:Optional[_FixtureFunctio...
- 干货!SQL性能优化,书写高质量SQL语句
-
写SQL语句的时候我们往往关注的是SQL的执行结果,但是是否真的关注了SQL的执行效率,是否注意了SQL的写法规范?以下的干货分享是在实际开发过程中总结的,希望对大家有所帮助!1.limit分页优化...
- 一起学《C程序设计》第十课——结构体、共用体以及枚举类型
-
注意,请认真学习完《C程序设计(第五版)》第九章后再阅读本文会有更大的收获。结构体作用与定义前面我们学习过C语言的数组,C语言的数组在使用上有一定的局限性,比如我们常使用的一维数组一旦定义了就只能接纳...
- 8 种最坑的SQL错误用法,你有没有踩过?
-
来源:yq.aliyun.com/articles/725011、LIMIT语句2、隐式转换3、关联更新、删除4、混合排序5、EXISTS语句6、条件下推7、提前缩小范围8、中间结果集下推总结sq...
- ArkTS基础语法:从声明到类型的深度解析
-
#ArkTS基础语法:从声明到类型的深度解析在鸿蒙应用开发的领域中,ArkTS作为重要的编程语言,其基础语法是开发者们必须掌握的关键内容。今天,我们就围绕ArkTS的声明和类型相关知识展开深入探讨,...
- 8 种最坑的 SQL 错误用法,你有没有踩过坑?
-
原文作者:程序员追风01、LIMIT语句分页查询是最常用的场景之一,但也通常也是最容易出问题的地方。比如对于下面简单的语句,一般DBA想到的办法是在type,name,create_time...
- Python常用数据类型及其用法-总结篇
-
前言在前面的文章中,我们介绍了Python常用的数据类型及其相关方法,分别为:《Python列表详解》《Python元组与字典用法详解》《Python集合详解》《Python字符串》与我们软件开发或测...
- 贯穿知识点看“线”(名师知识点总结训):状语从句
-
添加关注不迷路!!!状语从句状语从句有时间、地点、原因、目的、结果、条件、方式、比较和让步状语从句,共9种,是每年必考的语法项目,主要考查连词的判断选用,主句与从句谓语动词的时态运用。其中,以对时间状...
- C++关键字介绍(c++语言中常用的关键字含义)
-
下表列出了C++中的常用关键字,这些关键字不能作为变量名或其他标识符名称。1、autoC++11的auto用于表示变量的自动类型推断。即在声明变量的时候,根据变量初始值的类型自动为此变量选择匹配的...
- 核心词汇aboard,abroad和board用法解析
-
1.aboardadv./prep.在船上;在(船、飞机、公共汽车、火车等)上;上(船、飞机、公共汽车、火车等)意为“在公共汽车/船/火车/飞机上;上公共汽车/船/火车/飞机”,可作介词式副词。Th...
- Excel VBA小技巧:Areas集合,你不知道的多区域操作神器
-
大家好!今天我们来聊聊ExcelVBA中一个超级实用但经常被忽视的功能——Areas集合。如果你经常需要处理不连续的多区域操作,这篇文章绝对能让你眼前一亮!什么是Areas集合?简单来说,Areas...
- Flink用法介绍(flink的使用场景)
-
自定义source只需要传入一个SourceFunction即可val stream4 = env.addSource( new MySensorSo...
- amiable与amicable 用法辨析(able和capable的区别)
-
1.amiable/'emibl/用于指人,其意义为:“友好的”“和蔼的”(friendly,good-natured,good-humored):Thenext-doorneighbou...
- 常考词汇in terms of用法解析(in terms of doing)
-
intermsof含义较多,要根据上下文来判断,如:1.intermsof用……术语(话、字眼、口吻)Hereferredtoyourworkintermsofhighpr...
- 一周热门
- 最近发表
- 标签列表
-
- grid 设置 (58)
- 移位运算 (48)
- not specified (45)
- 导航栏 (58)
- context xml (46)
- scroll (43)
- dedecms模版 (53)
- c 视频教程下载 (33)
- listview排序 (33)
- characterencodingfilter (33)
- getmonth (34)
- label换行 (33)
- android studio 3 0 (34)
- html转js (35)
- 索引的作用 (33)
- checkedlistbox (34)
- xmlhttp (35)
- mysql更改密码 (34)
- 权限777 (33)
- htmlposition (33)
- 学校网站模板 (34)
- textarea换行 (34)
- 轮播 (34)
- asp net三层架构 (38)
- bash (34)