- 537 名前：デフォルトの名無しさん [2007/03/11(日) 01:10:19 ]
- 『定本Cプログラマのためのアルゴリズムとデータ構造』（近藤嘉雪 著）のP14に下のような文があります。
【以下抜粋】
次に，計算量の乗算について考えてみましょう。O(f(n))の計算量をもつループをO(g(n))回繰り返すとすると，全体の計算量は，
O(f(n))・O(g(n))＝O(f(n)g(n))
となります。たとえば，O(n)のループをn/2回繰り返すと全体でO(n2)の計算量になります。
【抜粋ここまで】
ここで疑問なんですが、なぜO(n)のループをn/2回繰り返すとO(n2)の計算量になるんでしょうか。
初歩的な質問で申し訳ないですがお願いします。
