algorithm - からつば乗数

Question

2 つの n 桁の正の整数を n 桁のカラツバ乗数で乗算しています。しかし、ほとんどの場合、副問題は依然として 2 つの n 桁の数を処理する必要があります。では、サブ問題に対して再帰的に n 桁のカラツバ アルゴリズムを再度使用する必要がありますか? このアプローチに冗長性はありますか? 何らかの方法で計算時間 (O(n^1.5)) を妥協しますか?

Answer 1

はい、同じアプローチを使用する必要があります。まだ十分に小さい数の場合は、数字を追加するオーバーヘッドが大きすぎる可能性があるため、他のアプローチを使用してください。

しかし、n 桁の数を掛ける必要があるのは事実ではありませんn/2。桁数を掛ける必要があります。それがこの方法の要点です。