計算量とBig-O記法 - 素人がプログラミングを勉強していたブログプログラマであればアルゴリズムに関する話で、O(n)だとかO(log n)だとか、O(n2)だとか、そういった記号を目にすることはよくあると思う。 なんとなく、log n < n < n2の順に計算量が増加していくとかそういうことも知っていると思うが、計算量の増加とは何か説明しろと言われると、なかなか難しいと思う。この記事では高校数学レベルでわかるように考えていきたい。 まず、計算にかかる時間を、nを入力のサイズとしてf(n)を計算にかかる最大時間を返す関数とすると、計算量一般を、O(f(n))という、入力に対する計算時間の増加率として定義することができる（より厳密には、f:R+ -> R+ where R+=[0,∞)で、a>bであればf(a) >= f(b)であるとき）。 g(n) = n ^ 2 はn = 1に対して1を返す一方、より増加率の低い h(n) = n + 100 は、n
