大數乘法

Question

在分析算法時，我看到我們通常假設乘法採取單個計算機指令。但是當這個數字的大小（以位數爲單位）時，這個假設並不適用。在最基本的乘法形式中，乘以兩個n位數通常是O（n^2）。在這種情況下，計算x^n（x增加到n的冪）的複雜度（就位操作而言）可能是什麼？

有了解釋的方法，複雜性對我來說似乎是在正指數（但不知道確切的數字的）

Answer 1

所使用的算法對課程的計算x^n的複雜性取決於用於計算功率，並且乘法。如果您通過平方計算每個Exponentiation的功率，則需要O（log n）次乘法。在每個步驟中，您要麼將一個數字平方，要麼將兩個數字相乘，並將其中一個平方。

如果x有d(x)數字，x^n有Θ（N * d（X））的數字，在最後一步，你方大量有關n/2*d(x)位（也可能是乘上數以較小的一個）和算法然後通過將重複的方塊x^(2^k)（如果2^k <= n < 2^(k+1)）與累加器相乘來完成。

設S(m)是平方一個m位數字號碼的費用（可以是或可以不是相同的成本相乘兩個任意m位數字號碼的M(m)）。該平方然後需要大約

S(2^(k-1)*d(x)) + S(2^(k-2)*d(x)) + S(2^(k-3)*d(x)) + ... 

工作。由於S(m) >= m，即在S(2^(k-1)*d(x))和2*S(2^(k-1)*d(x))之間。所以平方的工作是由最後一步控制的。對於x^(2^s)與累加器的乘法運算，情況同樣如此，最終的乘法運算在工作中占主導地位。最終累加器幾乎可以作爲重複正方形的大，所以通過反覆平方提高x到n次方的總成本是

Θ(M(2^k*d(x)), 

這是Θ(M(n*d(x)))。隨着天真的乘法 - M(m) = O(m^2) - 你會得到總成本O(n^2*d(x)^2)。使用更高級的乘法算法（Karatsuba，Toom-Cook，Schönhage-Strassen，...），您的複雜度會低得多，低於O(n*d(x)*log (n*d(x)) * log log (n*d(x)))。

當通過與x相乘，在步驟n迭代計算功率，讓M(m,k)表示一個m - 數位數目與k - 數位數目乘以的成本。由於的因素之一是始終x，總成本是

M(d(x),d(x)) + M(d(x),2*d(x)) + M(d(x),3*d(x)) + ... + M(d(x),(n-1)*d(x)) 

與成本M(m,k) = m*k教科書算法，這總計爲n*(n-1)/2*d(x)^2，所以總成本又是Θ(n^2*d(x)^2)。但常數因子大於重複平方的冪運算。

當你乘大大不同長度的數字，因爲經過幾次反覆發生在這裏，你不能 - 因爲據我所知 - 降低成本M(m,k)遠低於Θ(m*k) - 如果m < k，查看號碼爲1位數數字和r -digit數字（r*m <= k < (r+1)*m）的基數爲b^m，如果m足夠大，但您不能減少r因子，則可以使用更好的算法降低乘以「數字」的成本。所以這個算法的複雜度爲O(n^2*M(d(x)))，因此n^2不能被消除。

Answer 2

Wikipedia具有複雜時代的各種乘算法很好的概述。

要回答你的問題，假設天真的教科書方法乘以兩個m位數字（其複雜度爲O（m^2），並且通過將數字乘以n來提高權力的天真方法n倍，則有n個乘法，因此的O（n * m個^ 2）的複雜或簡單地（納米^ 2）

Answer 3

N R個ķO開銷：

O((log(n))^k) 

的log（n） - 比特n的表示形式

^k - 因爲將兩個n位數相乘的簡單算法的訟費爲O（n^2）