なっとく!アルゴリズム
あれもこれもアルゴリズム
アルゴリズムの速度は秒で表さない=ビッグオー記法
計算時間(時間計算量)の増加を式で示す
ビッグオー記法では最悪の場合(=最も時間がかかる場合)の時間計算量を示す
https://gyazo.com/4b13764990ee7e08d3b9d82de4fed6d5
時間計算量の増加のイメージ
https://gyazo.com/e20c5b59448d4915cce1255b2a2b8e41
巡回セールスマン
O(n!)の有名な例
この問題に対してスマートなアルゴリズムを定義することは不可能と言われる(総当たりしかない)
ソート
コンピュータのメモリは巨大な引き出し繋がったようなものをイメージする
配列とソートリスト
配列
連続したメモリ領域をあらかじめ確保して使用する
(デメリット)確保した領域以上に新たに要素が増えるときは別の領域を改めて確保する必要がある
(デメリット)あらかじめ確保した領域を使い切らなかったら無駄になる
要素の読み取りは○、要素の挿入&削除はX
読み取り対象のアドレスがわかっている(リストの場合は先頭から辿っていく必要がある)
配列ないの要素は全て同じ型でないといけない(intやdoubleなど)
最初にメモリを確保するから、かなmochi5o.icon
リンクリスト(リスト)
メモリ領域は連続している必要がない
リンクリストの要素は、それぞれ次の要素のアドレスを格納している(リンクしている)
(デメリット)新たに要素を挿入するのにスムーズに対応できる
メモリに空きがある限り確保した領域が足りない、とかがない
(デメリット)最後の要素を取り出そうとすると、最初の要素から順番にアドレスを辿っていく必要がある
要素の挿入&削除は○、要素の読み取りはX
一つ前の指し示す次の要素のアドレスを書き換えるだけですむ
ランダムアクセスとシーケンシャルアクセス(逐次アクセス)
ソートリストの場合はシーケンシャルアクセス
シーケンシャルアクセスは最初から順にアクセスすること
リンクリストの配列(配列でもリストでもないハイブリッドデータ構造)
Facebookの例
Aから始まるユーザー名を登録したリンクリスト、Bから始まるユーザー名を登録したリンクリスト…という風に26個のスロットを持つ配列で、スロットはそれぞれリンクリストを指している
選択ソート
要素の中で一番大きいものを探してリストの追加していく
要素の回数分計算が必要なのでそれほど高速ではない
クイックソートはあとの章にて
再帰
箱の中から鍵を探すたとえ
箱の中には別の箱が含まれていて、その箱の中にも箱が含まれている可能性がある
箱の中のどこかに鍵がある
Whileで解決する
調べる箱を積み重ねて山にする
箱を取り出して調べる
箱を見つけたら山に追加して後から調べる
鍵を見つけたら終了
再帰で解決する
箱の中に入っているものを全て調べる(関数1)
箱を見つけたら、箱の中に入っているものを全て調べる(関数1)
鍵を見つけたら終了
関数1は同じ処理である
関数が自分自身を呼び出す、これが再帰
再帰のメリットデメリット
再帰の方が人間が見て何をやっているかパッと分かり易い
パフォーマンスが悪くなることがある
再帰を使うときの注意
パフォーマンスに注意する
無限ループを回避するために基本ケースから書く
基本ケースとは再帰をしない条件の時の処理
再帰ケースと基本ケースを必ず組み合わせることになる
スタック
先入れ後出し
プッシュとポップ
全ての関数呼び出しはコールスタックに配置される
メモリの確保と合わせて解説されると非常にわかりやすかったmochi5o.icon
再帰におけるパフォーマンスの問題も、スタックを使うことで確保するメモリの量が大きくなりすぎるということがよくわかる
無限ループの再帰を実行してしまうと、再帰関数を呼び出すたびにスタック上のメモリを確保することを繰り返し、最終的にはスタックオーバーフローになる