gpt4 book ai didi

big-o - 为什么乘法是 n^2 次?

转载 作者:行者123 更新时间:2023-12-05 01:07:53 25 4
gpt4 key购买 nike

我读过诸如加法/减法之类的运算是线性时间,而乘法是 n^2 次。为什么这是真的?

不是加法floor(log n)次,什么时候 n 是较小的操作数?同样的论点适用于减法和乘法,如果我们编写一个程序来进行长乘法而不是将整数相加,那么复杂度不应该是 floor(log a) * floor(log b)其中 a 和 b 是操作数?

最佳答案

答案取决于什么是“n”。当他们说加法是 O(n) 和乘法(使用朴素算法)是 O(n^2) 时,n 是数字的长度,以位或其他单位为单位。使用此定义是因为任意精度算术是作为对“数字”列表(不一定以 10 为基数)的操作实现的。

如果 n 是要相加或相乘的数字,只要数字存储在 log n 空间中,对于正 n,复杂度将为 log n 和 (log n)^2。

关于big-o - 为什么乘法是 n^2 次?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17780719/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com