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

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)。