有效的算法來轉換整數爲十進制

Question

課題的CLRS算法書的31.1-12詢問以下問題：

給出一個有效的算法給定β位（二進制）整數轉換爲十進制表示。認爲如果長度至多爲β的整數的乘法或除法需要時間M(β)，則可以在時間Θ(M(β) lg β)中執行二進制到十進制的轉換。 （。提示：使用分而治之的方法，獲得具有獨立的遞歸結果的上半部和下半部

它要求時間Θ(M(β) lg β)這怎麼可能一個分而治之算法

Answer 1

爲了提示工作，它必定是M（β）是一個線性函數的情況，特別是那個M（β）≈2·M（β/ 2）

如果給出，有一個明顯的解決方案：Rec將數據分成幾部分，分別處理各部分，併合並結果。在遞歸級別k處將會有2個部分，每個部分的長度大約爲β/（2ᵏ）個比特，或者大約β總數。 k級的處理的總時間爲2ᵏM（β/（2ᵏ））≈M（β），其中O（M（β）·lgβ）爲何。爲了將β分成一個值並處理它的兩部分（v，w），設2·d或2·d + 1 =⌊β·ln（2）/ ln（10）⌋;讓v =⌊u/10ᵈ⌋和w = u-v·10ᵈ。