Web開発者ロードマップを学習する 第３章 アルゴリズムとデータ構造
はじめに
WEB DEVELOPER Roadmap 2021 に
webエンジニアが身につけておくべきスキルの順序が示されています。
このロードマップに沿って、各スキルの要点を抑えた記事を書きます。
WEB DEVELOPER Roadmap 2021 Introduction
- Git - Version control
- Basic Terminal Usage
- Data Structures & Algorithms
- Git Hub
- Licenses
- Semantic Versioning
- SSH
- HTTP/HTTPS and APIs
- Design Patterns
- Character Encodings
今回はアルゴリズムとデータ構造について学習します。
まとめた記事は今後リンク更新していきます！
アルゴリズムとは？
- 問題や課題を解決するための処理手順のこと
- プログラム作成の基礎知識となる
- どのプログラミング言語を学習しても共通して使える知識である
- アルゴリズムには代表的なもので、探索・ソート（整列）・数値計算などがある
アルゴリズムと計算量
• 単の計算量は時間計算量のこと指す
• 計算量からある程度の処理時間の目安がつく
• アルゴリズムの性能評価や比較が可能になる
| 種類 | 意味 |
|---|---|
| 時間計算量 | 処理時間の計算 |
| 空間計算量 | 記憶容量の計算 |
O記法(オー記法)
• 計算量を表したもの
• 実行されるアルゴリズムの処理時間や記憶領域を使用するのか評価する基準
データ量をnとする⬇️
| O記法 | 説明 | 例 |
|---|---|---|
| O(1) | nが２倍、３倍と何倍になっても計算量は一定 | •配列のインデックスへのアクセス •リストの先頭アクセス •ハッシュ探索法 |
| O(n) | nが２倍、３倍と増えると、計算量も比例して２倍、３倍増える | リニアサーチ |
| O(log n) | ｎが増えても、それほど計算量は増えない | バイナリサーチ |
| O(nlog n) | (log n)にnの計算量がかけられたもの | クイックソート |
| O(n^2) | nが２倍、３倍となると、計算量は４倍、９倍となる | •バブルソート •挿入ソート |
→計算量オーダーについて
※logがわからない人はこちら→対数関数とは？logの基礎から公式やグラフまで解説！
計算量・O記法について基本的な知識を知りたい方は以下がおすすめです。
→ 一週間で身につくアルゴリズムとデータ構造 アルゴリズムと計算量
→ 開発新卒に捧ぐ、基本のアルゴリズムと計算量
計算量の使い方や求め方をより詳しく知りたい方は以下の記事がおすすめです。
→計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜
探索
- 複数のデータから目的のデータを探し出す
- 検索エンジンもデータ探索が使われている
リニアサーチ（線型探索法）
• 先頭から順番に探索する
• 探しているデータが見つかれば探索終了
• データが見つからなければ見つからないという結果を出力する
• データの数が大きくなると探し出すまでに時間がかかる
• 計算量はO(n)
バイナリサーチ（二分探索法）
• 予め整列されているデータが対象（昇順または降順）
• 探索範囲を半分に絞りながら探索する
• 大量のデータを扱う場合線型探索法より探索が速い
• 計算量はO(log n)
手順
1 真ん中の要素を選択
2 真ん中のデータと目的のデータを比較する
3 比較から探索範囲を半分に絞る
4 目的のデータがなければ見つからないという結果を出力
ハッシュ探索法
• 計算式（ハッシュ関数）を使ってデータを計算し、計算結果と格納する場所を紐付ける
• 計算結果でデータの格納場所が特定できる探索法
• 計算結果の値はハッシュ値と呼ばれる
• 格納位置を重複させないようにしなければならない
• ハッシュ関数の設定に決まりはないが同じハッシュ関数を使用しなければならない
• 計算量はO(1)
ソート（整列）
- データを並び替えること（昇順、降順など）
- 処理速度は遅め、データが多い場合適さない
選択ソート（単純選択法）
• データの最小値を探し、先頭から順に並び替える
• 計算量はO(n^2)
バブルソート（単純交換法）
• 隣り合うデータを比較し、入れ替えを繰り返しソートする
• 単純だが、処理時間が遅い
• 計算量はO(n^2)
挿入ソート(単純挿入法)
• 整列済みデータと順番に比較
• 適切な位置にデータを挿入
• 計算量はO(n^2)
クイックソート
• 基準となるデータを指定し、そこから大小２つのグループに分けソートしていく
• 実行速度が早い
• 計算量はO(log n)
エキストテネスのふるい
• 素数を求めるアルゴリズム
手順
• ある数以下の全整数のデータを用意する
• 平方根以下の素数の倍数を取り除く
• 最後まで残った数を素数として出力
ユークグリッドの互換性
• 最大公約数を求めるアルゴリズム
エキストテネスのふるいとユークグリッドの互換性についてもっと知りたい方はこちら。
→一週間で身につくアルゴリズムとデータ構造 入門編6日目：アルゴリズムの例③
データ構造とは？
• データの集まりを管理する仕組み
• 各データを要素という
配列
• 添字（インデックス）を用いて複数のデータ（要素）並べて管理
• データはメモリ上に配置（予めメモリを確保）
• 要素数不変
• データを追加・削除する際は低速(要素をずらす必要があるため)
• インデックスを使用することで、各要素にアクセスできる(アクセスが速い)
リスト
• 添字（インデックス）を用いて複数のデータ（要素）並べて管理
• リストの種類： 単方向リスト、双方向リスト
• 要素数可変
• データを追加・削除する際は高速(次のデータ情報を書き換えるだけ)
• 要素を辿っていかないとアクセスできない（インデックスでアクセス不可 アクセスが遅い）
⬆️次のデータの格納場所の情報も保持
⬆️次のデータのだけでなく前のデータの格納場所の情報も保持
| メリット | デメリット | |
|---|---|---|
| 配列 | 各要素へのアクセスが用意、速い | 要素の追加・削除の処理時間がかかる |
| リスト | 要素の追加・削除の処理時間が早い | 要素を辿っていかなければならないので アクセスが遅い |
スタック(LIFO (Last In First Out)
• 格納したデータを最後から順番に取り出せるデータ構造
• イメージとしては、積み上げられた本。
| 用語 | 意味 |
|---|---|
| push(プッシュ) | スタックにデータを追加すること |
| pop(ポップ) | スタックからデータを取り出すこと |
キュー(FIFO (First In First Out)
• 格納したデータを最初から順番に取り出せるデータ構造
• イメージとしては、飲食店の行列。先に並んだ人が先に入店できる。
| 用語 | 意味 |
|---|---|
| enqueue(エンキュー) | キューにデータを追加すること |
| dequeue(デキュー) | キューからデータを取り出すこと |
| →スタックとキューを極める！ 〜 考え方と使い所を特集 〜 |
木構造
• 階層関係(親子関係)があるデータを木に見立てたデータ構造
| 用語 | 意味 |
|---|---|
| ルートノード | データの始まり |
| ノード | 各データ |
| 親ノード | それぞれのデータの１つ上の層 |
| 小ノード | それぞれのデータの１つ下の層 |
| リーフノード | 子ノードを持たないノード |
| エッジ | ノードを繋ぐ枝 |
二分探索木
• 子ノードの左側の値が小さく、右側が大きい値をもつ
• データを取り出す際には必ずルートから順にノードの大小を比較して探索する
今回はアルゴリズムとデータ構造の本当に初歩的なことをまとめていきました。 新しく学んだことがあれば追加更新していく予定です。 アルゴリズムとデータ構造はプログラミング言語に依存しない基礎知識なので学んでいて損しない思います！ 私もいつか効率的なプログラム書けるようになりたいですね。 この記事がアルゴリズムとデータ構造について勉強するきっかけになれば幸いです。
Discussion