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

1デフォルトの名無しさん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

31デフォルトの名無しさん2013/04/02(火) 04:21:53.96
O(nPr)=O((n-r)!)

32282013/04/02(火) 12:45:51.99
>>29
ありがとうございます。
しかし、先ほどの質問は>>30の言う通り、「ある計算をするアルゴリズムの計算量がnPrとエスティメイトされたとき
ビッグ・オー記法ではO(n!)と表すのですか?それともO(n)ですか?」ということです。

>>31
本来はnPr=n!/(n-r)!ですよね?

33デフォルトの名無しさん2013/04/02(火) 12:54:06.97
O(nPr)=O(n!-r!)

34282013/04/02(火) 12:58:00.61
>>33
それは実際に計算してみると違いますが、O記法ではそうなるということですか?

35デフォルトの名無しさん2013/04/03(水) 16:50:10.99
nPrは
O(n!)

36282013/04/13(土) 11:16:01.44
>>35
カキコするのとても遅れましたが、ありがとうございます。
そう表記するのですね。

37デフォルトの名無しさん2013/04/13(土) 23:55:40.31
マジレスするとnPr=O(n^r)

38デフォルトの名無しさん2013/05/12(日) 11:23:49.97
BTreeで検索にかかる計算量を一定以下に見積もるために
(ほぼ)常にバランスを取る方法は色々あるようですが
それぞれの方法は同じ原理に基くものなのでしょうか?

39デフォルトの名無しさん2013/06/01(土) 17:39:32.93
OとΘの区別もついてない人がいるせいで
無駄な議論が増えていく

40デフォルトの名無しさん2013/06/13(木) 09:48:20.28
O(オーダー)は計算量の上界、つまり
とある問題を解く場合に「これだけの時間があれば確実に解けます」という計算量を示す。

Ω(オメガ)は計算量の下界、つまり
とある問題を解く場合に、「どんなに頑張ってもこの問題はこれだけの時間がかかります」
という計算量を示す。

41デフォルトの名無しさん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))だけどな。

42デフォルトの名無しさん2013/06/20(木) 15:14:52.70
Θ(g(x))=O(g(x))>Ω(g(x))
ですか?

43デフォルトの名無しさん2013/06/21(金) 00:58:33.29
>>41
教科書丸写しして楽しい?

44!ninja2013/11/10(日) 14:23:28.68
結局馬鹿いじりしたがるスレチの馬鹿ばっかりになったか
もういいよ
コミュ障ばっかりだからやめやめ

45デフォルトの名無しさん2013/11/11(月) 17:55:23.45
おお
こんなスレ立ってたのか

46デフォルトの名無しさん2013/11/11(月) 22:39:54.14
Oは命より重い

47デフォルトの名無しさん2013/11/12(火) 07:33:55.61
スモールoの方が好きです

48デフォルトの名無しさん2014/01/27(月) 14:31:55.81
無限大

49デフォルトの名無しさん2014/11/09(日) 04:13:27.18ID:iOEsToOb
Do As Infinity

50デフォルトの名無しさん2015/02/05(木) 18:48:53.91ID:Wisgh0P5
Do It Yourself

51デフォルトの名無しさん2015/02/07(土) 18:33:03.78ID:5foNN6B4
When in Rome do as the Romans do.の意味や和訳。 《ローマではローマ人のするようにせよ》 「郷に入っては郷に従う」

52デフォルトの名無しさん2015/09/04(金) 08:42:12.98ID:efXmgHpK
なあ、再帰関数好きな人いる? [転載禁止]©2ch.net
http://peace.2ch.net/test/read.cgi/tech/1439109993/

53デフォルトの名無しさん2015/09/04(金) 20:19:26.41ID:6EQzrIAR
クイックソートの空間計算量に対する無理解について。

54デフォルトの名無しさん2015/12/08(火) 05:31:39.05ID:4pAacKsE
最短経路問題を解く為のダイキストラの方法で使われるヒープに関して、計算量の解析結果からバイナリヒープよりフィボナッチヒープの方が速いと言う内容が論文等に記載されているが
実際にプログラムを作製するとバイナリヒープの方が速いとか
何故フィボナッチヒープのスピードが出ないのですか?等と言うQAをネット上で見かける。計算量解析は実行速度を表現出来ているのでしょうか?

55デフォルトの名無しさん2015/12/08(火) 23:35:39.36ID:VwS2Arsg
いわゆる「計算量」ってのは、だいたい演算の回数を指してる。
でも今時のコンピュータだと、ボトルネックになるのはだいたいメモリアクセスとかの通信で、演算じゃない。
だから実行速度を正確に反映するような指標じゃないんだよね。

他にメモリアクセスの回数とかを使う指標があって、そっちのほうが実際の速度に近くなる。
その路線で cache-oblivious とか cache-aware なアルゴリズムが作られた。

56デフォルトの名無しさん2015/12/09(水) 10:00:28.48ID:3EPxHLPC
ok

57デフォルトの名無しさん2015/12/09(水) 10:03:24.98ID:3EPxHLPC
スタック積むよりレジスタ渡しとか

58デフォルトの名無しさん2015/12/15(火) 16:41:44.14ID:hXE077iv
べき集合を生成するアルゴリズムの計算オーダーは指数O(2^n)とされていますが,
このアルゴリズムの計算量が指数なのは
@「生成する対象が指数個存在するため」
A「アルゴリズムの構造のため(つまり,アルゴリズムによってオーダーは変化する)」
この@、Aの理由のどちらによるものなのですか?
よろしくお願いします.

59デフォルトの名無しさん2015/12/15(火) 18:59:25.97ID:GmzcEDm2

60デフォルトの名無しさん2015/12/15(火) 20:36:32.63ID:hXE077iv
>>59
素早い返信ありがとうございました

61デフォルトの名無しさん2015/12/16(水) 04:41:02.19ID:JxdBAlmf
そもそも2だとしたら
「この」アルゴリズムの〜
と矛盾するので題意が成り立たない
つまり実は国語の問題だったのである

62デフォルトの名無しさん2015/12/20(日) 16:25:19.99ID:8RLYRFXT
さむすぎ

63デフォルトの名無しさん2016/08/07(日) 17:01:40.20ID:sg2m+nAp

64デフォルトの名無しさん2016/08/26(金) 15:22:07.02ID:4Tk0fahk
開平・開立のアルゴリズムって最速なのdeath?

65デフォルトの名無しさん2017/01/08(日) 21:33:16.56ID:5b4VWoeT
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

66デフォルトの名無しさん2017/01/08(日) 21:33:49.00ID:5b4VWoeT
T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

と解けばいいんですかね?

67デフォルトの名無しさん2017/01/08(日) 21:34:12.25ID:5b4VWoeT
T(n) = c1 + c2*n + T(n-1)
T(0) = c3

この漸化式の解を求めればいいんですかね?

68デフォルトの名無しさん2017/01/08(日) 21:34:50.14ID:5b4VWoeT
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)

69デフォルトの名無しさん2017/01/08(日) 21:35:29.94ID:5b4VWoeT
以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。

70デフォルトの名無しさん2017/07/20(木) 19:12:09.58ID:SAzDIjFD
もうこうういうの教えないんだな

71デフォルトの名無しさん2017/10/11(水) 13:56:46.10ID:nNLLKLnX
浅野孝夫著『アルゴリズムの基礎とデータ構造』を読んでいます。

「上の挿入ソートの例のように、基本演算回数(比較回数)は入力サイズ 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)) ですが。

72デフォルトの名無しさん2017/10/11(水) 13:57:29.93ID:nNLLKLnX
浅野さんは、挿入ソートの計算量を

O(n^2)

と書いています。

これも

Θ(n^2)

と書くべきですよね。

>>71

に引用したように、

「上の挿入ソートの例では T(n) = n*(n-1)/2」

ですから。

73デフォルトの名無しさん2017/10/11(水) 14:02:04.45ID:nNLLKLnX
T(n) を最悪の場合の計算量としたとき、

T(n) ∈ O(f(n))

と書くという場合はあるのでしょうか?

T(n) ∈ Θ(f(n))

とかならず書くことになると思うのですが。

74デフォルトの名無しさん2018/03/05(月) 21:18:11.90ID:aiLdZy6r
アルゴリズムイントロダクションのヒープソートのところに、

「サイズ n のヒープ上の MAX-HEAPIFY の最悪実行時間が Ω(lg n) であることを示せ。」

という問題があります。

最悪実行時間が Θ(lg n) であることはすぐに分かります。
なぜ、 Ω(lg n) であることを示せという問題なのでしょうか?

75デフォルトの名無しさん2018/03/05(月) 21:20:53.28ID:aiLdZy6r
最悪実行時間や最良実行時間については、 Θ 記法で書くのが自然だと思います。

76デフォルトの名無しさん2018/03/06(火) 01:54:50.88ID:bDrXTt4P
うぃ

77デフォルトの名無しさん2018/05/23(水) 20:13:51.20ID:Au5e7VGg
僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法 モニアレフヌノ』

ATFOT

78デフォルトの名無しさん2018/07/05(木) 01:30:31.86ID:RfoszcD2
K6W

79デフォルトの名無しさん2018/07/08(日) 12:58:38.88ID:MJ8iSrG7
どんな言語だろうが全部ソートすれば O(n*log(n)) で最小値や最大値を探すのは O(n)

この n と n*log(n) の差を無視できないなら
そもそも n と 100*n の差を無視するのもダメじゃないかと思う

80デフォルトの名無しさん2018/07/08(日) 14:27:51.99ID:l291c8sA
>>79
> この n と n*log(n) の差を無視できないなら

上の両者の比はnがどんどん大きくなれば幾らでも大きくなるが

> そもそも n と 100*n の差を無視するのもダメじゃないかと思う

この両者の比はnがいくら大きくなっても100のまま(100に収束するというべきか)

1行目と2行目とではnをどんどん大きくした時の漸近的挙動が全く違うのよ
その違いを理屈として理解する以前に感覚として納得できないならば、君には計算量に関するセンスが決定的に欠落している

81デフォルトの名無しさん2018/09/30(日) 20:17:50.44ID:VkRnSMR8
てst

新着レスの表示
レスを投稿する