Merge Sort や Quick Sort で出てきます。
Glossary
ページの中で出てくる言葉を、短く整理した一覧です。意味があやふやになったときに引けるようにしてあります。
目次
ことば
大きい問題を小さい問題に分けて解くやり方です。
たとえば 100 人を一気に処理するのではなく、50 人と 50 人に分けて考えるイメージです。
分けたあと、それぞれを解いて、最後に結果をまとめます。
最初は『半分ずつに分けて進める方法』と考えるとつかみやすいです。
Merge Sort や Quick Sort で出てきます。
ことば
同じ形の小さい問題を、自分でもう一度呼び出して解く書き方です。
たとえば 5 段の問題を、4 段の問題にして考える、というように小さくします。
必ず『ここまで来たら終わり』という止まる条件が必要です。
止まる条件がないと、ずっと呼び出し続けて止まりません。
再帰の考え方、ハノイの塔、Merge Sort などで使います。
ことば
一度出した答えを覚えておいて、同じ計算をもう一度しない方法です。
前に解いた宿題の答えをノートに書いておいて、次は見返すイメージです。
同じ計算が多いときに、とても効きます。
Fibonacci のページで差が見えやすいです。
再帰が遅いときの改善方法として出てきます。
ことば
同じ値どうしの元の順番を、そのまま残して並べ替えることです。
80 点の A さんと 80 点の B さんがいたとき、並べ替えたあとも A さんが前のままなら安定です。
同じ点でも元の並びに意味があるときに大事です。
A や B のラベルを付けると違いが見えやすくなります。
Bubble Sort、Insertion Sort、Merge Sort などと関係します。
ことば
比べるための目印になる値です。
Quick Sort では、まず 1 つ値を選んで、それより小さいものと大きいものに分けます。
英語では pivot と書かれることがあります。
基準値の選び方が偏ると、処理が遅くなることがあります。
Quick Sort の中心になる考え方です。
ことば
データが増えたときに、仕事の回数がどれくらい増えるかを表す目安です。
『今何秒かかったか』より『データが増えたらどれくらい大変になるか』を見ます。
O(n) や O(n²) は、その増え方を書く記号です。
最初は『増え方の違いを見るもの』と考えれば十分です。
計算量のページで最初に確認してください。
ことば
親と子の大小関係だけを守る、木の形のデータの持ち方です。
全部きれいに並んでいるわけではありません。
ただし、いちばん大きい値や小さい値を先頭から取り出しやすいのが強みです。
優先順位の高いものを先に取り出したいときに向いています。
Heap Sort や優先度付きキューで使います。