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

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

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

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

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

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