sorting - リストを使用した挿入ソートの複雑さ?

Question

挿入ソートでは、配列を介して実装されている間に、既にソートされたリストの要素をシフトすることにより、ソートされた順序で要素を挿入する必要があります。配列を使用する代わりに、二重連結リストを使用すると、時間の計算量はどうなりますか?

時間の複雑さは O(n^2) になるのですか? なんで？n 要素の挿入を考慮すると、log(1) + log(2) + log(3) + ..... + log(n) - n 要素に対して n 回になるため、複雑さは O(nlogn) になります。

Answer 1

リンクされたリストへの挿入には、挿入ポイントを見つけるためにリンク構造をナビゲートする必要があるため、O(lg n ) ではなく O( n ) の時間がかかります。