python - 两种算法的运行时复杂度(大 O 符号计算)

Question

这两种算法的大 O 表示法是什么:

def foo1(n):
    if n > 1:
        for i in range(int(n)):
            foo1(1)
        foo1(n / 2)

def foo2(lst1, lst2):
    i = 1
    while i < max(len(lst1), len(lst2)):
            j = 1
            while j < min(len(lst1), len(lst2)):
                j *= 2
            i *= 2

我认为 foo1 的运行时间复杂度是 O(n)，因为在那种情况下，如果我看到 for 循环，我可以这样做:

T(n) = O(n) + O(n/2) <= c*O(n) (c is const) for all n.

是吗？

我无法计算 foo2 的运行时间，有人可以帮助我知道如何计算吗？

谢谢...

Answer 1

1. 操作数T(n)等于T(n/2) + n。应用 Master theorem我们得到 T(n) = O(n)。简单来说，有 n + n/2 + n/4 + ... + 1 操作小于 2*n 并且是 O(n )。

2. 内层循环不依赖于外层循环，所以我们可以独立对待。 T(n) = O(log(maxlen) * log(minlen))。