算法的漸近分析：如何在時間O（k log k + n）中插入k個新元素到大小爲n的排序列表中

Question

此示例演示如何確定元素應插入到排序列表中的索引。雖然binarySearch（）用於定位存在的元素，但它也可用於確定不存在的元素的插入索引。

// Create a list with an ordered list of items 
List sortedList = new LinkedList(); 
sortedList.addAll(Arrays.asList(new String[]{"ant", "bat", "cat", "dog"})); 
// Search for the non-existent item int index = Collections.binarySearch(sortedList, "cow"); 
// -4 // Add the non-existent item to the list 
if (index < 0) { sortedList.add(-index-1, "cow"); } 

我怎麼不能插入時間O（k日誌k + n）的元素。 k是列表的數量。 n是所有列表中元素的總數（n = n1 + n2 + ... + nk）。

解釋算法的漸近分析？

Answer 1

這聽起來像是值得一個家庭作業標誌，所以我不會爲你完全破壞它，但審查你的經典排序算法，不要認爲它是插入元素，認爲它創建一個仍然有序列表包含來自兩個列表中的所有元素。