2023.12.28

ソートと探索アルゴリズムの概要

marugotoyoten

cs50のYoutube動画「ソートと探索アルゴリズムの概要」について要点と要約をまとめました

３つの要点

要点１
選択ソートとバブルソートは、最悪の場合と最良の場合の実行時間がnの2乗です。
要点２
挿入ソートは、最悪の場合と最良の場合の実行時間がnの2乗とnです。
要点３
マージソートは、最悪の場合と最良の場合の実行時間がいずれもn log nです。

要約

ソートアルゴリズムの概要
CS50では、さまざまなソートアルゴリズムについて学びましたが、それぞれの詳細を覚えるのは難しいかもしれません。しかし、各アルゴリズムの核となる要素をまとめて説明し、理解と区別を助けます。

挿入ソートとマージソートの概要
挿入ソートは、要素をシフトして小さい要素のためのスペースを作り、ソートされた配列を要素ごとに構築します。最悪の場合の実行時間はnの2乗であり、最良の場合の実行時間はnです。マージソートは配列をより小さな部分配列に分割し、それらを正しい順序で結合します。最悪の場合と最良の場合の実行時間はいずれもn log nです。

探索アルゴリズムの概要
また、2つの探索アルゴリズムについても説明しました。線形探索は、配列を左から右にイテレートし、目的の要素を見つけようとします。最悪の場合の実行時間はnであり、最良の場合の実行時間は1です。バイナリ探索はソートされた配列を必要とし、分割統治法を使用して各イテレーションで要素の半分を排除します。最悪の場合の実行時間はlog nであり、最良の場合の実行時間は1です。

結論
ソートアルゴリズムは異なるアプローチと実行時間を持っていますが、バイナリ探索は線形探索に比べて大幅な改善を提供します。ただし、ソートされた配列が必要であり、追加の作業が必要になる場合もあります。これらのアルゴリズムを理解することで、ソートや探索の問題を効果的に解決することができます。

▼今回の動画