Karatsuba算法的特例
Special case of Karatsuba algorithm
我需要一些帮助来解决以下问题：
让我们考虑一个字长为 sqrt(n) 位的计算机。这意味着 2 个 sqrt(n) 位整数之间的任何乘法都是 O(1)。
问题是要证明在这台计算机上使用 Karatsuba 算法进行 2 个 n 位整数相乘的复杂度是 O(n^1.29).
我试过写一个递归关系，比如：
T(sqrt(n)) = 3T(sqrt(n)/2) + Θ(sqrt(n))
然后，通过用 n 替换 sqrt(n)，我最终得到：T(n) = 3T(n/2) + Θ(n)
给出 T(n) = Θ(n^1.58).
我不明白我哪里弄错了。
非常感谢！！
你说得对，原来的递推关系是T(n) = 3T(n/2) + Θ(n)；您犯的逻辑错误是直接将 n 替换为 sqrt(n).
您在这里必须做的是使用不同的停止条件 - 即T(m) = O(1) Ɐ m ≤ sqrt(n) 重新推导时间复杂度。给定的结果 T(n) = Θ(n^1.58) 是通过使停止条件等于某个小常数得出的，但这里不是这种情况。
让我们重复展开这个循环：
... 并应用修改后的停止条件：
...使用一些对数定律。因此我们得出：
...这是要求的结果。
我需要一些帮助来解决以下问题：
让我们考虑一个字长为 sqrt(n) 位的计算机。这意味着 2 个 sqrt(n) 位整数之间的任何乘法都是 O(1)。 问题是要证明在这台计算机上使用 Karatsuba 算法进行 2 个 n 位整数相乘的复杂度是 O(n^1.29).
我试过写一个递归关系，比如： T(sqrt(n)) = 3T(sqrt(n)/2) + Θ(sqrt(n))
然后，通过用 n 替换 sqrt(n)，我最终得到：T(n) = 3T(n/2) + Θ(n) 给出 T(n) = Θ(n^1.58).
我不明白我哪里弄错了。 非常感谢！！
你说得对，原来的递推关系是T(n) = 3T(n/2) + Θ(n)；您犯的逻辑错误是直接将 n 替换为 sqrt(n).
您在这里必须做的是使用不同的停止条件 - 即T(m) = O(1) Ɐ m ≤ sqrt(n) 重新推导时间复杂度。给定的结果 T(n) = Θ(n^1.58) 是通过使停止条件等于某个小常数得出的，但这里不是这种情况。
让我们重复展开这个循环：
... 并应用修改后的停止条件：
...使用一些对数定律。因此我们得出：
...这是要求的结果。