finding/verifying 递归函数的大O表示法
finding/verifying big O notation of recursive function
函数:
函数乘法(x, y)
如果 y = 0:
return 0
z = 乘法(x, ⎣y/2⎦)
如果 y 是偶数：
return 2z
其他：
return x + 2z
问题：
"If the input is an m-bit number x and an n-bit number y, how long does it take to multiply x and y?"
我的逻辑:
需要 n 次递归调用才能达到基本情况*。退出每个函数调用需要 n 步，然后执行 2z 或 x + 2z。
因此，需要O(n2)时间。
这样对吗？
有人告诉我应该是 O(mn)，但我不相信。如果我错了，请解释原因。
*由于它重复将y除以2直到到达基本情况，因此递归调用的次数基于最接近y值以下的2的幂。由于二进制只是2的幂位，所以y的n位等于递归调用的次数。
有些情况下，除了最后一种情况（当 y 将为 0 时）外，您总是会在任何递归调用中执行 'x + 2z' 的计算。例如，multiply(5, 31) 等。
所以我认为最主要的是“+”操作。当数字很大时，加法不需要1个机器步。因此，我们必须计算将 x 个数字（m 位长）加到另一个数字上需要花费多少机器步骤。结果是 O(m) 步。
这就是为什么答案是 O(mn).
P.S。 '2z' 将采用静态步数，因为我们可以在数字末尾添加 0 并得到结果。想象一下这个数字非常大，我们将每一位都存储为数组的一个元素。所以我们可以将 0 推到数组的末尾，我们将得到操作 '2z' 的结果。
函数:
函数乘法(x, y)
如果 y = 0:
return 0
z = 乘法(x, ⎣y/2⎦)
如果 y 是偶数：
return 2z
其他：
return x + 2z
问题：
"If the input is an m-bit number x and an n-bit number y, how long does it take to multiply x and y?"
我的逻辑:
需要 n 次递归调用才能达到基本情况*。退出每个函数调用需要 n 步，然后执行 2z 或 x + 2z。
因此，需要O(n2)时间。
这样对吗？
有人告诉我应该是 O(mn)，但我不相信。如果我错了，请解释原因。
*由于它重复将y除以2直到到达基本情况，因此递归调用的次数基于最接近y值以下的2的幂。由于二进制只是2的幂位，所以y的n位等于递归调用的次数。
有些情况下，除了最后一种情况（当 y 将为 0 时）外，您总是会在任何递归调用中执行 'x + 2z' 的计算。例如，multiply(5, 31) 等。 所以我认为最主要的是“+”操作。当数字很大时，加法不需要1个机器步。因此，我们必须计算将 x 个数字（m 位长）加到另一个数字上需要花费多少机器步骤。结果是 O(m) 步。 这就是为什么答案是 O(mn).
P.S。 '2z' 将采用静态步数，因为我们可以在数字末尾添加 0 并得到结果。想象一下这个数字非常大，我们将每一位都存储为数组的一个元素。所以我们可以将 0 推到数组的末尾，我们将得到操作 '2z' 的结果。