私はすべてのケースで（n logn）マージソートの複雑さを知っていますが、カットやパーティションが一方の側で4、他側で5のような不均衡の場合はどうですか？ 9素子アレイがので、この不均衡は、n LOGNから変更する複雑さを生じない,,, 4指標でカットを有するであろう...は、マージソートの複雑さに影響を与えます
などがNクイックソートのような任意の他の形態にログから、それが変化し最も良い場合はn lognですが、不均衡ピボットの原因がn lognからn 2にシフトします。
OK Merge Sortは、の場合はの場合、Θ（n。log n）の時間複雑さを持ちます。 これには、問題のサイズ「n」が奇数である場合が含まれます。
Big-Oh表記で時間の複雑さを考慮する場合、複雑さを最終的に計算するときに表示される可能性のある低次の用語が常に削除されるからです。 'n'が奇数である場合は、単純にいくつかの低次の項が含まれていますが、複雑さには影響しません。さらに明確にするために、次の例を参照してください。
などです。 'n'はタームの数、 'c'は分割とマージの一定時間です。マージソートのための複雑さを計算する上で
は、我々が得る：
CN（ログのn + 1）。 （ここで 'log n + 1'はツリー内のレベル数を与える）
Big-Ohで表現するとき、下位の項 '+1'と定数cは破棄されるので、Θ n）。
同様に、 'n'が奇数の場合は、この最終的な複雑さにいくつか追加の低次の項がありますが、破棄されるので問題はありません。あなたが疑って複雑さは増しません。希望は明らかです。
より良く理解を取得するには、このリンクを参照してくださいされていない場合：https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort
感謝を:) ...たくさん私をhelpe –