漫画：如何实现大整数相乘？（上）
戳藍(lán)字“CSDN云計(jì)算”關(guān)注我們哦！
前一段時(shí)間，小灰發(fā)布了一篇有關(guān)大整數(shù)相加的漫畫，沒看過的小伙伴可以先看一看：
漫畫：如何實(shí)現(xiàn)大整數(shù)相加？
那么，大整數(shù)相乘又是如何實(shí)現(xiàn)的呢？
起初，小灰認(rèn)為只要按照大整數(shù)相加的思路稍微做一下變形，就可以輕松實(shí)現(xiàn)大整數(shù)相乘。但是隨著深入的學(xué)習(xí)，小灰才發(fā)現(xiàn)事情并沒有那么簡(jiǎn)單......
—————? 第二天? —————
怎樣列出這個(gè)乘法豎式呢？以 93281 X 2034 為例，豎式如下：
在程序中，我們可以利用int型數(shù)組，把兩個(gè)大整數(shù)按位進(jìn)行存儲(chǔ)，再把數(shù)組中的元素像小學(xué)豎式那樣逐個(gè)進(jìn)行計(jì)算。
這個(gè)乘法豎式的計(jì)算過程可以大體分為兩步：
1.整數(shù)B的每一個(gè)數(shù)位和整數(shù)A所有數(shù)位依次相乘，得到中間結(jié)果。
2.所有中間結(jié)果相加，得到最終結(jié)果。
/**
* 大整數(shù)求乘積
* @param bigNumberA ?大整數(shù)A
* @param bigNumberB ?大整數(shù)B
*/
public static String multiply(String bigNumberA, String bigNumberB) {
? ?//1.把兩個(gè)大整數(shù)用數(shù)組逆序存儲(chǔ)，數(shù)組長度等于兩整數(shù)長度之和
? ?int lengthA = bigNumberA.length();
? ?int lengthB = bigNumberB.length();
? ?int[] arrayA = new int[lengthA];
? ?for(int i=0; i< lengthA; i++){
? ? ? ?arrayA[i] = bigNumberA.charAt(lengthA-1-i) - '0';
? ?}
? ?int[] arrayB = new int[lengthB];
? ?for(int i=0; i< lengthB; i++){
? ? ? ?arrayB[i] = bigNumberB.charAt(lengthB-1-i) - '0';
? ?}
? ?//2.構(gòu)建result數(shù)組，數(shù)組長度等于兩整數(shù)長度之和
? ?int[] result = new int[lengthA+lengthB];
? ?//3.嵌套循環(huán)，整數(shù)B的每一位依次和整數(shù)A的所有數(shù)位相乘，并把結(jié)果累加
? ?for(int i=0;i<lengthB;i++) {
? ? ? ?for(int j=0;j<lengthA;j++) {
? ? ? ? ? ?//整數(shù)B的某一位和整數(shù)A的某一位相乘
? ? ? ? ? ?result[i+j] += arrayB[i]*arrayA[j];
? ? ? ? ? ?//如果result某一位大于10，則進(jìn)位，進(jìn)位數(shù)量是該位除以10的商
? ? ? ? ? ?if(result[i+j] >= 10){
? ? ? ? ? ? ? ?result[i+j+1] += result[i+j]/10;
? ? ? ? ? ? ? ?result[i+j] = result[i+j]%10;
? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?//4.把result數(shù)組再次逆序并轉(zhuǎn)成String
? ?StringBuilder sb = new StringBuilder();
? ?//是否找到大整數(shù)的最高有效位
? ?boolean findFirst = false;
? ?for (int i = result.length - 1; i >= 0; i--) {
? ? ? ?if(!findFirst){
? ? ? ? ? ?if(result[i] == 0){
? ? ? ? ? ? ? ?continue;
? ? ? ? ? ?}
? ? ? ? ? ?findFirst = true;
? ? ? ?}
? ? ? ?sb.append(result[i]);
? ?}
? ?return sb.toString();
}
public static void main(String[] args) {
? ?String x = "3338429042340042304302404";
? ?String y = "12303231";
? ?System.out.println(multiply(x, y));
}
————————————
下面，我們的推導(dǎo)會(huì)有一些燒腦，請(qǐng)大家坐穩(wěn)扶好~~
大整數(shù)從高位到低位，被平分成了兩部分。設(shè)整數(shù)1的高位部分是A，低位部分是B；整數(shù)2的高位部分是C，低位部分是D，那么有如下等式：
如果把大整數(shù)的長度抽象為n，那么：
因此，整數(shù)1與整數(shù)2 的乘積可以寫成下面的形式：
如此一來，原本長度為n的大整數(shù)的1次乘積，被轉(zhuǎn)化成了長度為n/2的大整數(shù)的4次乘積（AC，AD，BC，BD）。
什么是master定理呢？
master定理的英語名稱是master theorem，它為許多由分治法得到的遞推關(guān)系式提供了漸進(jìn)時(shí)間復(fù)雜度分析。
設(shè)常數(shù)a >= 1，b > 1，如果一個(gè)算法的整體計(jì)算規(guī)模 T(n)?=??a T(n / b) + f(n)，那么則有如下規(guī)律：
假設(shè)兩個(gè)長度為n的大整數(shù)相乘，整體運(yùn)算規(guī)模是T(n) 。
根據(jù)剛才得到的結(jié)論，兩個(gè)大整數(shù)相乘被拆分成四個(gè)較小的乘積：
所以在第一次分治時(shí)，T(n)和T(n/2)有如下關(guān)系：
T(n) = 4T(n/2) + f(n)
其中f(n)是4個(gè)乘積結(jié)果相加的運(yùn)算規(guī)模，f(n)的漸進(jìn)時(shí)間復(fù)雜度很明顯是O(n)。
把這個(gè)關(guān)系帶入到master定理的公式 T(n)?=??a T(n / b) + f(n) 當(dāng)中，
此時(shí)?a=4， b=2。
此時(shí)，把a(bǔ)和b的值，以及f(n)的時(shí)間復(fù)雜度帶入到master定理的第一個(gè)規(guī)律，也就是下面的規(guī)律：
發(fā)現(xiàn)正好符合條件。
怎么符合呢？推導(dǎo)過程如下：
所以我們的平均時(shí)間復(fù)雜度是：
—————END—————
1.微信群：
添加小編微信：color_ld，備注“進(jìn)群+姓名+公司職位”即可，加入【云計(jì)算學(xué)習(xí)交流群】，和志同道合的朋友們共同打卡學(xué)習(xí)！
2.征稿：
投稿郵箱：liudan@csdn.net；微信號(hào)：color_ld。請(qǐng)備注投稿+姓名+公司職位。
推薦閱讀
細(xì)數(shù)華為核心技術(shù)家底：華為真會(huì)被擊垮嗎？
如何使用 Lucene 做網(wǎng)站高亮搜索功能？
20張圖表達(dá)程序員的心酸
一個(gè)程序員父親的呼吁：不要教你的孩子從小學(xué)編程！
Python | 7招教你識(shí)別一個(gè)網(wǎng)站是否是Django后臺(tái)
月薪 50K 大牛整理！6 張 Python 圖譜，看完茅塞頓開！
程序人生公眾號(hào)是CSDN旗下有影響力的開發(fā)者自媒體之一。這是一個(gè)以程序員日常工作和生活緊密相關(guān)且垂直服務(wù)于程序員群體的自媒體平臺(tái)，掃描關(guān)注吧~
↓點(diǎn)擊“閱讀原文”，打開APP 閱讀更順暢
總結(jié)
以上是生活随笔為你收集整理的漫画：如何实现大整数相乘？（上）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 圣诞抽奖 | 2018年的开发者，经历了
- 下一篇： t十1最晚几点到账