递归函数Big-Oh复杂性

Question

Algorithm multiply(n, m)
PRE: n :: Integer, greater than or equal to 0
m :: Integer
POST: ????
RETURNS: the product, n * m
if (n = 0)
return 0
else if (n is even)
return multiply(n/2, m+m)
else
return m + multiply((n-1)/2, m+m)
endif

这个函数是O（logn），因为它在每个递归的情况下除以n吗？我正在为我的期中考试，我想确保我正确地做到这一点。先感谢您。

Answer 1

是的，你是对的。

虽然这是这种情况，但要注意，递归调用中的除数并不总是表示对数复杂度。