計算機科学・情報科学の本
■ このスレッドは過去ログ倉庫に格納されています
0375名無しさん@お腹いっぱい。
2010/06/09(水) 02:47:42ID:yvlprKJK0> >>372
> 作図者は凸の様子は問題にしなかった、だけだと思うが。
> そもそも計算量の評価に関するかぎり、曲線の凹凸具合など関係ない。
> >>370 は本質がわからないか、>>373 のとおりか。
本質が分ってないのはお前の方だ
下に凸か上に凸かは問題サイズが大きくなって行くと
計算量の増え方がサイズの増え方より激しいか否かを表しており
計算量の漸近的振る舞いに関して図形として表現できる情報として最も重要なものの一つ
だから本来ならばO(n^k)のグラフはk<1, k=1, k>0の3通りを示す必要がある
そしてO(c^n)は同じ下に凸でもO(n^k) (k>1)より遥かに急激に増加する様子を示し、
O(log n)は逆に同じ上に凸でもO(n^k) (k<1)より遥かに緩やかに増加する様子を示す必要がある
その事に気付かず、指摘しても「本質がわからない」なんて強弁してるお前は
この作図者と同じく計算量の漸近的振る舞いを図的に示すとはどういう事なのかのポイントを何も理解していない
■ このスレッドは過去ログ倉庫に格納されています