Dia*_*ana 2 algorithm complexity-theory multiplication time-complexity execution-time
我有以下问题
在什么情况下可以将乘法视为单位时间运算？
但我认为乘法总是被认为是单位时间.我错了吗？
这取决于什么N.如果N是任意大数的位数,则随着位数的增加,计算产品需要更长的时间.但是,在大多数编程语言和应用程序中,数字的大小限制为一些合理的位数(通常为32或64).在硬件中,这些数字在一个步骤中相乘,而不依赖于数字的大小.
当位数是固定数,如32时,那么谈论渐近复杂度是没有意义的,并且你可以O(1)根据你正在看的任何算法将乘法视为一个操作.如果可以变得任意大,就像Java的BigInteger类一样,那么乘法取决于这些数字的大小,存储它们所需的内存也是如此.
只有在你对两个数字执行操作的情况下of numeric type(这里强调,不要进入二进制细节),你只需要假设正在执行的操作只是恒定的时间.
它没有被定义为单位时间,但更严格的是,即使我们增加数字的大小也不会改变的恒定时间间隔,但实际上计算确实利用微妙的更多时间来对大数字进行计算.这些通常被认为是微不足道的,除非乘以的数字太大BigIntegers in Java,等等.
但是,一旦我们开始执行二进制字符串的乘法运算,我们的复杂性就会增加,而朴素的方法会产生O(n ^ 2)的复杂性.
因此,为了简化,我们执行基于划分和征服的乘法,也称为Karatsuba的乘法算法,其复杂度为O(n ^ 1.59),它减少了乘法的总数,并增加了一些较少的乘法和一些补充.
我希望我没有误判这个问题.如果是这样,请提醒我,以便我可以删除此答案.如果我理解了这个问题,那么此处发布的其他答案似乎不完整.
| 归档时间： |
|
| 查看次数： |
509 次 |
| 最近记录： |