【O(n)】計算量の評価方法について【O(log n)】

**デフォルトの名無しさん** · 2013/03/21(木) 17:35:37.80

論文を仕上げるときに欠かせない計算量の考察
ランダウ表記というのがあるそうですが
計算量算出の根拠とかコツとかについて語り合いましょう

関連スレ
O（n)のソートアルゴリズムを発見した
http://toro.2ch.net/test/read.cgi/tech/1212217022/

参考
http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%82%A6%E3%81%AE%E8%A8%98%E5%8F%B7

**デフォルトの名無しさん** · 2013/03/21(木) 18:28:13.28

計算量について基本的なことなんですが教えてください。
このページに
http://imoz.jp/algorithms/imos_method.html
＞記録には O(C) が，シミュレートには O(T) がかかるので，全体としての計算量は O(C+T) となります
と書いてありますが、ループを並べる場合ってO(max(C, T))ではなくてO(C+T)のように足し算してもいいんでしょうか？

**デフォルトの名無しさん** · 2013/03/21(木) 19:32:19.42

「データ構造とアルゴリズム総合」のスレでいいじゃん

**デフォルトの名無しさん** · 2013/03/21(木) 20:27:35.02

アイちゃんまだーチンチン

**デフォルトの名無しさん** · 2013/03/21(木) 22:57:18.98

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

**デフォルトの名無しさん** · 2013/03/22(金) 01:45:09.35

O(定数+定数)=O(定数)

全部読んでないけど、この問題に出てくる C は定数の C じゃなくて、お客さんの数らしいんだよね。
で、C も T も入力時に与えられる変数で定数じゃないみたい。

**デフォルトの名無しさん** · 2013/03/22(金) 01:45:47.23

蟻本見たらループ回数が変数のループを並べる場合の計算量はO(N+M)みたいな足し算になってたよ

そりゃそう書く事に意味があるからね

**デフォルトの名無しさん** · 2013/03/22(金) 01:48:26.58

O(C+T)でなくてO(N)でよい

**デフォルトの名無しさん** · 2013/03/22(金) 01:53:06.06

==> [多変数の場合]

関連の無い2つの変数があるなら
それは1つにはまとめられないよ

**デフォルトの名無しさん** · 2013/03/22(金) 02:05:41.98

O(n)をO(log n)に出来るアルゴリズムの変更をしたが、
1要素を処理する為の計算量がm倍に増えた

仮にnが10000の時、
計算量が100倍に増えても
速度的には等価ってことであってる？

**デフォルトの名無しさん** · 2013/03/22(金) 03:34:16.33

何と何が「等価」なのかを聞きたいの？

**デフォルトの名無しさん** · 2013/03/22(金) 09:17:21.24

O(M+N)でM側が常にゴミ同然ならO(N)でいいだろうが
MとNのどちらが支配的になるかがMとNの大きさによるのであれば
O(M+N)と書くべき

**デフォルトの名無しさん** · 2013/03/22(金) 09:18:02.09

グラフ探索で頂点の数がM、辺の数がNの時に探索のオーダーをO(M+N)と表すのが有名な例。

**デフォルトの名無しさん** · 2013/03/22(金) 09:38:08.05

QuickSort の計算量の求め方が判らないんだけど
誰か解説して

**デフォルトの名無しさん** · 2013/03/22(金) 09:39:37.84

O(M+N)って例えばO( m^2 + n )や O( m + log(n) )という書き方できるの？

MとNが常に同じ次元なら別々に書く意味はそれ程ないと思うけど、別のものを使えるなら、
分けて書かないと意味が違ってくるような気がする。

**デフォルトの名無しさん** · 2013/03/22(金) 10:02:34.23

もちろんできるよ。

**デフォルトの名無しさん** · 2013/03/22(金) 10:45:09.98

>>14
厳密な証明じゃないけど、入力(ソートする配列)のサイズを n として、パーティションのステップで n 、結果としてサイズ n/2 の配列が2つできる。2つのサイズ n/2 の配列に対してそれぞれクイックソートするから、合わせると

T(n) = n + 2T(n/2)

= n + 2{ n/2 + 2T(n/4) } = 2n + 4T(n/4)
= 2n + 4{ n/4 + 2T(n/8) } = 3n + 8T(n/8)
...
// 繰り返すと以下のようなパターンが見えてくる
...
= kn + 2^k * T(n / (2^k)) --------- (*)

になる。
T(n/(2^k)) の n / (2^k) が 1 になるとき、n = 2^k <---> k = log n

k = log n を (*) の式に戻してやると

= kn + 2^k * T(n / (2^k))
= n log n + n * T(1)
= O (n log n)

**デフォルトの名無しさん** · 2013/03/23(土) 17:00:23.30

>>15
できるとは思うが、大抵次元の低い方がゴミになるんじゃないかな

**デフォルトの名無しさん** · 2013/03/23(土) 17:55:14.51

>>17
= n log n + n * T(1)
= O (n log n)
じゃなくて

T(n)
= n log n + n * T(1)
↓
O ( T(n) )
= O ( n log n + n * T(1) )
= O (n log n)

ではないのですか？

17 · 2013/03/23(土) 18:55:05.27

O 記法は、ある定数Cがあって、n がある程度大きいときに常に以下の式が成り立つとき

f(n) < C * g(n) ---------- (*)

f(n) = O(g(n)) と表記する。ってのが定義だから、この場合は T(n) = O(n log n) であってる。

最後端折っちゃったけど、つづき
T(n) = n log n + n * T(1)

T(1) は入力サイズにかかわらず一定なので定数 d とする。

T(n) = n log n + d * n

n がある程度大きくなれば常に d < log n なので

T(n) = n log n + d * n < n log n + n log n = 2 n log n

整理すると

T(n) < 2 n log n

O記法に戻って f(n) を T(n)、C を2、g(n) を n log n と対応させると T(n) = O(n log n)
アルゴリズムイントロダクションみたいな有名な本をちょっと見てみるといいよ。