[動画まとめ]基本情報に出るアルゴリズム〜サーチ編〜

はじめに

今回は、前回に引き続き、アルゴリズムについての動画まとめ「サーチ(探索)編」です。前回同様、基本情報技術者試験でアルゴリズムの範囲を勉強していて、活字からイメージを得るのが難しいと感じたため、分かりやすく動画で解説してくれているものをまとめました。

YouTubeで公開されている動画から、なるべく5分以内で分かりやすいものを集めましたので、イメージしにくい方は、ぜひ参考にして頂ければと思います。

まずは二分探索法です。この探索方法は

効率良く見つかるが、あらかじめ整列させておく必要がある

という特徴があります。

続いて、線形探索法。これは、単純に一つずつ見ていき、目的のものが見つかれば終了する方法です。しかし、要素が1000兆個あれば、最大1000兆回計算する必要があるので、時間がかかる可能性があります。特徴としては、

単純で分かりやすいが、要素の数によっては時間がかかる

といったところかと思います。

ハッシュ表探索は、ハッシュ関数を使ってハッシュ表を作成し、データを格納しておく方法です。見つけるときに、ほぼ一発で見つけられるメリットがあるが、データが重複(シノニム)した場合に、二次的な処理として線形探索法等との併用が必要になることがあります。まとめると

少ない計算数で見つけられるが、ハッシュ表のデータ重複してしまうと時間がかかる可能性がある

という感じかと思います。

以上です。前回に続き、今回もまとめ系の記事にしましたが、自力で文章にして説明するよりも、分かりやすい解説をまとめて、ご紹介するのも良いかと考え、このような形にしてみました。

また、間違い等あれば、お気軽にコメントして頂けると嬉しいです。最後まで読んでいただき、ありがとうございました。

まえだ