python - 计算这段具体代码的时间复杂度

Question

我正在尝试计算以下代码的时间复杂度。 lst_of_lsts 包含长度至多为 n 的 m 列表。

这就是我的想法:所有运行在 O(m*n) 中，最小值 = O(m*n)，remove = O(m *n).

总体 O(m*n)*O(m*n) = O(m^2*n^2)

我说得对吗？

 def multi_merge_v1(lst_of_lsts): 
      all = [e for lst in lst_of_lsts for e in lst] 
      merged = [] 
      while all != []: 
          minimum = min(all) 
          merged += [minimum] 
          all.remove(minimum) 
      return merged 

Answer 1

def multi_merge_v1(lst_of_lsts): # M lists of N
  all = [e for lst in lst_of_lsts for e in lst]
  # this is messy. Enumerate all N*M list items --> O(nm)

  merged = [] # O(1)
  while all != []: # n*m items initially, decreases in size by 1 each iteration.
    minimum = min(all) # O(|all|).
    # |all| diminishes linearly from (nm) items, so this is O(nm).
    # can re-use work here. Should use a sorted data structure or heap

    merged += [minimum] # O(1) amortized due to table doubling
    all.remove(minimum) # O(|all|)
  return merged # O(1)

整体复杂度似乎为 O(nm + nm*nm + 1) = O(n^2m^2+1)。哎呀。