アルゴリズムの漸近解析：時間nでソートされたリストnにk個の新しい要素を挿入する方法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

これは宿題のフラグが必要なように聞こえるので、私は完全にあなたのためにそれを台無しにしませんが、非常に古典的なソートアルゴリズムを見直し、要素を挿入するとは考えません。両方のリストのすべての要素を含むリスト。