わかったこと 文字列系のDPでよく使われるsub-problem prefix suffix substring 当然といわれれば当然。prefixとsuffixをどちらも使いそうな時はつまりsubstringである。 pseudo polynomial ナップザック問題： ナップザックに、重さ、価値の品物を入れるか…

ふと、まとまった時間でアルゴリズムを学び直したいと思った。 いつ転職しても(させられても)いいように。 MITのCS 6.006という講座がある。2011年の秋学期にMITで行われたアルゴリズムの授業であり、ほぼ全てのリソースが無料で公開されている。 G社に内定…

わかったこと Multiplicationの時間計算量 桁どうしの掛け算を行うときの時間計算量は、 で与えられる。 naiveなアルゴリズム: Karatsuba: DivisionはNewton Method + Multiplicationによって行われる を求めたいとき、と考え、 を先に求める。 を求めたいと…

表記: n: テーブルに入っている要素のサイズ m: テーブルのサイズ とする。 わかったこと Table Shrinkingでは、縮めるタイミングとサイズの係数をずらすのが良い テーブルの要素の追加・削除を繰り返し、n = m/2となったタイミングでテーブルを縮めるとする…

わかったこと ディクショナリはハッシュ表、Binary Search Treeの上位概念 Pythonでお馴染みのディクショナリ。 ディクショナリは insert delete search を行うもので、具体的な実装方法としてハッシュ表、Binary Search Treeがある。 ディクショナリとハッ…

トピック Insertion Sort Merge Sort Heap Sort Counting Sort Radix Sort わかったこと Insertion, Merge, Heap Sortは要素同士の大小関係の判定(Comparison)を行うが、これを行なっている限り最低でもの計算量がかかる。 理由 最低かかる計算量は、決定木…