python - 这些函数的运行时间是多少？

Question

运行时间是多少？

def a(n):
    if n % 2 == 0:
        return n
    else:
        return a(n/2)

我的猜测 T(n) = T(n/2) + 1，然后使用主定理。

---

这个功能怎么样：

def b(n):
    for i in range(n):
        print(a(i))

这是我的猜测。

T(n) = nT(n/2) + 1

Answer 1

第一个是 O(logN) 第二个是 O(NlogN)。

1）您每次迭代都将问题减半。所以你迭代的总次数是：

i 使得 2**i = N，在数学中 i = logN 以 2 为底。有 O(logN)

2）您正在遍历大小为 N 所以 O(N) 的整个列表，但您在每次迭代时都调用一个 logN 函数。所以我们调用了一个 logN 函数 N 次。这是 O(NlogN)。