分割統治とマスター定理の紹介

基本的な分割統治は，最悪実行時間をT(n)T(n)T(n)とすると， T(n)={O(1)(n=1)2T(n2)+O(n)(otherwise) T(n) = \begin{cases} O(1) &(n =1)\\ 2T(\frac{n}{2}) + O(n)&(otherwise) \end{cases} T(n)={O(1)2T(2n​)+O(n)​(n=1)(otherwise)​ という形で書き表すことができ，T(n)=O(nlog⁡n)T(n) = O(n \log n)T(n)=O(nlogn)であることが知られています このことは，図で書き表すことによりすぐにわかります．つまり，12\frac{1}{2}21​になっていくのでn=1n=1n=1にlog⁡n\log nlogn回の再帰でたどり着き，各深さで合計O(n)O(n)O(n)しかかからないのでO(nl