★★Java質問・相談スレッド161★★ #6

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) と答えればよい


スパムを通報

このレスがスパム・荒らしである場合は以下のボタンをクリックして通報してください。
(同意できない意見などに反対票を投じる機能ではありません)
通報

このスレッドを全て表示


レスを書き込む