Frage

 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

What is the time complexity of this code? is it O(2mn)? Because creating "all" requires mn steps and also while requires mn steps

War es hilfreich?

Lösung

It is O((m*n)**2) because while loop is executed m*n times and min(all), all.remove(minimum) are O(n*m) operations.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top