读书人

[]极简单的代码时间复杂度分析

发布时间: 2012-04-17 15:06:33 作者: rapoo

[求助]极简单的代码时间复杂度分析
各位好,我的问题很简单,就是是否可以把c++中的一个乘法运算作为常数级的时间复杂度

按算法书上的解释,两个分别n位和m位的常数相乘,算法时间复杂度应为O(m*n)

也就是说,考虑算法:求A个int数的积,算法复杂度变为O(32^A),一下子变为指数级!而指数级照理来说是计算机难以承受的.

然而实际上,即便是求10000个数的乘积,根本也用不了多少时间.

求各位指导!谢谢

[解决办法]
两个分别n位和m位的常数相乘,算法时间复杂度应为O(m*n)
对于两个32位的整数相乘,事件复杂度为 O(32*32)=> O(1)
A个int相乘,就是每两个int相乘之和合并成一个int,所以 时间复杂度为 A*O(1)=>O(A).

而书上的意思是,保证精度.两个int相乘,就是64位的,而不是一般的两个int相乘还是int的那种
[解决办法]

探讨
感谢回答,那么这样的话是否可以认为:
两个32位的数相加和相乘,其时间复杂度均为O(1)?

[解决办法]
探讨

引用:
感谢回答,那么这样的话是否可以认为:
两个32位的数相加和相乘,其时间复杂度均为O(1)?

这个是不对的!

算法书里面讨论加法,乘法,除法,以及取余运算等的复杂度,是假设输入数字是n bits长的!

所以相加操作是O(n),而乘法操作是O(n^2)。所以你不能假设长度是32位,而是得考虑长度n是很大的情况才行

读书人网 >C++

热点推荐