ｺﾝﾋﾟｭｰﾀｻｲｴﾝｽの授業をします｡初心者に､計算量のｵｰﾀﾞｰについて教えたいのですが､ [1] ｿｰﾄ以外の､ [2] 面白く [3] 理解が簡単な問題で､ [4] 複数の解…

難しい｡うん､難しいですねえ､本当に｡

｢並べ替え｣と同列でよく題材に出されるのは｢探索｣だと思います｡

ただ､並べ替えと違ってすっきりのは､事前に並べ替えておいたり､ﾊｯｼｭ値を求めておくのは計算量の中には入れないのかい､という初学者にとってやや反則めいた部分があるところ｡
あまり面白いとは言えず([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までの数字が入っていて､十分にｼｬｯﾌﾙされている｡
横軸に､配列のｲﾝﾃﾞｯｸｽ｡縦軸に､その値をとってﾌﾟﾛｯﾄすると､並べ替える前は､ﾌﾟﾛｯﾄの点が一様に散らばっているように見えます｡
そのｸﾞﾗﾌを､並べ替えの過程の途中で表示させると､何ｽﾃｯﾌﾟで､どのように並べ替えられていくのかが目で見てわかります｡
端から順番に並べ替えていくと､きれいに並んでいく様子が分かるけど､完了するまでに時間(ｽﾃｯﾌﾟ数)がかかる｡
よく分からないけど､全体的にざっくりと並べ替えていく方法だと､最初は並び替えられているのかどうか､よく分からないけど､ｽﾃｯﾌﾟが進むにつれて､ざくざくときれいに整列していく｡

計算量のｵｰﾀﾞや､各ｱﾙｺﾞﾘｽﾞﾑの計算過程､加えて､自分がひねり出すようなﾛｼﾞｯｸは得てして効率は良くない､というところが直観的に理解できるのではないかな､と､思います｡

ｿｰﾄ以外だと､ｴｲﾄｸｲｰﾝが定番ですね｡
条件の[4]までは満たしていると思います｡

8ｸｲｰﾝのどのあたりが教材として優れているかといえば､
ﾁｪｽの盤面がｲﾒｰｼﾞしやすいため､
何をしようとしているか想像しやすいところにあります｡

逆に高度なｱﾙｺﾞﾘｽﾞﾑでは､初見の生徒が
何をしているかﾊﾟｯと想像できないと思います｡

また､一桁ｸｲｰﾝなら短時間で計算できるとか､
単純な解法ならｺｰﾄﾞが難解にはならないとか､
ｹﾞｰﾑへの応用を想像できる(から面白い)､
などというのもﾒﾘｯﾄです｡

それから､ご質問の意図とは異なってしまいますが､
ｿｰﾄが実際にどのように使われているのか､
説明する方向でも面白くできるかもしれません｡
(ﾌﾟﾛｸﾞﾗﾐﾝｸﾞ自体に興味がなくても面白いと思えるかも)

たとえば､ﾌﾞﾛｸﾞのｴﾝﾄﾘが
日付順に並んでいるのもｿｰﾄ(の結果)ですし､
RPGの道具屋でｱｲﾃﾑが
価格順に並んでいるのもｿｰﾄでしょう｡

生徒側の心理を見たときに､
それが実用的にどのように使われているか分からないと､
自分の役に立つと思えず､興味も湧かないのだと思います｡