两种算法的运行时复杂性（大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))。