論文を仕上げるときに欠かせない計算量の考察
ランダウ表記というのがあるそうですが
計算量算出の根拠とかコツとかについて語り合いましょう
関連スレ
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
【O(n)】計算量の評価方法について【O(log n)】
■ このスレッドは過去ログ倉庫に格納されています
2013/03/21(木) 17:35:37.80
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)のように足し算してもいいんでしょうか？
このページに
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 も入力時に与えられる変数で定数じゃないみたい。
全部読んでないけど、この問題に出てくる 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つにはまとめられないよ
関連の無い2つの変数があるなら
それは1つにはまとめられないよ
10デフォルトの名無しさん
2013/03/22(金) 02:05:41.98 O(n)をO(log n)に出来るアルゴリズムの変更をしたが、
1要素を処理する為の計算量がm倍に増えた
仮にnが10000の時、
計算量が100倍に増えても
速度的には等価ってことであってる？
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)と書くべき
MとNのどちらが支配的になるかがMとNの大きさによるのであれば
O(M+N)と書くべき
2013/03/22(金) 09:18:02.09
グラフ探索で頂点の数がM、辺の数がNの時に探索のオーダーをO(M+N)と表すのが有名な例。
14デフォルトの名無しさん
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が常に同じ次元なら別々に書く意味はそれ程ないと思うけど、別のものを使えるなら、
分けて書かないと意味が違ってくるような気がする。
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)
厳密な証明じゃないけど、入力(ソートする配列)のサイズを 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)
ではないのですか？
= 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)
ではないのですか？
2017
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)
アルゴリズムイントロダクションみたいな有名な本をちょっと見てみるといいよ。
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)
アルゴリズムイントロダクションみたいな有名な本をちょっと見てみるといいよ。
2013/03/25(月) 13:47:30.00
2013/03/25(月) 13:52:27.86
第三版日本語版が出てるらしい。
http://diary.overlasting.net/2013-01-02-2.html
- 第一回 [2013-01-24-1]
-- http://diary.overlasting.net/2013-01-24-1.html
- 第二回 [2013-01-31-1]
-- http://diary.overlasting.net/2013-01-31-1.html
- 第三回 [2013-02-07-1]
-- http://diary.overlasting.net/2013-01-31-1.html
http://diary.overlasting.net/2013-01-02-2.html
- 第一回 [2013-01-24-1]
-- http://diary.overlasting.net/2013-01-24-1.html
- 第二回 [2013-01-31-1]
-- http://diary.overlasting.net/2013-01-31-1.html
- 第三回 [2013-02-07-1]
-- http://diary.overlasting.net/2013-01-31-1.html
2013/03/25(月) 14:05:13.78
なんかリンクが可笑しいので訂正。
アルゴリズムイントロダクション 第3版の日本語版が出揃ってた
http://diary.overlasting.net/2013-01-02-2.html
アルゴリズムイントロダクション輪読会 01
http://diary.overlasting.net/2013-01-24-1.html
アルゴリズムイントロダクション輪読会 02
http://diary.overlasting.net/2013-01-31-1.html
アルゴリズムイントロダクション輪読会 03
http://diary.overlasting.net/2013-02-07-1.html
アルゴリズムイントロダクション輪読会 04
http://diary.overlasting.net/2013-02-14-1.html
アルゴリズムイントロダクション 第3版の日本語版が出揃ってた
http://diary.overlasting.net/2013-01-02-2.html
アルゴリズムイントロダクション輪読会 01
http://diary.overlasting.net/2013-01-24-1.html
アルゴリズムイントロダクション輪読会 02
http://diary.overlasting.net/2013-01-31-1.html
アルゴリズムイントロダクション輪読会 03
http://diary.overlasting.net/2013-02-07-1.html
アルゴリズムイントロダクション輪読会 04
http://diary.overlasting.net/2013-02-14-1.html
24デフォルトの名無しさん
2013/03/25(月) 14:06:31.10 NHNってLINE(ハ○ゲ)の会社か
なかなか良スレだと思うけど
逆に言えばこういうの語られる場所はほとんど無かったわけで
計算量の見積もりとか語りにくい地味な話題なんだろうな
>>3
計算量もわからないのにこのスレいるの？とか話終わらす奴もいるし適当だと思わん
実際計算量見積もりとかまでやりだしたらごちゃごちゃするぜ？
逆に言えばこういうの語られる場所はほとんど無かったわけで
計算量の見積もりとか語りにくい地味な話題なんだろうな
>>3
計算量もわからないのにこのスレいるの？とか話終わらす奴もいるし適当だと思わん
実際計算量見積もりとかまでやりだしたらごちゃごちゃするぜ？
2013/03/25(月) 16:19:10.51
迷路を解くアルゴリズムで
(出題される迷路は四角形でスタートとゴール以外の通路は全て繋がっていて
解答は一本道のみで浮いたループとかもないものとします)
１．各枝を順に探索して袋小路まで行ったら戻って続き(左手の法則とか)
２．各通路を最小の四角形の部屋に分け三方を壁で囲まれている部屋を全て壁に置き換え(繰り返し)
３．もっと速い何か
のどれが最速かとか計算量で考察出来ますか？
(出題される迷路は四角形でスタートとゴール以外の通路は全て繋がっていて
解答は一本道のみで浮いたループとかもないものとします)
１．各枝を順に探索して袋小路まで行ったら戻って続き(左手の法則とか)
２．各通路を最小の四角形の部屋に分け三方を壁で囲まれている部屋を全て壁に置き換え(繰り返し)
３．もっと速い何か
のどれが最速かとか計算量で考察出来ますか？
2013/03/25(月) 19:56:39.91
>>25
> 逆に言えばこういうの語られる場所はほとんど無かったわけで
> 計算量の見積もりとか語りにくい地味な話題なんだろうな
> 実際計算量見積もりとかまでやりだしたらごちゃごちゃするぜ？
いや、そういう積極的な意図や目的があって立てられたのならいいと思うよ。
ただ逃げるようにして立てられたのなら、結局同じだろと思ってただけで。
> 逆に言えばこういうの語られる場所はほとんど無かったわけで
> 計算量の見積もりとか語りにくい地味な話題なんだろうな
> 実際計算量見積もりとかまでやりだしたらごちゃごちゃするぜ？
いや、そういう積極的な意図や目的があって立てられたのならいいと思うよ。
ただ逃げるようにして立てられたのなら、結局同じだろと思ってただけで。
28デフォルトの名無しさん
2013/04/01(月) 21:14:09.47 唐突ですまんが、
nPrの計算量は、O(n!)で表すのか？
nPrの計算量は、O(n!)で表すのか？
2013/04/01(月) 21:34:18.21
>>28
O(n) でいいんじゃないの？
1) n! を計算するのに O(n) (for 文で 1 から n までを掛け合わせるだけ)
2) (n - r)! を計算するのに O(n) (手順は上と同じ。最大でも r = 0 の時で O(n))
トータルで O(n)
2) の (n - r)! の計算を先にやって覚えておいて、1) を計算するのに残りの n から n - r + 1 までの掛け算だけをやればもうちょっと手数は削減できるかも。結局 O(n) だけど。
O(n) でいいんじゃないの？
1) n! を計算するのに O(n) (for 文で 1 から n までを掛け合わせるだけ)
2) (n - r)! を計算するのに O(n) (手順は上と同じ。最大でも r = 0 の時で O(n))
トータルで O(n)
2) の (n - r)! の計算を先にやって覚えておいて、1) を計算するのに残りの n から n - r + 1 までの掛け算だけをやればもうちょっと手数は削減できるかも。結局 O(n) だけど。
2013/04/01(月) 22:25:38.26
質問は、たぶん nPr の値を計算するのに必要な計算量ではなく、
ある計算をするのに必要な計算回数などが nPr 回と見積もられたら、
ビッグ・オー記法では O(n!) になるのか、という事だと思う。
ある計算をするのに必要な計算回数などが nPr 回と見積もられたら、
ビッグ・オー記法では O(n!) になるのか、という事だと思う。
2013/04/02(火) 04:21:53.96
O(nPr)=O((n-r)!)
3228
2013/04/02(火) 12:45:51.992013/04/02(火) 12:54:06.97
O(nPr)=O(n!-r!)
2013/04/03(水) 16:50:10.99
nPrは
O(n!)
O(n!)
2013/04/13(土) 23:55:40.31
マジレスするとnPr=O(n^r)
38デフォルトの名無しさん
2013/05/12(日) 11:23:49.97 BTreeで検索にかかる計算量を一定以下に見積もるために
(ほぼ)常にバランスを取る方法は色々あるようですが
それぞれの方法は同じ原理に基くものなのでしょうか？
(ほぼ)常にバランスを取る方法は色々あるようですが
それぞれの方法は同じ原理に基くものなのでしょうか？
2013/06/01(土) 17:39:32.93
OとΘの区別もついてない人がいるせいで
無駄な議論が増えていく
無駄な議論が増えていく
40デフォルトの名無しさん
2013/06/13(木) 09:48:20.28 O（オーダー）は計算量の上界、つまり
とある問題を解く場合に「これだけの時間があれば確実に解けます」という計算量を示す。
Ω（オメガ）は計算量の下界、つまり
とある問題を解く場合に、「どんなに頑張ってもこの問題はこれだけの時間がかかります」
という計算量を示す。
とある問題を解く場合に「これだけの時間があれば確実に解けます」という計算量を示す。
Ω（オメガ）は計算量の下界、つまり
とある問題を解く場合に、「どんなに頑張ってもこの問題はこれだけの時間がかかります」
という計算量を示す。
2013/06/20(木) 12:04:09.45
lim[x→a]f(x)=0
lim[x→a]g(x)=0
とする。lim[x→a]f(x)/g(x)=0
となるときf(x)はg(x)の高度の無限小といい
f(x)=o(g(x))と書くんだよな。
lim[x→a]f(x)/g(x)が定数になるときO(g(x))とかく。
ちなみに（a_n）がaに収束する列とするときf(a_n)/g(a_n)については条件を満たさなくていいし
上極限をΩ(g(x))下極限をO(g(x))と定義してO(g(x))をΘ(g(x))で定義する場合もあるんだよな。
もちろんlim[x→a]f(x)/g(x)が収束すればΘ(g(x))=O(g(x))だけどな。
lim[x→a]g(x)=0
とする。lim[x→a]f(x)/g(x)=0
となるときf(x)はg(x)の高度の無限小といい
f(x)=o(g(x))と書くんだよな。
lim[x→a]f(x)/g(x)が定数になるときO(g(x))とかく。
ちなみに（a_n）がaに収束する列とするときf(a_n)/g(a_n)については条件を満たさなくていいし
上極限をΩ(g(x))下極限をO(g(x))と定義してO(g(x))をΘ(g(x))で定義する場合もあるんだよな。
もちろんlim[x→a]f(x)/g(x)が収束すればΘ(g(x))=O(g(x))だけどな。
■ このスレッドは過去ログ倉庫に格納されています
ニュース
- 【東京】わずか9平方メートル…都心に近い「極小」アパートが若者に人気 狭くても“住めば都” [煮卵★]
- 「外国人はもう日本を選ばなくなる」経営者たちが抱く深刻な懸念 ベトナム人実習生なしでは「成り立たない街」…【多文化共生企画】 [少考さん★]
- 【△】コンビニの鮭おにぎり、価格にネット衝撃「ついに…」 驚き続々「これはキツい…」「日本人を殺しに来てる」 ★2 [ぐれ★]
- 上野動物園の双子パンダ、1月末に中国に返還へ 国内でパンダ不在に ★2 [蚤の市★]
- 「ルンバ」製造のアイロボット、連邦破産法11条適用申請－近年収益減 [少考さん★]
- 【伊東市長選】「きょうは行きたくない」 落選の田久保眞紀 前市長が”取材拒否” 約束の場所に姿を現さず 最後まで誠実さを欠く [ぐれ★]
- 中国との関係『不安』6割超えwwwwwwwwwでも高市の中国対応は評価しているとのこと… [271912485]
- 高市早苗「2時間しか寝てない」まさか頑張ってるアピールではなく頭悪過ぎて国会準備に人より時間がかかるだけなのでは [517791167]
- 有名漫画家「差別するやつは、少なくとも正直者ではある。一方、「差別反対」を言うやつは大体嘘つき。」 [762037879]
- 【年金支給日】今日は偶数月の15日だ❗うおおおおおおおおおお★2🏡
- ＰＣってマジで来年値上げするの？いまのうちに買いだめしといたほうがええの？😲 [861717324]
- 【高市悲報】中国「だから事前通知してたやろ…」日本「ろ、論点をずらすな～！😡根拠を言えぇ！！」 [359965264]