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

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

Answer 1

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