乘法需要单位时间吗? [英] Does multiplication take unit time?

问题描述

我有以下问题

在什么情况下可以将乘法视为单位时间 操作吗?

Under what circumstances can multiplication be regarded as a unit time operation?

但是我认为乘法一直被认为是单位时间.我错了吗?

But I thought multiplication is always considered to be taking unit time. Was I wrong?

推荐答案

这取决于N是什么.如果N是任意大位数的位数，则随着位数的增加，计算乘积会花费更长的时间.但是，在大多数编程语言和应用程序中，数字的大小限制为一定的合理位数(通常为32或64).在硬件中，这些数字是一步相乘的，而不取决于数字的大小.

It depends on what N is. If N is the number of bits in an arbitrarily large number, then as the number of bits increases, it takes longer to compute the product. However, in most programming languages and applications, the size of numbers are capped to some reasonable number of bits (usually 32 or 64). In hardware, these numbers are multiplied in one step that does not depend on the size of the number.

当位数是32的固定数时，那么谈论渐近复杂性就没有意义，并且无论您使用哪种算法，都可以像O(1)运算那样对待乘法.当像Java的BigInteger类那样可以任意地变大时，则乘法取决于这些数字的大小，存储它们所需的内存也取决于这些数字.

When the number of bits is a fixed number, like 32, then it doesn't make sense to talk about asymptotic complexity, and you can treat multiplication like an O(1) operation in terms of whatever algorithm you're looking at. When can become arbitrarily large, like with Java's BigInteger class, then multiplication depends on the size of those numbers, as does the memory required to store them.

这篇关于乘法需要单位时间吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！