【O(n)】計算量の評価方法について【O(log n)】
■ このスレッドは過去ログ倉庫に格納されています
計算量について基本的なことなんですが教えてください。 このページに http://imoz.jp/algorithms/imos_method.html >記録には O(C) が,シミュレートには O(T) がかかるので,全体としての計算量は O(C+T) となります と書いてありますが、ループを並べる場合ってO(max(C, T))ではなくてO(C+T)のように足し算してもいいんでしょうか? 「データ構造とアルゴリズム総合」のスレでいいじゃん このスレッドは天才チンパンジー「アイちゃん」が 言語訓練のために立てたものです。 アイと研究員とのやり取りに利用するスレッドなので、 関係者以外は書きこまないで下さい。 京都大学霊長類研究所 O(定数+定数)=O(定数) 全部読んでないけど、この問題に出てくる C は定数の C じゃなくて、お客さんの数らしいんだよね。 で、C も T も入力時に与えられる変数で定数じゃないみたい。 蟻本見たらループ回数が変数のループを並べる場合の計算量はO(N+M)みたいな足し算になってたよ そりゃそう書く事に意味があるからね ==> [多変数の場合] 関連の無い2つの変数があるなら それは1つにはまとめられないよ O(n)をO(log n)に出来るアルゴリズムの変更をしたが、 1要素を処理する為の計算量がm倍に増えた 仮にnが10000の時、 計算量が100倍に増えても 速度的には等価ってことであってる? O(M+N)でM側が常にゴミ同然ならO(N)でいいだろうが MとNのどちらが支配的になるかがMとNの大きさによるのであれば O(M+N)と書くべき グラフ探索で頂点の数がM、辺の数がNの時に探索のオーダーをO(M+N)と表すのが有名な例。 QuickSort の計算量の求め方が判らないんだけど 誰か解説して O(M+N)って例えばO( m^2 + n )や O( m + log(n) )という書き方できるの? MとNが常に同じ次元なら別々に書く意味はそれ程ないと思うけど、別のものを使えるなら、 分けて書かないと意味が違ってくるような気がする。 >>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) >>15 できるとは思うが、大抵次元の低い方がゴミになるんじゃないかな >>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) ではないのですか? 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) アルゴリズムイントロダクションみたいな有名な本をちょっと見てみるといいよ。 >>17 >>20 ありがとうございます 以前なにかの本で読んだときは意味不明だったのですが 懇切丁寧な説明のおかげで多少理解が進みました きっと前に見た本が糞だったのだと思います >アルゴリズムイントロダクションみたいな有名な本をちょっと見てみるといいよ。 そうします なかなか良スレだと思うけど 逆に言えばこういうの語られる場所はほとんど無かったわけで 計算量の見積もりとか語りにくい地味な話題なんだろうな >>3 計算量もわからないのにこのスレいるの?とか話終わらす奴もいるし適当だと思わん 実際計算量見積もりとかまでやりだしたらごちゃごちゃするぜ? 迷路を解くアルゴリズムで (出題される迷路は四角形でスタートとゴール以外の通路は全て繋がっていて 解答は一本道のみで浮いたループとかもないものとします) 1.各枝を順に探索して袋小路まで行ったら戻って続き(左手の法則とか) 2.各通路を最小の四角形の部屋に分け三方を壁で囲まれている部屋を全て壁に置き換え(繰り返し) 3.もっと速い何か のどれが最速かとか計算量で考察出来ますか? >>25 > 逆に言えばこういうの語られる場所はほとんど無かったわけで > 計算量の見積もりとか語りにくい地味な話題なんだろうな > 実際計算量見積もりとかまでやりだしたらごちゃごちゃするぜ? いや、そういう積極的な意図や目的があって立てられたのならいいと思うよ。 ただ逃げるようにして立てられたのなら、結局同じだろと思ってただけで。 唐突ですまんが、 nPrの計算量は、O(n!)で表すのか? >>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) だけど。 質問は、たぶん nPr の値を計算するのに必要な計算量ではなく、 ある計算をするのに必要な計算回数などが nPr 回と見積もられたら、 ビッグ・オー記法では O(n!) になるのか、という事だと思う。 >>29 ありがとうございます。 しかし、先ほどの質問は>>30 の言う通り、「ある計算をするアルゴリズムの計算量がnPrとエスティメイトされたとき ビッグ・オー記法ではO(n!)と表すのですか?それともO(n)ですか?」ということです。 >>31 本来はnPr=n!/(n-r)!ですよね? >>33 それは実際に計算してみると違いますが、O記法ではそうなるということですか? >>35 カキコするのとても遅れましたが、ありがとうございます。 そう表記するのですね。 BTreeで検索にかかる計算量を一定以下に見積もるために (ほぼ)常にバランスを取る方法は色々あるようですが それぞれの方法は同じ原理に基くものなのでしょうか? OとΘの区別もついてない人がいるせいで 無駄な議論が増えていく O(オーダー)は計算量の上界、つまり とある問題を解く場合に「これだけの時間があれば確実に解けます」という計算量を示す。 Ω(オメガ)は計算量の下界、つまり とある問題を解く場合に、「どんなに頑張ってもこの問題はこれだけの時間がかかります」 という計算量を示す。 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))だけどな。 Θ(g(x))=O(g(x))>Ω(g(x)) ですか? 結局馬鹿いじりしたがるスレチの馬鹿ばっかりになったか もういいよ コミュ障ばっかりだからやめやめ When in Rome do as the Romans do.の意味や和訳。 《ローマではローマ人のするようにせよ》 「郷に入っては郷に従う」 クイックソートの空間計算量に対する無理解について。 最短経路問題を解く為のダイキストラの方法で使われるヒープに関して、計算量の解析結果からバイナリヒープよりフィボナッチヒープの方が速いと言う内容が論文等に記載されているが 実際にプログラムを作製するとバイナリヒープの方が速いとか 何故フィボナッチヒープのスピードが出ないのですか?等と言うQAをネット上で見かける。計算量解析は実行速度を表現出来ているのでしょうか? いわゆる「計算量」ってのは、だいたい演算の回数を指してる。 でも今時のコンピュータだと、ボトルネックになるのはだいたいメモリアクセスとかの通信で、演算じゃない。 だから実行速度を正確に反映するような指標じゃないんだよね。 他にメモリアクセスの回数とかを使う指標があって、そっちのほうが実際の速度に近くなる。 その路線で cache-oblivious とか cache-aware なアルゴリズムが作られた。 べき集合を生成するアルゴリズムの計算オーダーは指数O(2^n)とされていますが, このアルゴリズムの計算量が指数なのは @「生成する対象が指数個存在するため」 A「アルゴリズムの構造のため(つまり,アルゴリズムによってオーダーは変化する)」 この@、Aの理由のどちらによるものなのですか? よろしくお願いします. ■ このスレッドは過去ログ倉庫に格納されています
read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる