★★Java質問・相談スレッド161★★ ID:nAadkoiM

6名無しさん@Next2ch:2016/03/20(日) 16:27:41.87 ID:nAadkoiM

O はランダウの記号
「問題が無限に大きいときの値が」「定数倍の違いを除いてだいたいこんなもの」という意味(厳密な定義はググれ)
無限にという言葉が嫌なら n = 10^100000000000000 くらいを仮定すればいい

例えば 10n^2 + 4n + 2 という式があるとき n = 10^100000000000000 を代入すると
4n+2 は 10n^2 より 100000000000000 桁も小さいゴミなので無視できる
10n^2 の 10 も n = 10^100000000000000 と比べれば些細な違いなので無視する

だから 10n^2 + 4n + 2 = O(n^2)

1. 空間計算量はメモリ使用量だと思えばいい
バイト数でもビット数でもGBで数えてもなんでも構わない
なぜなら何を単位として数えても定数倍変わるだけだから
(ビット単位とGB単位ならたった80億倍しかかわらない n = 10^100000000000000 と比べれば微々たる違い)

2. 計算量を考えるときはまず「問題の大きさ」を定義する。一次元配列なら要素数 n を「大きさ」にすればいい
 二次元配列についての問題なら幅wと高さhの二つを「大きさ」としてもいいし
 全要素数 n = w*h を「大きさ」としてもいい。考えやすいように何かを自分勝手に採用すればいい

 次に空間計算量を求める場合「何が一番メモリを食うか」を考える
 ソートなら仮に要素数 n に対して 100^(1000n) 行のプログラムが必要ならば
 プログラム自体を格納するためのメモリのほうがワーキング領域よりたぶん大きい
 でも普通そんなことはないのでプログラムの大きさは無視し「テンポラリに確保する要素数」を採用する
 もちろん「テンポラリに確保するバイト数」でもいい。定数倍違うだけ

 あとはゴリゴリ文章題を解く
 「要素数 n の配列をこの方法でソートするとき、テンポラリに確保する要素数はいくつになりますか?」
 答えが 1000000 log(30n + 2) とかになったならこれを O(logn) と答えればよい


このIDをNGリストに追加する

今後このIDの書き込みやスレッドを表示したくない場合、以下のボタンをクリックしてください。
NGリストに追加

レスを書き込む