- ベストアンサー
ランダウの記号
データ構造とアルゴリズムの分野では有名なオーダーがありますが。 f1(n)f2(n) = O(g1(n)g2(n)) O(f(n)) + O(g(n)) = O(max{ | f(n) | , | g(n) | }) この上記の公式(？)は有名だと思います。 問題は証明なんですが。。。 教授に質問しても, あいまいな返答しか返ってこず図書館でも証明が書いてある本がありませんでした。 簡単な証明でいいので教えていただけないでしょうか？ ご協力お願いします。
- 数学・算数
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
積の方は, f1(n) = O(g1(n)) かつ f2(n) = O(g2(n)) ですよね? O(・) の定義から f1(n) と g1(n), f2(n) と g2(n) の関係を書いて, そこから f1(n) f2(n) と g1(n) g2(n) の関係を示し, これが「うまく定数を選ぶ」とO(・) の定義を満たすことを言えば OK. 和の方も, まあ似たような感じです. ちょっと気をつけなければならないところはありますが, 流れはこんな感じです.
関連するQ&A
- ランダウの記号
ランダウの記号について初歩的な質問をさせていただきます。まず、 lim[x→a] f(x)/g(x) = 0 のとき、 f(x)=o(g(x)) (x→a) とかき、o( ) をランダウの記号という。 また、ランダウを記号を含む等式は、右辺で左辺を評価することを表す。 私はこのように理解しているということを記しておきます。 (1) cos(x) = 1+o(x) (x→0) は、 1+o(x) で cos(x) を評価するということを表しているのだと思いますが、" 1+o(x) で cos(x) を評価する"ということの意味が分かりません。 (2) o(x^2) = o(x) も(1)と同様に、 "o(x)でo(x^2)を評価する"ということの意味が分かりません。 (3)ランダウの記号に対して四則演算が成立する意味が分かりません。例えば、lim[x→0] x^m*o(x^n)/x^(m+n) = 0 といった具合です。ランダウの記号は「評価すること」を表すのであって、「何らかの数(0,1といったもの)」を表すのではないのでは？ 以上3点、宜しくお願いいたします。
- ベストアンサー
- 数学・算数
- スターリングの公式周りのことについて
現在私は大学3年で、ゼミでスターリングの公式について調べているのですが、 １、e(n/e)^n＜n!＜ne(n/e)^n ２、n!～√(2πn)(n/e)^n ３、n!=√(2πn)(n/e)^n*(1+1/12n+1/288n^2-1139/5140n^3+O(1/n^4)) O：ラージオーダー この3つに関して、3から2を、2から1を証明するように課題を出されたのですが、いまいちわかりません。 英文の数学書(TheBook)を和訳しながら読み進めていて、その中でヒントになりそうなのは F(n)～G(n)：lim[n→∞]F(n)/G(n)=1くらいしかありませんでした。
- ベストアンサー
- 数学・算数
- アルゴリズムの計算量問題で、
今、大学でアルゴリズムのクラスをとっているのですが、 教科書を読んでいて、感覚的には理解できているのですが、それを証明するとなるとどうしたらいいのか分からないところがあり、困っています。 それは、 2つの入力関数のうち、おおきい方を出力する関数をmax()、小さい方を出力する関数をmin()とするとき、 (1). max(f(x),g(x))=Θ(g(x)+f(x))は正しいか？ (2). min(f(x),g(x))=Θ(g(x)+f(x))は正しいか？ という問題なのですが、 1に関して言えば、 f(x)≦max(f,g) かつ g(x)≦max(f,g) 故に f(x)+g(x)≦2max(f,g) よって、定数1/2を掛けたf(x)+g(x)によってmax(f,g)は下から抑えられるため、max(f(x),g(x)) = Ω(f(x)+g(x)). また、max(f,g)は大きいどちらかの関数を選ぶため、f(x)かg(x) 故にmax(f,g)≦f(x) + g(x) よって、定数1を掛けたf(x)+g(x)によってmax(f,g)は上から抑えられるためO(f(x)+g(x)). 従って、Ω(f(x)+g(x))かつO(f(x)+g(x))より、max(f(x),g(x))=Θ(g(x)+f(x)). といった感じで1.の方は証明できると思います。 2.の問題では、O(f(x)+g(x))であるが、Ω(f(x)+g(x))にならないことを示せばいいと思うのですが、 1.と同様に、f(x)≧min(f,g) かつ g(x)≧min(f,g) 故に f(x)+g(x)≧2min(f,g) よって、定数1/2を掛けたf(x)+g(x)によってmax(f,g)は上から抑えられるため、max(f(x),g(x)) = O(f(x)+g(x)).と漸近的上界を求めることはできるのですが、 漸近的下界を反証する方法が思いつきません。 アドバイスをいただければ大変助かります。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- 計算機特論の問題がわかりません2
f(n),g(n)は漸近的に単調減少関数とする。 このとき、 max{f(n),g(n)}=θ(f(n)+g(n)) これを証明せよ、という問題なのですが 単調減少関数をどう使って証明すればいいのか わかりません。 誰か教えてください。
- 締切済み
- 数学・算数
- アルゴリズムの計算量O(ｎ)の証明
O()ビッグオーダについての証明問題なのですが どうすればよいのかわかりません。どなたか教えていただけませんか？ O(n*log n + n) = O(n*log n)を証明せよ f(n) ε O(n) f(n) > 0で、ある定数Cがあり ここでlim n→∞ f(n)/n ≦ C おそらく上を使うと思うのですが式変形を行っても 左辺-右辺で0にできません。ひょっとしたら はさみうち等を使うのでしょうか？ よろしくお願いいたします。
- 締切済み
- 科学
- 時間計算量とオーダーに関する問題がわかりません
1.サイズnの入力に対する、あるアルゴリズムの時間計算量f(n)が、F(n)=2^(2n)であるとする。 このとき、f(n)がO(2^n)でないことを示しなさい。 2.サイズnの入力に対する、あるアルゴリズムの時間計算量f(n)が、f(n)=c^(2n)であるとする。ただし、CはC>1の実数とする。このとき、F(n)がO(c^n)であるといえるか否かを示しなさい。 この二つの問題ですが、全然分かりません。 導出方法を教えてください。お願いします。
- ベストアンサー
- 数学・算数
- 繰り返しの方法を教えて下さい
初めて投稿します。 よろしくお願い致します SHINXの木工ＮＣを１年ほど導入しました。 自動プロというもので書いて動かすが基本となっており、 Ｇコード質問しても、ほどよい回答を得られずです。 困っているのは、丸ノコで凹面の削り出しを試みているのですが、 下記のように１本はなんとかできたのですが、 これをＸ方向に２ｍｍつづ、１００回動かしたいのです。 ぜひ、繰り返しの方法教えて下さい //////////////////////////////// O0100 N000001 M06 O0100 N000002 G53 O0100 N000003 G90 G00 Z 0.000 O0100 N000000 M92 O0100 N000001 G90 G00 Z 0.000 O0100 N000002 T9 O0100 N000003 M23 O0100 N000004 M03 O0100 N000005 S3600 O0100 N000006 G04 X1.0 O0100 N000007 M09 O0100 N000008 G61 O0100 N000009 G90 G00 G40 X-1205.110 Y-708.450 O0100 N000010 G92 X 100.000 Y 1900.000 O0100 N000010 M21 O0100 N000011 G90 G00 Z 83.000 O0100 N000012 G91 G01 Z-30.000 F2000 O0100 N000013 G01 Y-90.000 Z-13.000 F5000 O0100 N000019 G01 Y-90.000 Z-5.000 F5000 O0100 N000025 G01 Y-90.000 Z-4.000 F5000 O0100 N000031 G01 Y-90.000 Z-2.000 F5000 O0100 N000037 G01 Y-90.000 Z-2.000 F5000 O0100 N000043 G01 Y-90.000 Z-2.000 F5000 O0100 N000049 G01 Y-90.000 Z-1.000 F5000 O0100 N000055 G01 Y-90.000 Z-1.000 F5000 O0100 N000055 G01 Y-90.000 Z-0.000 F5000 O0100 N000055 G01 Y-90.000 Z-0.000 F5000 O0100 N000055 G01 Y-90.000 Z-0.000 F5000 O0100 N000055 G01 Y-90.000 Z-0.000 F5000 O0100 N000085 G01 Y-90.000 Z 1.000 F5000 O0100 N000091 G01 Y-90.000 Z 1.000 F5000 O0100 N000097 G01 Y-90.000 Z 2.000 F5000 O0100 N000103 G01 Y-90.000 Z 2.000 F5000 O0100 N000109 G01 Y-90.000 Z 2.000 F5000 O0100 N000115 G01 Y-90.000 Z 4.000 F5000 O0100 N000121 G01 Y-90.000 Z 5.000 F5000 O0100 N000127 G01 Y-90.000 Z 13.000 F5000 O0100 N000128 G90 G00 Z 83.000 O0100 N000129 G64 O0100 N000130 G218 O0100 N000131 S0 T100 O0100 N000132 G90 G00 Z 0.000 O0100 N000133 G219 O0100 N000134 G04 X2.0 O0100 N000135 M05 O0100 N000136 M92 M95 O0100 N000137 G65 P9900 L1 O0100 N000138 G53 O0100 N000139 G90 G00 Y 0.000 O0100 N000140 M07 O0100 N000138 M30 ///////////////////////////////// なんだか、場違いのところに質問したようで、申し訳ないです。
- 締切済み
- NC言語
- 計算量（オーダー）に関する計算
計算量に関する式で、わからないことがあります。 f(h)=g(h)+O(h^n),p(h)=q(h)+O(h^m),k=min(n,m)とした時、 1.f(h)+p(h)=g(h)+q(h)+O(h^k) 2.f(h)*p(h)=g(h)*q(h)+O(h^k) 3.f(h)/p(h)+g(h)/q(h)+O(h^k) らしいのですが、この3式が成立する意味がわかりません。k=max(n,m)だったら、成り立つような気がするのですが…。 誰か解説よろしくお願いいたします。
- 締切済み
- 数学・算数
- 二分探索アルゴリズムの問題の解法
二分探索アルゴリズムを用いて、N件のレコードを持つ表の中からキーの値がkに一致するレコードを探し出す探索を考える。この探索について以下の問いに答えよ。 1）このアルゴリズムにおいて最も計算時間が短くなるのは、どのような場合か？ 2）このアルゴリズムにおいて最も計算時間が長くなる場合の時間計算量をNのオーダーで表せ。 全くわからないので教えていただいたら、ありがたいです。 一応二分探索なのでO（logN）だけはわかります。 宜しくお願いします。
- 締切済み
- その他（プログラミング・開発）
- トリボナッチ数列とコーシー列
トリボナッチ数列｛F_(n)}の隣接する二項の比a_(n)が収束することをコーシー列を絡めて証明する方法を教えて下さい 大学初等数学を勉強している際、コーシー列で証明できるという事を書いてある本を数冊見つけましたが具体的な証明方法を載せている本を見つけることはできませんでした また、教授に聞いても簡単、コーシー列で証明できる程度のことしか聞くことができず、また、検索しても証明方法を見つけることができませんでした この範囲のテストも終わりゆっくり考える時間を取れるようになりましたが三週間考えてもわかりません ご協力をお願いします ただし トリボナッチ数列 F_n=F_(n-1)+F_(n-2)+F_(n-3) 二項間の比 a_n=F_(n+1)/F_(n) としていただけると幸いです
- ベストアンサー
- 数学・算数
