- 締切済み
O(n log n)について
O(n log n)のOはオーダーnはデータの数、logてなんですか？
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- D-Matsu
- ベストアンサー率45% (1080/2394)
関連するQ&A
- アルゴリズムの計算量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にできません。ひょっとしたら はさみうち等を使うのでしょうか？ よろしくお願いいたします。
- 締切済み
- 科学
- 対数logについて
対数logについて 基本情報処理技術者試験の勉強をしているのですが、 オーダ記法のところで、よく使われる表現として O(1) O(log n) O(n) O(n log n) O(n^2) ←計算時間小 計算時間大→ という五つの表現が紹介されているのですが、 このうち対数logを用いた物が理解できません。 例えば0(n)は、データ量nが2倍に増えれば計算時間も2倍になるということですよね。 しかしO(log n)だとどういう考え方になるのかわかりません。 対数についてもまだ理解できていないので、 対数のことから教えていただけないでしょうか。回答お待ちしてます。
- ベストアンサー
- 情報処理技術者
- 漸化的計算量のオーダー記法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)) であってますか？
- ベストアンサー
- その他([技術者向] コンピューター)
- 整列の比較回数を表す数式でよく見るO(n log n)のOって何ですか
タイトルどおりなのですが、数式の(n log n)とO(n log n)では何がちがうのですか。 どなたか教えてください。
- ベストアンサー
- その他(データベース)
- O(n log n)について2
n log nはつまり１０の(nのn乗）乗という事ですね？ なにやらこちらの参考文献にはNの２乗よりn log nの方が効率が良いとあるのですが計算するとn log nのほうが数値が高くなるのですが、これはどういうことでしょう？
- ベストアンサー
- C・C++・C#
- 計算量オーダーについて 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)オーダーに見えるのですが、この判断は正しいでしょうか？ 皆さんのご意見を伺わせてください。
- ベストアンサー
- C・C++・C#
- 【対数】log(2)n=n-1となるnを求める問題
はじめまして。 題の通りなのですが、nを自然数とするときにlog(2)n=n-1を満たすnの値は求められますか？ 2^(n-1)=nと変形はしたのですが、ここから動きません
- ベストアンサー
- 数学・算数
- 1+1/2+1/3+…とlog(n)
数学の参考書を読んで疑問に思ったんですけど Ｓ＝1+1/2+1/3+…+1/nとして lim（Ｓ-log(n))が0.5772くらいに収束するのは y=1/xなどのグラフからの面積評価で感覚的になんとなくわかるんですけど lim(Ｓ/log(n))という極限値が１にいくのが全然理解できません。 わかる方はヒントでもなんでもいいのでお願いします。 ちなみにlogは自然対数です。limはｎ→∞という 意味です。
- ベストアンサー
- 数学・算数
- 【計算量Log n】僕は実際の面接でソートの計算量
【計算量Log n】僕は実際の面接でソートの計算量を聞かれて、log nですかねと言ったら「は？」という顔をされたので即座に「nより速いのはありえないですよねー、HAHAHA!」とごまかして事なきを得た。 ツイッターより 計算量のlog nのnより早いのはあり得ないってどういう意味ですか? あとLog nの計算量とOのオーダ量の違いは何ですか?
- ベストアンサー
- Excel（エクセル）
- ∑[8/(n・sinh(nπ)]=log2
次の式を証明していただけませんか。 和はnの和で、n=1,3,5,7・・・と奇数です。 ∑[8/(n・sinh(nπ)]=log2 数値計算では両辺が等しいことを確認しています。 お願いいたします。
- ベストアンサー
- 数学・算数
お礼
ありがとうございます。が、サイトを見てもいまいち（てかさっぱり）分かりません・・・（・・；）すいません、素人の私でも分かるようなざっくりとした解説を誰が詳しい方お願いします。