新・アルゴリズムとデータ構造入門 Java編5:ソートと時間計算量

※有料会員になるとこの動画をご利用いただけます

＃01:ソートと時間計算量

このレッスンでは、ソートアルゴリズムの時間計算量について学び、より高速なソートアルゴリズムについて理解を深めます。

挿入ソートでは i 回目の平均移動回数が (i-1)/2 なので、全体での平均計算量は O(n^2) になります。

交換が不要であることがわかった時点でループを終了することで、最良計算量を O(n) にする方法もあります。