函数：
函数乘法(x，y(
如果y=0：
nbsp；返回0
z=乘(x，⎣y/2⎦(
如果y是偶数：
nbsp；返回2z
其他：
nbsp；返回x+2z
问题：
"如果输入是m位数字x和n位数字y，将x和y相乘需要多长时间？">
我的逻辑：
需要n递归调用才能到达基本情况*。退出每个函数调用并执行2z或x+2z需要n步骤。
因此，它需要O(n2(时间。
这是对的吗？
有人告诉我应该是O(mn(，但我不相信。如果我错了，请解释为什么。
*由于它重复地将y除以2，直到达到基本情况，递归调用的数量基于y值以下2的最接近幂。由于二进制只是2的幂的位，y的n位等于递归调用的次数。
在某些情况下，除了最后一种情况(y为0(外，您将始终在任何递归调用中执行'x+2z'的计算。例如，乘以(5，31(等。所以我认为最主要的是"+"运算。当数字很大时，执行加法不需要1个机器步骤。因此，我们必须计算将x个数字(长度为m位(与另一个数字相加所需的机器步数。结果是O(m(步。这就是为什么答案是O(mn(。
第页。S."2z"将采取静态数量的步骤，因为我们可以将0添加到数字的末尾并获得结果。想象一下，这个数字非常大，我们将每一位存储为数组的一个元素。因此，我们可以将0推到数组的末尾，我们将得到运算"2z"的结果。