计算算法的复杂度。 Python

Question

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

假设你在你的all数据结构N成员，你每一次得到的O(N)min，然后除去它，再次O(N)，你这样做N倍，所以你会与结束O(N^2)时间复杂度。

可以转而有这样的：

def multi_merge_v1(lst_of_lsts): 
    all = [e for lst in lst_of_lsts for e in lst] 
    return(sorted(all)) 

具有O(N log(N))时间复杂度。