基數轉換的計算複雜度

將非常大的n位數轉換爲十進制表示的複雜度是多少？基數轉換的計算複雜度

我的想法是，重複整數除法的基本算法，其餘部分得到每個數字，將有複雜性，其中M(n)是乘法算法的複雜性;然而，這種劃分不是在2個n位數之間，而是在1個n位數和一個小常數之間，所以在我看來複雜度可能更小。

2015-02-09 Tanner

@xdavidliu：不需要花O（M（n））時間計算一個大整數的商和餘數10，線性時間就足夠了。 – tmyklebu 2017-12-23 14:59:55

@tmyklebu沒關係，是的，這是正確的 – xdavidliu 2017-12-23 15:15:43

您所描述的樸素鹼基轉換需要二次時間;你可以做一些bigint-by-smallint分區，其中大部分需要時間與n位bigint的大小成線性關係。

您可以在O（M（n）log（n））時間內進行基礎轉換，但是，通過選擇大致爲要轉換的數字的平方根的目標基礎的力量，（它可以通過牛頓方法在O（M（n））時間完成），並在兩半上遞歸。

2015-02-09 20:13:11 tmyklebu

我想我的問題是否由小數分割可以在線性時間O（n）或更少。例如，除以2或4是平凡的O（1）;有沒有一個O（n）算法除以10？ – Tanner 2015-02-09 20:37:06

如何除以2 O（1）？你必須移動所有的位，不是嗎？ – 2015-02-09 20:53:24

@坦納，是的，任何固定除數除以O（n），其中n是股息的長度。只需使用通常的長分法算法即可。允許任意的除數改變一切。 – dfeuer 2015-02-09 20:53:25

回答