[求助]极简单的代码时间复杂度分析
各位好,我的问题很简单,就是是否可以把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的那种
[解决办法]
[解决办法]