【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が常に同じ次元なら別々に書く意味はそれ程ないと思うけど、別のものを使えるなら、
分けて書かないと意味が違ってくるような気がする。