您能否向我解释一下如何正确计算Karatsuba 算法的 O(n) ？
我读过它等于O(n^log_2(3))但我仍然不明白如何得出这个值。
首先，我对输入长度表示为n而不是表示有点困惑n + m，但我想这只是为了缩短。
我知道每个数字都在执行一个操作，这就是它的原因n。但是你能向我解释一下是如何log_2(3)计算的，为什么是O(n^log_2(3))而不是O(n log_n(3))？
问问题
54 次
您能否向我解释一下如何正确计算Karatsuba 算法的 O(n) ？
我读过它等于O(n^log_2(3))但我仍然不明白如何得出这个值。
首先，我对输入长度表示为n而不是表示有点困惑n + m，但我想这只是为了缩短。
我知道每个数字都在执行一个操作，这就是它的原因n。但是你能向我解释一下是如何log_2(3)计算的，为什么是O(n^log_2(3))而不是O(n log_n(3))？