的两种算法（大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），因为在这种情况下，对于所有的n

T（N）= O（N）+ O（N/2）< = C * O（n）的（c是常数）：如果我看到for循环我可以做到这一点。

是这样吗？

，我不能计算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))。