初心者に、計算量のオーダーについて教えたいのですが、
[1] ソート以外の、
[2] 面白く
[3] 理解が簡単な問題で、
[4] 複数の解くアルゴリズム(4つ以上)があり、
[5] [4]の計算量のオーダーがそれぞれ違う(以下の内、4つ以上を含むのが望ましい)
https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7#.E4.B8.80.E8.88.AC.E7.9A.84.E3.81.AA.E3.82.AA.E3.83.BC.E3.83.80.E3.83.BC
ような問題をご存じでしたら教えて下さい。
難しい注文かとは思いますが、よろしくお願いいたします。
難しい。うん、難しいですねえ、本当に。
「並べ替え」と同列でよく題材に出されるのは「探索」だと思います。
ただ、並べ替えと違ってすっきりのは、事前に並べ替えておいたり、ハッシュ値を求めておくのは計算量の中には入れないのかい、という初学者にとってやや反則めいた部分があるところ。
あまり面白いとは言えず（[2]に違反）、4つ以上のアルゴリズムではない（[4]に違反）ので、題意にもそぐわず。
計算量のオーダーって、考え方としては大切だけどちょっと古いかなあ、と思います。
「古い」というのは、それを気にしなくちゃいけない場面が少なくなってしまったから、という意味です。
昔は、限られた領域の中で、比較演算（引き算）のコストが馬鹿にならなかったから、それを減らすことが限りある CPU リソースを有効に使う、という意味ではとても大切だった。
今は、CPU リソースがふんだんにあるので、比較演算よりも、それの準備にかかるコストの方が馬鹿にならない時代になったなあ、と。
極端なケースで言うと、あるデータを整列するときに、それを比較するための基準値は DB をアクセスすると手に入る状況。
比較用の関数を渡せるようなライブラリを備えているものが多いので、その比較用の関数の中で DB をアクセスに行っちゃう。
先に DB をアクセスしておいて、比較用の値はあらかじめ取得しておこうね、と。
＃ ん？ DB のアクセスにコストがかかるから、計算量のオーダが大切という話にもなる？
複数のアルゴリズムがあって、題材が面白い、という意味では、オセロやチェスの最適手を求める、というのが良いかな、とは思うのですが、面白いというところに達するまでの時間がかかり過ぎるのが難点。
MIN-MAX 法の話があって、取りうる手が木構造で表現できて、αβ刈りまでいって、ようやく計算量の話になる。
でも、どこで計算を打ち切るか、って部分が大きいので、ランダウの記法で表される計算量の理解には、すんなりとはいかないかな...
「ソート以外の」という [1]に違反しているんですが、並べ替えの過程を図示するの、って、初めて見たときに面白いと思ったんですけれど、どうでしょう。
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/index.html
100個の配列に、1～100までの数字が入っていて、十分にシャッフルされている。
横軸に、配列のインデックス。縦軸に、その値をとってプロットすると、並べ替える前は、プロットの点が一様に散らばっているように見えます。
そのグラフを、並べ替えの過程の途中で表示させると、何ステップで、どのように並べ替えられていくのかが目で見てわかります。
端から順番に並べ替えていくと、きれいに並んでいく様子が分かるけど、完了するまでに時間（ステップ数）がかかる。
よく分からないけど、全体的にざっくりと並べ替えていく方法だと、最初は並び替えられているのかどうか、よく分からないけど、ステップが進むにつれて、ざくざくときれいに整列していく。
計算量のオーダや、各アルゴリズムの計算過程、加えて、自分がひねり出すようなロジックは得てして効率は良くない、というところが直観的に理解できるのではないかな、と、思います。
１ピタゴラス数を重複さずに順番に見つける。
２素数を重複さずに順番に見つける。
３ＸＹ平面上の点を3点ずつ（線が交差する事なく）結ぶ。---できる図は1通りではありませんが、1つだけできたら終わりにする。---計算量は大体点数の４乗になります比例します。
tazikisai-mukou様、ありがとうございます。参考にいたします!!
難しい。うん、難しいですねえ、本当に。
「並べ替え」と同列でよく題材に出されるのは「探索」だと思います。
ただ、並べ替えと違ってすっきりのは、事前に並べ替えておいたり、ハッシュ値を求めておくのは計算量の中には入れないのかい、という初学者にとってやや反則めいた部分があるところ。
あまり面白いとは言えず（[2]に違反）、4つ以上のアルゴリズムではない（[4]に違反）ので、題意にもそぐわず。
計算量のオーダーって、考え方としては大切だけどちょっと古いかなあ、と思います。
「古い」というのは、それを気にしなくちゃいけない場面が少なくなってしまったから、という意味です。
昔は、限られた領域の中で、比較演算（引き算）のコストが馬鹿にならなかったから、それを減らすことが限りある CPU リソースを有効に使う、という意味ではとても大切だった。
今は、CPU リソースがふんだんにあるので、比較演算よりも、それの準備にかかるコストの方が馬鹿にならない時代になったなあ、と。
極端なケースで言うと、あるデータを整列するときに、それを比較するための基準値は DB をアクセスすると手に入る状況。
比較用の関数を渡せるようなライブラリを備えているものが多いので、その比較用の関数の中で DB をアクセスに行っちゃう。
先に DB をアクセスしておいて、比較用の値はあらかじめ取得しておこうね、と。
＃ ん？ DB のアクセスにコストがかかるから、計算量のオーダが大切という話にもなる？
複数のアルゴリズムがあって、題材が面白い、という意味では、オセロやチェスの最適手を求める、というのが良いかな、とは思うのですが、面白いというところに達するまでの時間がかかり過ぎるのが難点。
MIN-MAX 法の話があって、取りうる手が木構造で表現できて、αβ刈りまでいって、ようやく計算量の話になる。
でも、どこで計算を打ち切るか、って部分が大きいので、ランダウの記法で表される計算量の理解には、すんなりとはいかないかな...
「ソート以外の」という [1]に違反しているんですが、並べ替えの過程を図示するの、って、初めて見たときに面白いと思ったんですけれど、どうでしょう。
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/sort-algorithm/index.html
100個の配列に、1～100までの数字が入っていて、十分にシャッフルされている。
横軸に、配列のインデックス。縦軸に、その値をとってプロットすると、並べ替える前は、プロットの点が一様に散らばっているように見えます。
そのグラフを、並べ替えの過程の途中で表示させると、何ステップで、どのように並べ替えられていくのかが目で見てわかります。
端から順番に並べ替えていくと、きれいに並んでいく様子が分かるけど、完了するまでに時間（ステップ数）がかかる。
よく分からないけど、全体的にざっくりと並べ替えていく方法だと、最初は並び替えられているのかどうか、よく分からないけど、ステップが進むにつれて、ざくざくときれいに整列していく。
計算量のオーダや、各アルゴリズムの計算過程、加えて、自分がひねり出すようなロジックは得てして効率は良くない、というところが直観的に理解できるのではないかな、と、思います。
a-kuma3様、計算量のオーダーが昔ほど、重要ではなくなったとの指摘、ありがとうございます。
自分も普段、プログラミングする際、あまりオーダーについて考えてないなあと思っていました。
教えていただいたURLも、たいへん参考になりました。
計算量のオーダーという考え方があって、それを減らすアルゴリズムって大事だよね、ってところは知ってて欲しいところだと思います。
ただ、大半の人は、良く練られたアルゴリズムを使う側になっちゃうんですよね。
下手に自分で作り込むよりは、きちんと調べて、先駆者の資産を使うことが大切。
それを踏まえたうえで、並べ替えって、題材としては結果が分かりやすいし、一番面白いと思うんですよね。
計算量としては、良く知られたところだとクイックソートかマージソートが効率良いよね、というところなのですが、条件が加わると、また違ってきます。
ほぼ整列されているのだけれど、ほんのいくつかだけ並んでないのが紛れ込んでいる場合には、挿入ソートは割りと効率が良いとか。
ハードディスクのようにデータのアクセスにコストがかかるものを直接交換しなければいけない（整列のキーはメモリにキャッシュできるけど、並び替えたいデータは大きくてメモリに乗せられない、とか）場合には、比較が演算コストにつながるのではなく、データの入れ替えが演算コストに効くのだとか。
こういったことを「面白ぇなあ」と思える人が、次のステップに進んで、とんがったことにのめり込んでくれるんじゃないかな、と思います。
ソート以外だと、エイトクイーンが定番ですね。
条件の[4]までは満たしていると思います。
8クイーンのどのあたりが教材として優れているかといえば、
チェスの盤面がイメージしやすいため、
何をしようとしているか想像しやすいところにあります。
逆に高度なアルゴリズムでは、初見の生徒が
何をしているかパッと想像できないと思います。
また、一桁クイーンなら短時間で計算できるとか、
単純な解法ならコードが難解にはならないとか、
ゲームへの応用を想像できる（から面白い）、
などというのもメリットです。
それから、ご質問の意図とは異なってしまいますが、
ソートが実際にどのように使われているのか、
説明する方向でも面白くできるかもしれません。
（プログラミング自体に興味がなくても面白いと思えるかも）
たとえば、ブログのエントリが
日付順に並んでいるのもソート（の結果）ですし、
RPGの道具屋でアイテムが
価格順に並んでいるのもソートでしょう。
生徒側の心理を見たときに、
それが実用的にどのように使われているか分からないと、
自分の役に立つと思えず、興味も湧かないのだと思います。
dev2様、ありがとうございます。8クイーン問題、了解です。
ソートについては、学生は教育学部が多く、あまりというかほとんど、プログラミングに興味がないのだろうと思います。なので、実用面を話すのはいいですね。
普通の数学との関係からすると、変数の多い連立一次方程式の解法はどうでしょうか。
詳しいことは私も分かりませんが、いわゆるクラメルの公式は計算量が多くて使い物になりません。
みやど様、いつもありがとうございます。了解です。これはわかりやすくていいですね。
巡回セールスマン問題、と思ったが、最適解を求めるのが大変だから、出てきた解を評価できないなぁ。
あ、コメントのつもりが回答に・・・
takejin様、巡回セールス問題は、わかりやすいのに難しい問題で、アルゴリズムの重要性の説明には面白いと思います。ありがとうございます。
最近だとこんな記事がありましたね。
Atomの重要なプリミティブの最適化 | コンピュータサイエンス | POSTD
http://postd.cc/optimizing-an-important-atom-primitive/
Atomというエディタで、テキスト内部の範囲を表現する「マーカ」という構造体の扱いによって処理速度が大きく変わってくるという内容です。
単にテキスト内部の位置を保持するだけのマーカの処理でも、数が多くなると計算量が問題になってくるわけです。
最近流行りのいわゆるビッグデータやディープラーニングなども大概データ量が多いので、常に計算量を意識しないと、まずまともに動きません。
なので計算量のオーダーの話が古い、なんてことはありませんよ。
さて上記のマーカの問題に戻りますが、「効率的な探索方法」のところで、探索木の中で22番目の位置を含む領域にアクセスするのがO(log(n))とされています。同じように22番めの要素にアクセスする場合でも、配列に格納して22番目に直接アクセスできればO(1)、配列ではなく隣接リストでデータを持っていて最初から一つずつたどる必要があればO(n)になります。
他にも例えば「全てのマーカの対を考え、そのマーカに重複する部分があれば出力しろ」といった問題をナイーブに処理するとO(n^2)になるでしょう。
上記の話は「一つの問題」ではないので、お望みの回答ではないかもしれません。
ただ個人的には、何に使うのかわからない呪術的なアルゴリズムを幾つか読み解くよりも、普段自分が書いている簡単なプログラムの計算量を確認したり、データを1億倍にした場合の悪夢を体験させたりした方が良い学びになるかと思います。
計算量を「特殊なアルゴリズムを利用する際に優劣を決めるためのもの」と考えるとつまらないですが、「プログラムが遅くて困ったときに見直すと、100倍以上の改善の可能性があるもの」と考えると面白いですよ。
ite様、興味深い記事のご紹介、ありがとうございます。了解です。
a-kuma3様、計算量のオーダーが昔ほど、重要ではなくなったとの指摘、ありがとうございます。
2015/07/22 21:34:39自分も普段、プログラミングする際、あまりオーダーについて考えてないなあと思っていました。
教えていただいたURLも、たいへん参考になりました。
計算量のオーダーという考え方があって、それを減らすアルゴリズムって大事だよね、ってところは知ってて欲しいところだと思います。
2015/07/22 22:17:42ただ、大半の人は、良く練られたアルゴリズムを使う側になっちゃうんですよね。
下手に自分で作り込むよりは、きちんと調べて、先駆者の資産を使うことが大切。
それを踏まえたうえで、並べ替えって、題材としては結果が分かりやすいし、一番面白いと思うんですよね。
計算量としては、良く知られたところだとクイックソートかマージソートが効率良いよね、というところなのですが、条件が加わると、また違ってきます。
ほぼ整列されているのだけれど、ほんのいくつかだけ並んでないのが紛れ込んでいる場合には、挿入ソートは割りと効率が良いとか。
ハードディスクのようにデータのアクセスにコストがかかるものを直接交換しなければいけない（整列のキーはメモリにキャッシュできるけど、並び替えたいデータは大きくてメモリに乗せられない、とか）場合には、比較が演算コストにつながるのではなく、データの入れ替えが演算コストに効くのだとか。
こういったことを「面白ぇなあ」と思える人が、次のステップに進んで、とんがったことにのめり込んでくれるんじゃないかな、と思います。