algorithm - 给定程序的递归关系

Question

考虑以下代码:

def f(int A):
     if A<256 :
         return A^(1/2)
     B = A^(1/2)
     C = B^(1/2)
     return (f(B)+f(C))mod 16

令 T(n) 表示该算法的时间复杂度。时间复杂度是:

a) T(n) = T(n/2) + T(n/4) + O(1)
b) T(n) = T(n^(1/2)) + T(n^(1/4)) +O(1)

根据我的说法，答案应该是 (b)，但给出的答案是 (a)。为什么这是答案，我哪里出错了？

Answer 1

我们通常谈论算法的复杂性与它的输入大小(即它的二进制表示的长度)有关，而不是输入的实际数值.

因此在这种情况下，输入大小为 n = log(A)，B 和 C 的二进制表示为 n/2 = log(A)/2 = log(A^(1/2)) = log(B) 和 n/4 = log(C)。这给了我们 (a) 中的关系。