問題はこちら 意訳が間違っていたらご指摘ください。 大問1 (a) 文字列の文字コードの和(のmod)をハッシュ値として使った場合、を達成できるか？ 1. Yes, 文字列の長さに基づいて均等にハッシュ値がばらける 2. Yes, 文字列中の文字に基づいて均等にハッシュ…

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

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