• 締切済み

アルゴリズムの計算量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にできません。ひょっとしたら はさみうち等を使うのでしょうか？ よろしくお願いいたします。

  • 科学
  • 回答数2
  • ありがとう数2

みんなの回答

  • a-saitoh
  • ベストアンサー率30% (524/1722)
回答No.2

wikipedia(下のURL)の定義式は正しいですが、あなたが質問文にかいた定義式は間違っています。理解できるまでよく読むことが必要です。 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

  • a-saitoh
  • ベストアンサー率30% (524/1722)
回答No.1

O(nlogn)を示すのに、O(n)の定義式を持ってきても駄目です。 まず教科書をもっとよく読んでください。

jetblue
質問者

お礼

ご回答ありがとうございます。 定義式以外の式があるのでしょうか？ 離散なのですが教科書には定義式すら書いてありません。 Wikipediaで定義式をやっと拾ってきたところです。 何かヒントでも良いのでいただけませんか？

  1. カテゴリ
  2. 学問・教育
  3. 自然科学
  4. 科学

関連するQ&A

  • ０の０乗＝１……かな？

    ０の０乗はいったい何なのかを考えていたら、ある本の中にあった、lim（ｎ→∞）ｎ＾1/n＝１の証明を見て少しひらめきました。 　　f(x)＝(1+x)^n－(1+nx) という関数はｘ＞０で微分可能ですから。 　　f'(x)＝n(1+x)^n-1－n＝n{(1+x)^n-1-1}＞０ 　である事がわかります。すると、f(0)=0であり、f(x)はｘ＞＝０で増加するから、ｘ＞０のときf(x)＞０で、つまり 　　(1+x)^n＞(1+nx) ここで、ｘ＝1/√ｎとおくと 　　(1+1/√n）^n＞1+√n＞√n この式の左辺と右辺を2n乗すると 　　(1+1/√n）^2n＾2＞n^n ここでn＞１ならn^n＞１ですから 　　(1+1/√n）^2n＾2＞n^n＞１ 　 さらにlim（n→0)とすると 　　(1+1/√n）^2n＾2→1 となり、n^nは1で両側から挟み撃ちにされるので 　　lim(n→0)n^n＝1 つまり、０の０乗は１ってことにならないでしょうか。長々とした証明でした。読んでくださってありがとうございました。 　　　　　　　　　

  • O(n log n)について

    O(n log n)のOはオーダーnはデータの数、logてなんですか？

  • 計算量オーダーについて　O(1/n)オーダー？

    　こんにちは、c#初心者です。 　今回は計算量オーダーの話なので、基本的に言語は関係ないと思います。 　計算量オーダーの基本的な部分は分かるのですが、O(1/n)オーダーのアルゴリズムは（今のところは）まだ見かけないというか、名前程度しか知らないので、これに関しては無知です。そこで、この場合はどういうオーダーになっているのかという質問です。 　質問は３つあります。 １）この一連の処理はO(1/n)オーダーになっているか？ int count = 1000 / length; // lengthは正の整数 for ( int i = 0; i < count; i++ ) Do(); // O(1)オーダーの処理 ２） （１がO(1/n)の場合）繰り返す処理がO(n^2)になった場合に、この一連の処理はO(n)オーダーになるのか？ int count = 1000 / length; // lengthは正の整数 for ( int i = 0; i < count; i++ ) Do(); // O(n^2)オーダーの処理 ３）配列型のコレクション（コレクションって、c#の呼び方だったっけ？） [c#] List<T>,[c++] Bector, [Java] ArrayList(だったっけ？)のようなクラスのAddメソッドのオーダーは？ //Addメソッドの中身 if ( Capacity == Count ) Expand(); // Expandは配列の容量を２倍に拡張するO(n)処理とします。 array[Count++] = item; 　以上です。 　補足で、２）については大学の教授に「一回でもO(n^2)の処理が呼び出されたら、O(n^2)オーダーになる」と言われましたが、納得いかないです。確かに、O(1/n)オーダーの処理の後にO(n^2)オーダーの処理を行えば、そうなるのは納得いくのですが……という感じです。教授が読み間違えたとは考えにくいですが（確かにちょっと忙しそうでしたが）、念のため質問です。 　それと、３）はよくある配列型のコレクションのまねです。「もし内容物が容量一杯になれば拡張→追加」を繰り返すとした場合です。ExpandメソッドのオーダーがO(n)なので、単純に計算すればO(n)オーダーになるのですが、呼び出される頻度が「(拡張された容量)回に１回」です。 　例えば、容量が４ずつ拡張されるとすれば、「４回に１回」拡張が必要になり、１０ずつ拡張されるとすれば、「１０回に１回」の拡張が必要です。この場合、どう考えても全体として定数で割っているだけなので、O(n)オーダーのままになるのは明白なのですが、今回は容量２倍とさせていただきました。すると拡張の頻度は「（さっきまでの容量）回に１回」の頻度で、容量に反比例し、直感的にはO(Count / Capacity) = O(1)オーダーに見えるのですが、この判断は正しいでしょうか？ 　皆さんのご意見を伺わせてください。

  • 「e」が絡んだ不等式証明

    「自然数nについて、次の不等式が成り立つことを求めよ。 　　　n・log(n)-n+1 ≦ log(n!) ≦ (n+1)log(n+1)-n　　」 という問題で、最初は素直に左辺-右辺≧0を使って示しました。 その後、別解として数学的帰納法を用いた証明に挑みました。 n=1のときは楽勝ですが、n=kで成り立つことを仮定した後の「n=k+1」のときに、式変形でつまずきました。今回の質問は、その最後の大小関係の評価についてです。（以下、式はn=k+1のときのもの） log{(k+1)!}-(k+1)log(k+1)+(k+1)-1 =log(k+1)+log(k!)-(k+1)log(k+1)+k ≧k・logk-k+1-k・log(k+1)+k =1-log(1+1/k)^k　・・・・・・・・・・・・(1) (1)をみた時、「あ、これってeの定義式に似てるな」と思い、もしかして (1)≧1-log(e)=0　・・・・・・・・・・・・・(2) でも言えるのかと思ったのですが、 疑問I： だからといって果たして(2)で等号が言えるのか？ 疑問II：そもそも、lim[x→∞](1+1/x)^x=e は、eより大きい数からeに近付くのか？eより小さい数からeに近付くのか？そしてlim[x→-∞](1+1/x)^x=e では？ 上の疑問について、答が出せる方、宜しくお願いします。

  • (n!)^2≧n^n（nは自然数）

    (n!)^2≧n^n（nは自然数） この不等式の証明なのですが、第１手が分かりません。 両辺対数を取り、移行してnの関数と見て微分に持ち込もうとしたのですが、nが1に近付くと変数として扱えば良いのか定数として扱えば良いのか分からず断念。 そのまま(左辺)／(右辺)の形にして各項の評価も試みましたが、上手く行かず…。 分かる方がいらっしゃいましたら、何かヒントをお願いしたいです。

  • 漸化的計算量のオーダー記法O表記について

    漸化的計算量のオーダー記法O表記について オーダー記法Oでの表記の仕方って、ようするにnをn→∞とした時に、一番大きくなる項を抜き出しきて、n→∞の時、増加量が微少な係数は無視をする。という考え方でいいんでしょうか？ 例えば 1000*(2^n)+0.5(n^n)=O(n^n) nlogn+n√n=O(n√n) n^2.01+(n^2)log(n^2)=O((n^2)log(n^2)) であってますか？

  • cを正の実数とするときに、lim【n→∞】c^n/n!=0を示せ。

    cを正の実数とするときに、lim【n→∞】c^n/n!=0を示せ。 という問題でガウス記号［］を使ってc^n/n!を c/n*……*c/（［c］+1）とc/［c］*……*c/1 という二つの積の固まりに分けたとき、前半はn→∞としたときに0に収束し、後半は定数なのでn→∞としても影響を受けないため、lim【n→∞】c^n/n!=0となるというような証明の仕方でもよろしいでしょうか？模範解答では、後半部分ははさみうちの原理を使っておりました

  • 2^o(logn)・o(logn)=o(n^1/3

    以下ののような式が現在読んでいるものにかかれています。 2^o(logn)・o(logn)=o(n^1/3) このような式がなぜ成立するのかわかりません。元々右辺は求まっていなくて左辺から右辺を導き出すみたいなのですが、どうしてこのようになるのかわかりません。 ご存知のかたや、おそらくこうではないかと思う方は、ご回答のほどよろしくお願いします。

  • はさみうちの定理を使う極限の問題です。

    　lim(n→∞) n*sin(π/n)　の極限値を求める問題で、はさみうちの定理を使って解くことを考えたのですが 　 ≦ n*sin(π/n) ≦ n*π/n となり、右辺の数式は見つけられたのですが、左辺に最適な数式が見つけられずにいきずまっています。答えは、πになるそうなのですが、その過程が分からなくなったので、質問させていただきました。宜しければ、ご回答お願いいたします。

  • 数学的帰納法について

    (1+2+・・・+n)^2 = 1^3 + 2^3 + ・・・ + n^3 を数学的帰納法で証明するのですが、 n=1のとき、 1=1で左辺＝右辺。 n=kで成り立つとしたとき、　 n=k+1のとき、左辺 - (1+2+・・・+k)^2 = k^3 = (k+1)^3　を求めてみようとしたのですが、 式変形がうまくいきません。 どうかご教授願います。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する