動的計画法を用いるアルゴリズムの開発

>>67
多分わかっていると思われるのですが、１さんへの説明チックに書きます。
計算量において、/2とか+1とかいう概念は存在しません。
あくまでもオーダーなので、定数プラスや定数倍などは評価されません。
だから、nlognの場合も、「logの底って何だろう？」という事はナンセンスになります（何でもいいんです）
最終的に67さんの式は、結局O(kn^2)となります（なぜその式が出るのかの考察はまだしていませんが）。

>>1
実際にコードを書いてみて、そのfor文に注目すると、計算量は（概算で）出ます。
理論で証明しようとするととたんに面倒になりますが、もしそれを授業でやっていないなら
実際にソースコードを示して、そこから計算量を示す方法が現実的でしょう。
ちなみに、私は（証明はしてませんが）O(kn^2)だと思っています。

>>65
例えば動的計画法なんて、まず普通しらないし、実際の場面で応用する機会もまずありません。
しかし、使用できる道具がいくつかあるというのは選択肢を広げる上で非常に重要だし、
実際に、まず実世界で使わないと思っていた「巡回セールスマン問題」なども、流通業界の仕事で
使用したという経験もあります（時間軸に従ったグラフを利用）

過去の人たちが様々な証明を行ってくれている方法なので、応用できる場面にて
数学的考証をしなくてすむので、知っていればいるほど応用範囲が広がるかと。
決して「一流大学を出ているインテリだけが知ってろ」などと思わずに、
機会があれば学んで貰えればと思います。

とはいえアルゴリズムオタクってのは、応用になれば途端に使えなくなるのが
常ですよね。まさに頭でっかち。
そういう意味では、一般社会で経験を積んだプログラマこそが一流なのかもしれません。

酔っているから支離滅裂で失礼。