大整数乘法——分治算法的时间复杂度

大整数乘法的分治算法，通常采用 Karatsuba 算法或者 Schönhage-Strassen 算法。

对于 Karatsuba 算法，其时间复杂度为 $O(n^{\log_2 3})$，其中 $n$ 是大整数的位数。

对于 Schönhage-Strassen 算法，其时间复杂度为 $O(n \log n \log \log n)$，其中 $n$ 是大整数的位数。

因此，大整数乘法分治算法的时间复杂度在最坏情况下可以达到 $O(n^{\log_2 3})$ 或 $O(n \log n \log \log n)$。