読者です 読者をやめる 読者になる 読者になる

分割統治の計算量

分割統治法の計算量を再帰式で書いたときにどうなるかのメモ:




サイズn/bの小問題a個に分割できるとき;

より,

となる.




また,サイズf(n)の小問題n/f(n)個に分割できるとき;

より,