13/03/21 18:28:13.28 .net
計算量について基本的なことなんですが教えてください。
このページに
URLﾘﾝｸ(imoz.jp)
＞記録には O(C) が，シミュレートには O(T) がかかるので，全体としての計算量は O(C+T) となります
と書いてありますが、ループを並べる場合ってO(max(C, T))ではなくてO(C+T)のように足し算してもいいんでしょうか？
3:デフォルトの名無しさん
13/03/21 19:32:19.42 .net
「データ構造とアルゴリズム総合」のスレでいいじゃん
4:デフォルトの名無しさん
13/03/21 20:27:35.02 .net
アイちゃんまだー チンチン
5:デフォルトの名無しさん
13/03/21 22:57:18.98 .net
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
6:デフォルトの名無しさん
13/03/22 01:45:09.35 .net
O(定数+定数)=O(定数)
全部読んでないけど、この問題に出てくる C は定数の C じゃなくて、お客さんの数らしいんだよね。
で、C も T も入力時に与えられる変数で定数じゃないみたい。
7:デフォルトの名無しさん
13/03/22 01:45:47.23 .net
蟻本見たらループ回数が変数のループを並べる場合の計算量はO(N+M)みたいな足し算になってたよ
そりゃそう書く事に意味があるからね
8:デフォルトの名無しさん
13/03/22 01:48:26.58 .net
O(C+T)でなくてO(N)でよい
9:デフォルトの名無しさん
13/03/22 01:53:06.06 .net
==> [多変数の場合]
関連の無い2つの変数があるなら
それは1つにはまとめられないよ
10:デフォルトの名無しさん
13/03/22 02:05:41.98 .net
O(n)をO(log n)に出来るアルゴリズムの変更をしたが、
1要素を処理する為の計算量がm倍に増えた
仮にnが10000の時、
計算量が100倍に増えても
速度的には等価ってことであってる？
11:デフォルトの名無しさん
13/03/22 03:34:16.33 .net
何と何が「等価」なのかを聞きたいの？
12:デフォルトの名無しさん
13/03/22 09:17:21.24 .net
O(M+N)でM側が常にゴミ同然ならO(N)でいいだろうが
MとNのどちらが支配的になるかがMとNの大きさによるのであれば
O(M+N)と書くべき
13:デフォルトの名無しさん
13/03/22 09:18:02.09 .net
グラフ探索で頂点の数がM、辺の数がNの時に探索のオーダーをO(M+N)と表すのが有名な例。
14:デフォルトの名無しさん
13/03/22 09:38:08.05 .net
QuickSort の計算量の求め方が判らないんだけど
誰か解説して
15:デフォルトの名無しさん
13/03/22 09:39:37.84 .net
O(M+N)って例えばO( m^2 + n )や O( m + log(n) )という書き方できるの？
MとNが常に同じ次元なら別々に書く意味はそれ程ないと思うけど、別のものを使えるなら、
分けて書かないと意味が違ってくるような気がする。
16:デフォルトの名無しさん
13/03/22 10:02:34.23 .net
もちろんできるよ。
17:デフォルトの名無しさん
13/03/22 10:45:09.98 .net
>>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)
18:デフォルトの名無しさん
13/03/23 17:00:23.30 .net
>>15
できるとは思うが、大抵次元の低い方がゴミになるんじゃないかな
19:デフォルトの名無しさん
13/03/23 17:55:14.51 .net
>>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)
ではないのですか？
20:17
13/03/23 18:55:05.27 .net
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)
アルゴリズムイントロダクションみたいな有名な本をちょっと見てみるといいよ。
21:デフォルトの名無しさん
13/03/25 13:47:30.00 .net
>>17 >>20
ありがとうございます
以前なにかの本で読んだときは意味不明だったのですが
懇切丁寧な説明のおかげで多少理解が進みました
きっと前に見た本が糞だったのだと思います
>アルゴリズムイントロダクションみたいな有名な本をちょっと見てみるといいよ。
そうします
22:デフォルトの名無しさん
13/03/25 13:52:27.86 .net
第三版日本語版が出てるらしい。
URLﾘﾝｸ(diary.overlasting.net)
- 第一回 [2013-01-24-1]
-- URLﾘﾝｸ(diary.overlasting.net)
- 第二回 [2013-01-31-1]
-- URLﾘﾝｸ(diary.overlasting.net)
- 第三回 [2013-02-07-1]
-- URLﾘﾝｸ(diary.overlasting.net)
23:デフォルトの名無しさん
13/03/25 14:05:13.78 .net
なんかリンクが可笑しいので訂正。
アルゴリズムイントロダクション 第3版の日本語版が出揃ってた
URLﾘﾝｸ(diary.overlasting.net)
アルゴリズムイントロダクション輪読会 01
URLﾘﾝｸ(diary.overlasting.net)
アルゴリズムイントロダクション輪読会 02
URLﾘﾝｸ(diary.overlasting.net)
アルゴリズムイントロダクション輪読会 03
URLﾘﾝｸ(diary.overlasting.net)
アルゴリズムイントロダクション輪読会 04
URLﾘﾝｸ(diary.overlasting.net)
24:デフォルトの名無しさん
13/03/25 14:06:31.10 .net
NHNってLINE(ハ○ゲ)の会社か
25: 忍法帖【Lv=40,xxxPT】(1+0：5)
13/03/25 16:09:11.43 .net
なかなか良スレだと思うけど
逆に言えばこういうの語られる場所はほとんど無かったわけで
計算量の見積もりとか語りにくい地味な話題なんだろうな
>>3
計算量もわからないのにこのスレいるの？とか話終わらす奴もいるし適当だと思わん
実際計算量見積もりとかまでやりだしたらごちゃごちゃするぜ？
26:デフォルトの名無しさん
13/03/25 16:19:10.51 .net
迷路を解くアルゴリズムで
(出題される迷路は四角形でスタートとゴール以外の通路は全て繋がっていて
解答は一本道のみで浮いたループとかもないものとします)
１．各枝を順に探索して袋小路まで行ったら戻って続き(左手の法則とか)
２．各通路を最小の四角形の部屋に分け三方を壁で囲まれている部屋を全て壁に置き換え(繰り返し)
３．もっと速い何か
のどれが最速かとか計算量で考察出来ますか？
27:デフォルトの名無しさん
13/03/25 19:56:39.91 .net
>>25
> 逆に言えばこういうの語られる場所はほとんど無かったわけで
> 計算量の見積もりとか語りにくい地味な話題なんだろうな
> 実際計算量見積もりとかまでやりだしたらごちゃごちゃするぜ？
いや、そういう積極的な意図や目的があって立てられたのならいいと思うよ。
ただ逃げるようにして立てられたのなら、結局同じだろと思ってただけで。
28:デフォルトの名無しさん
13/04/01 21:14:09.47 .net
唐突ですまんが、
nPrの計算量は、O(n!)で表すのか？
29:デフォルトの名無しさん
13/04/01 21:34:18.21 .net
>>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) だけど。
30:デフォルトの名無しさん
13/04/01 22:25:38.26 .net
質問は、たぶん nPr の値を計算するのに必要な計算量ではなく、
ある計算をするのに必要な計算回数などが nPr 回と見積もられたら、
ビッグ・オー記法では O(n!) になるのか、という事だと思う。
31:デフォルトの名無しさん
13/04/02 04:21:53.96 .net
O(nPr)=O((n-r)!)
32:28
13/04/02 12:45:51.99 .net
>>29
ありがとうございます。
しかし、先ほどの質問は>>30の言う通り、「ある計算をするアルゴリズムの計算量がnPrとエスティメイトされたとき
ビッグ・オー記法ではO(n!)と表すのですか？それともO(n)ですか？」ということです。
>>31
本来はnPr=n!/(n-r)!ですよね？
33:デフォルトの名無しさん
13/04/02 12:54:06.97 .net
O(nPr)=O(n!-r!)
34:28
13/04/02 12:58:00.61 .net
>>33
それは実際に計算してみると違いますが、O記法ではそうなるということですか？
35:デフォルトの名無しさん
13/04/03 16:50:10.99 .net
nPrは
O(n!)
36:28
13/04/13 11:16:01.44 .net
>>35
カキコするのとても遅れましたが、ありがとうございます。
そう表記するのですね。
37:デフォルトの名無しさん
13/04/13 23:55:40.31 .net
マジレスするとnPr=O(n^r)
38:デフォルトの名無しさん
13/05/12 11:23:49.97 .net
BTreeで検索にかかる計算量を一定以下に見積もるために
(ほぼ)常にバランスを取る方法は色々あるようですが
それぞれの方法は同じ原理に基くものなのでしょうか？
39:デフォルトの名無しさん
13/06/01 17:39:32.93 .net
OとΘの区別もついてない人がいるせいで
無駄な議論が増えていく
40:デフォルトの名無しさん
13/06/13 09:48:20.28 .net
O（オーダー）は計算量の上界、つまり
とある問題を解く場合に「これだけの時間があれば確実に解けます」という計算量を示す。
Ω（オメガ）は計算量の下界、つまり
とある問題を解く場合に、「どんなに頑張ってもこの問題はこれだけの時間がかかります」
という計算量を示す。
41:デフォルトの名無しさん
13/06/20 12:04:09.45 .net
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))だけどな。
42:デフォルトの名無しさん
13/06/20 15:14:52.70 .net
Θ(g(x))=O(g(x))>Ω(g(x))
ですか？
43:デフォルトの名無しさん
13/06/21 00:58:33.29 .net
>>41
教科書丸写しして楽しい？
44:!ninja
13/11/10 14:23:28.68 .net
結局馬鹿いじりしたがるスレチの馬鹿ばっかりになったか
もういいよ
コミュ障ばっかりだからやめやめ
45:デフォルトの名無しさん
13/11/11 17:55:23.45 .net
おお
こんなスレ立ってたのか
46:デフォルトの名無しさん
13/11/11 22:39:54.14 .net
Oは命より重い
47:デフォルトの名無しさん
13/11/12 07:33:55.61 .net
スモールoの方が好きです
48:デフォルトの名無しさん
14/01/27 14:31:55.81 .net
無限大
49:デフォルトの名無しさん
15/02/05 18:48:53.91 Wisgh0P5.net
Do It Yourself
50:デフォルトの名無しさん
15/02/07 18:33:03.78 5foNN6B4.net
When in Rome do as the Romans do.の意味や和訳。 《ローマではローマ人のするようにせよ》 「郷に入っては郷に従う」
51:デフォルトの名無しさん
15/09/04 08:42:12.98 efXmgHpK.net
なあ、再帰関数好きな人いる？ [転載禁止]©2ch.net
ｽﾚﾘﾝｸ(tech板)
52:デフォルトの名無しさん
15/09/04 20:19:26.41 6EQzrIAR.net
クイックソートの空間計算量に対する無理解について。
53:デフォルトの名無しさん
15/12/08 05:31:39.05 4pAacKsE.net
最短経路問題を解く為のダイキストラの方法で使われるヒープに関して、計算量の解析結果からバイナリヒープよりフィボナッチヒープの方が速いと言う内容が論文等に記載されているが
実際にプログラムを作製するとバイナリヒープの方が速いとか
何故フィボナッチヒープのスピードが出ないのですか？等と言うQAをネット上で見かける。計算量解析は実行速度を表現出来ているのでしょうか？
54:デフォルトの名無しさん
15/12/08 23:35:39.36 VwS2Arsg.net
いわゆる「計算量」ってのは、だいたい演算の回数を指してる。
でも今時のコンピュータだと、ボトルネックになるのはだいたいメモリアクセスとかの通信で、演算じゃない。
だから実行速度を正確に反映するような指標じゃないんだよね。
他にメモリアクセスの回数とかを使う指標があって、そっちのほうが実際の速度に近くなる。
その路線で cache-oblivious とか cache-aware なアルゴリズムが作られた。
55:デフォルトの名無しさん
15/12/09 10:00:28.48 3EPxHLPC.net
ok
56:デフォルトの名無しさん
15/12/09 10:03:24.98 3EPxHLPC.net
スタック積むよりレジスタ渡しとか
57:デフォルトの名無しさん
15/12/15 16:41:44.14 hXE077iv.net
べき集合を生成するアルゴリズムの計算オーダーは指数O(2^n)とされていますが,
このアルゴリズムの計算量が指数なのは
①「生成する対象が指数個存在するため」
②「アルゴリズムの構造のため(つまり,アルゴリズムによってオーダーは変化する)」
この①、②の理由のどちらによるものなのですか？
よろしくお願いします.
58:デフォルトの名無しさん
15/12/15 18:59:25.97 GmzcEDm2.net
１
59:デフォルトの名無しさん
15/12/15 20:36:32.63 hXE077iv.net
>>58
素早い返信ありがとうございました
60:デフォルトの名無しさん
15/12/16 04:41:02.19 JxdBAlmf.net
そもそも2だとしたら
「この」アルゴリズムの～
と矛盾するので題意が成り立たない
つまり実は国語の問題だったのである
61:デフォルトの名無しさん
15/12/20 16:25:19.99 8RLYRFXT.net
さむすぎ
62:デフォルトの名無しさん
16/08/07 17:01:40.20 sg2m+nAp.net
>>57
63:デフォルトの名無しさん
16/08/26 15:22:07.02 4Tk0fahk.net
開平・開立のアルゴリズムって最速なのdeath？
64:デフォルトの名無しさん
17/01/08 21:33:16.56 5b4VWoeT.net
F(p, n, r) の計算量を教えてください。
n: 整数
p, r: 整数配列（インデックス0からn-1）
F(p, n, r):
if r[n] ≧ 0: return r[n]
if n == 0: q = 0
else: q = -∞, for i = 1 to n: q = max(q, p[i] + F(p, n-i, r))
return r[n] = q
65:デフォルトの名無しさん
17/01/08 21:33:49.00 5b4VWoeT.net
T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)
と解けばいいんですかね？
66:デフォルトの名無しさん
17/01/08 21:34:12.25 5b4VWoeT.net
T(n) = c1 + c2*n + T(n-1)
T(0) = c3
この漸化式の解を求めればいいんですかね？
67:デフォルトの名無しさん
17/01/08 21:34:50.14 5b4VWoeT.net
T(n)
=
[T(n) - T(n-1)] + [T(n-2) - T(n-3)] + … + [T(1) - T(0)] + T(0)
=
[c1 + c2*n] + [c1 + c2*(n-1)] + … + [c1 + c2*1] + c3
=
c1*n + c2*(1/2)*n*(n+1) + c3
=
Θ(n^2)
68:デフォルトの名無しさん
17/01/08 21:35:29.94 5b4VWoeT.net
以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。
69:デフォルトの名無しさん
17/07/20 19:12:09.58.net
もうこうういうの教えないんだな
70:デフォルトの名無しさん
17/10/11 13:56:46.10 nNLLKLnX.net
浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。
「上の挿入ソートの例のように、基本演算回数（比較回数）は入力サイズ n にのみ
依存するとは言えない。そこで、入力サイズ n の入力のうちでアルゴリズムが最も
多くの基本演算を必要とする入力を考えて、それに対する基本演算回数を、本書ではん、
サイズ n の入力に対するアルゴリズムの計算量（time complexity of an algorithm）と
呼ぶ。すなわち、最悪の場合を想定してアルゴリズムの計算量を定めていることになる。
このようにして定められたアルゴリズムの計算量 T はもちろん n にのみ依存する関数で
あるので T(n) と書ける。上の挿入ソートの例では T(n) = n*(n-1)/2 である。」
と書いてあります。
その後、マージソートのところには、
「マージソートの計算量は T(n) = O(n*log(n)) である」
と書いてあります。
T(n) は最悪の場合の計算量ですから、
T(n) = Θ(n*log(n)) が正しいのではないでしょうか？
ちなみに、浅野さんは、この本の最初のほうで O, Ω, Θ を定義しています。
もちろん、 f(n) ∈ Θ(n*log(n)) ⇒ f(n) ∈ O(n*log(n)) ですが。
71:デフォルトの名無しさん
17/10/11 13:57:29.93 nNLLKLnX.net
浅野さんは、挿入ソートの計算量を
O(n^2)
と書いています。
これも
Θ(n^2)
と書くべきですよね。
>>70
に引用したように、
「上の挿入ソートの例では T(n) = n*(n-1)/2」
ですから。
72:デフォルトの名無しさん
17/10/11 14:02:04.45 nNLLKLnX.net
T(n) を最悪の場合の計算量としたとき、
T(n) ∈ O(f(n))
と書くという場合はあるのでしょうか？
T(n) ∈ Θ(f(n))
とかならず書くことになると思うのですが。
73:デフォルトの名無しさん
18/03/05 21:18:11.90 aiLdZy6r.net
アルゴリズムイントロダクションのヒープソートのところに、
「サイズ n のヒープ上の MAX-HEAPIFY の最悪実行時間が Ω(lg n) であることを示せ。」
という問題があります。
最悪実行時間が Θ(lg n) であることはすぐに分かります。
なぜ、 Ω(lg n) であることを示せという問題なのでしょうか？
74:デフォルトの名無しさん
18/03/05 21:20:53.28 aiLdZy6r.net
最悪実行時間や最良実行時間については、 Θ 記法で書くのが自然だと思います。
75:デフォルトの名無しさん
18/03/06 01:54:50.88 bDrXTt4P.net
うぃ
76:デフォルトの名無しさん
18/05/23 20:13:51.20 Au5e7VGg.net
僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法 モニアレフヌノ』
ATFOT
77:デフォルトの名無しさん
18/07/05 01:30:31.86 RfoszcD2.net
K6W
78:デフォルトの名無しさん
18/07/08 12:58:38.88 MJ8iSrG7.net
どんな言語だろうが全部ソートすれば O(n*log(n)) で最小値や最大値を探すのは O(n)
この n と n*log(n) の差を無視できないなら
そもそも n と 100*n の差を無視するのもダメじゃないかと思う
79:デフォルトの名無しさん
18/07/08 14:27:51.99 l291c8sA.net
>>78
> この n と n*log(n) の差を無視できないなら
上の両者の比はnがどんどん大きくなれば幾らでも大きくなるが
> そもそも n と 100*n の差を無視するのもダメじゃないかと思う
この両者の比はnがいくら大きくなっても100のまま（100に収束するというべきか）
１行目と２行目とではnをどんどん大きくした時の漸近的挙動が全く違うのよ
その違いを理屈として理解する以前に感覚として納得できないならば、君には計算量に関するセンスが決定的に欠落している
80:デフォルトの名無しさん
18/09/30 20:17:50.44 VkRnSMR8.net
てｓｔ
81:デフォルトの名無しさん
19/05/22 12:11:36.06 1OSMRbFi.net
何に使ってますか？