问重复加法乘法的时间复杂度
EN

Stack Overflow用户

提问于 2017-09-09 14:03:52

回答 1查看 632关注 0票数 2

下面是我的教科书中关于分析不同乘法算法的时间复杂性的一个例子：

如果我们通过重复加法进行乘法：

4 * 7 = 7 + 7 + 7 + 7

时间复杂度为O(n*10^n)，其中n为数字。

当n是数字时，我对分析时间复杂性并不满意。有人能解释一下为什么是O(n*10^n)吗？

回答已采纳

发布于 2017-09-09 14:45:20

一个数字N有O(log )位数，其中log表示十进制对数。因此，添加N本身需要O(log )步骤，而这样做M次则需要O(M )步骤。对于O(N)中的M，得到了O(N log N)步骤。这一估计是根据数字计算的。如果要以数字n作为基，则必须将N替换为10^n，这将给出O(n 10^n)。

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/46131507

复制

相似问题

问重复加法乘法的时间复杂度EN