b*****7
发帖数: 31 | 1 请问Karatsuba algorithm analysis下面步骤是如何得出的？
3^logN => 3N^log3 |
|
i**********e
发帖数: 1145 | 2 看了看 topcoder 的讨论，第三题似乎是用 inclusion-exclusion principle 来排除
多余的组合，看来关系还是比较棘手的。出的题目也真是太难了，说要派 300 件
tshirt 给前 300 名，结果只有 150 人答对至少一题...
这轮看来是专门针对那些专做 topcoder 的选手，看看第一题的讨论就知道，听说要用
FFT 或者 Karatsuba algorithm 来做快速乘法。看了排第一名大牛级别的代码，还真
不是一般的复杂...
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
N**N
发帖数: 1713 | 3 Karatsuba不算复杂,大约是n^(log2 3) |
|
g**G
发帖数: 767 | 4 第一题如果面试时碰到，就自己写String multiplication呗，我是写好加法，cache1-
9的乘法结果，然后错位相加
如果想加速的话可以用Karatsuba乘法
第二题不会，搬小板凳听 |
|
e*******8
发帖数: 94 | 5 这题programming problems上有. 用vector，然后从最低位存到最高
位。加和乘都是用的256-进制的.
乘法给了两个算法：一个就是小学学的那种算法，另外一个是karatsuba算法. |
|
b*****7
发帖数: 31 | 6 请问Karatsuba algorithm analysis下面步骤是如何得出的？
3^logN => 3N^log3 |
|
|
c*******h
发帖数: 1096 | 8 3^logN = N^log3
具体见高一数学课本 |
|
|
