大整数乘法

                                                                                     大整数乘法                                                                                                                                                          

分析算法计算复杂性时,加法乘法当做基本运算来处理,即一次加法或者乘法当做一个仅取决于计算机硬件处理速度的常数。

正常的二进制整数X,Y要用O(n2)才能算出。如果分割为两段,

X=A2^(n/2)+B,Y=C2^(n/2)+D。

XY = (A2^(n/2)+B)(C2^(n/2)+D)=AC2^n+(AD+BC)2^(n/2)+BD

要进行4次N/2位整数的乘法,以及3次不超过2n为的整数加法,好要做2次移位。

T(n) = O(n^2);

XY=AC2^n+((A-B)(D-C)+AC+BD)2^(n/2)+BD

仅作3次N/2位整数的乘法,6次加减法,2次移位..

时间复杂度变为t(n)=O(n^1.59)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据文摘

正则表达式太慢?这里有一个提速100倍的方案(附代码)

26440
来自专栏chenjx85的技术专栏

leetcode-169-Majority Element

21740
来自专栏绿巨人专栏

Category Theory: 01 One Structured Family of Structures

\(G = \{ G, +, e \}\),一个数据集\(G\),一个二元操作符\(+\),和一个幺元\(e\)。

13530
来自专栏python读书笔记

《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

21360
来自专栏追不上乌龟的兔子

[多少懂点位运算]找出唯一的数字

大家都知道现代计算机的底层是以二进制为基础的,计算机所有的操作最后都归结到了简单的二进制位运算上:与,或,非和异或。

26350
来自专栏算法channel

其他|二维指针,数组指针,指针数组

望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。 1c++ c/c++的重要性毋庸置疑,凡是对性能要求很高的系统和算法,其中核...

33350
来自专栏Lambda

JavaScript排序算法详解

JS家的排序算法 引子 有句话怎么说来着: 雷锋推倒雷峰塔,Java implements JavaScript. 当年,想凭借抱Java大腿火一把...

31880
来自专栏小红豆的数据分析

小蛇学python(6)python实现经典排序算法并可视化分析复杂度

排序算法在算法界是一个怎么样的存在?就好像在学术界中数学的地位,说直接用好像用不上,可是不会做起事情来总会捉襟见肘,左支右绌。找工作的时候,有的面试官甚至会让我...

22120
来自专栏软件开发

分分钟弄明白UML中泛化 , 实现 , 关联, 聚合, 组合, 依赖

在UML类图中,常见的有以下几种关系: 泛化(Generalization),  实现(Realization), 关联(Association), 聚合(Ag...

193100
来自专栏编程直播室

读书笔记:《算法图解》第三章 递归

16550

扫码关注云+社区

领取腾讯云代金券