マイナー、好きなアルゴリズム

Question

みなさんの好きなアルゴリズム、マイナーなアルゴリズムを教えてください

Answer 1

●好きなアルゴリズム

動的計画法による編集距離の算出
文字列同士がどの程度類似しているかを「何回の編集操作で一致させられるか」という数字で出します。
えらい時間のかかりそうな計算と思いきや、動的計画法という工夫により、文字列長の積に比例した時間で算出可能です（計算時間がO(mn)であると表現します）。
http://karel.tsuda.ac.jp/class/algoB/c13.html
このアルゴリズムの恩恵を最も受けているのは生物学者・医学者です。DNA同士の類似度、どのくらい変化したか、種が枝分かれしてから何万年ほど経ったかを見積もるのに使えるので。

●マイナーなアルゴリズム

Sunday法
テキスト中から文字列を見つけるアルゴリズム。一般的な情報カリキュラムではKMP法、BM法というのを習うだけでこのSunday法は習わないのですが、なかなか難解なKMP法・BM法にくらべて理解しやすいのに大抵処理も速いという「みんなもっとこれ知ってれば良いのに」的なアルゴリズムです。
http://fussy.web.fc2.com/algo/search4_bm.htm