1.1 計算量

計算量(Complexity)とは

　計算量とは，あるアルゴリズムがどのくらい速く動作するか， つまり計算速度がどのくらいなのかを客観的に理解することが できる指標である．計算速度はコンピュータのスペックや，OS，言語，コンパイラ， コンパイラのオプションに依存する．
　計算量では，計算に必要な基本演算の数が登録されているデータ数nに対してどのように 増えるのかを表す．
　関数の計算量はオーダーという単位で扱い，O(f(n))，O(g(n))のように表記する．

具体例

　a,bを任意の有限の定数とすると，
O(a)=O(1)
O(an)=O(n)
O(an^2+bn+c)=O(n^2)
O(an+blog2(n))=O(n)
O(log2(n^3+4))=O(log2(n^3))=O(3log2(n))=O(log2(n))=O(log(n))

計算量の大小関係

O(1)＜O(log(n))＜O(√n)＜O(n^2)＜O(n^3)＜・・・＜O(n^a)＜O(2^n)＜O(3^n)＜・・・＜O(a^n)＜O(n!)