最初の (n-root(n)) 要素がソートされる n 要素リストをソートできるアルゴリズムを開発する必要があります。はい、これは宿題です。
インターネットとstack-overflowに関するいくつかの調査の後、挿入ソートとバブルソートは、部分的にソートされた配列に最適であると考えています。このリンクは、挿入ソートがマージソートよりも優れていることを明確に示しています。宿題の答えとして挿入ソートを入れました。
しかし、漸近的複雑度分析を始めると混乱します。
挿入ソートの場合、少なくとも各要素を確認する必要があります。要素がソートされていない場合は、シフト/反転を行う必要があります。したがって、挿入ソートには O(n + m) が含まれます。ここで、m は総反転です。または、線形複雑性 O(n) を持つとも言えます。
マージソートの場合、ソートされていないルート（n）要素に対してマージソートを実行する必要があります。これにより、ルート（n）ログ（ルート（n））の複雑さが生じます。さらに、ソートされたリストとマージする必要があります (これには O(n) が必要です)。したがって、複雑さは O(root(n) log (root (n)) + n) または O(n) になります。これは、n が root(n) log (root(n)) を支配するためです。
両方が同じ漸近的複雑さを持っているのはなぜですか? これは私の好奇心です。複雑さの計算の途中でどこかを間違えたのでしょう。
私は学生で、まだ学んでいます。助けていただければ幸いです。ありがとう。