計算算法的複雜度。 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))時間複雜度。