[10/18/2012] Challenge #104 [Hard] (Stack Attack) : dailyprogrammer 問題 あのDijkstraが発明した手法だそう。 説明 あなたは邪悪なエンジニアであり、D++という新しい言語を作ろうとしている。これはあなたのお気に入りの計算機科学者にちなんで"Dijkst…

アルゴリズム・イントロダクション軽い気持ちで図書館から借りてきたけど読み終わらないんじゃないのこれ。 関数の増加 入力が大きな時は、アルゴリズムの漸近的(asymptotic)な効率を調べるのが良い。 入力サイズの増加にともなって実行時間がどのように変化…

分割統治法 ソートすべきn要素の配列をn/2の部分列に分割する。 2つの部分列を再帰的にソートする。 ソートされた部分文字列をマージする。 実装（Ruby) 擬似コードと同じように実装しようとしたら配列の境界エラーでコケまくり。 Infinity = 2**30 def merg…

「アルゴリズム・イントロダクション 改訂2版」を読んでいる。 2章の挿入ソートを実装しつつ、ループ不変式や実行時間といったアルゴリズムの正当性に関する考え方がどのようなものかを検討する。参考：アルゴリズムイントロダクション 第2章の勉強会資料 挿…