Асимптотический анализ алгоритмов: как вставить k новых элементов в отсортированный список размера n во времени O (k log 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 log k + n). k - количество списков. n - общее количество элементов во всех списках (n = n1 + n2 + ... + nk).

Объясните в асимптотическом анализе алгоритмов ???

Answer 1

Похоже, что он заслуживает флаг домашней работы, поэтому я не буду полностью его испортить, но просмотрите свои классические алгоритмы сортировки и не думайте об этом как о вставке элементов, подумайте об этом как о создании упорядоченного который содержит все элементы из обоих списков.