目录
实验1 利用减治法和分治法来处理同一个问题
一、实验目的
二、实验内容和要求
【俄式乘法函数原型及功能说明】
【核心函数实现代码及时间复杂度与空间复杂度分析】
(1)俄式乘法实现代码
(2)时间复杂度:O(log(底数为2)n)
(3)空间复杂度:无递归算法,为S(1)
【大整数乘法函数原型及功能说明】
(1)大整数乘法分治思想实现代码
(2)时间复杂度分析:上式一共需要进行2次xn0的乘法(AC、AD各一次)、2次yn0的乘法(AC、BC各一次)和3次加法,因而该算法的时间复杂度为