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

运算次数T(n)等于T(n/2) + n。应用 Master theorem 我们得到 T(n) = O(n)。简单来说有n + n/2 + n/4 + ... + 1个操作小于2*n，就是O(n).
内层循环不依赖于外层循环，所以我们可以独立对待。 T(n) = O(log(maxlen) * log(minlen)).

运行两种算法的时间复杂度（大O符号计算）

Run-time Complexity for two algorithms (Big O notation calculation)

python

algorithm

runtime