- ベストアンサー
【計算量Log n】僕は実際の面接でソートの計算量
【計算量Log n】僕は実際の面接でソートの計算量を聞かれて、log nですかねと言ったら「は？」という顔をされたので即座に「nより速いのはありえないですよねー、HAHAHA!」とごまかして事なきを得た。 ツイッターより 計算量のlog nのnより早いのはあり得ないってどういう意味ですか? あとLog nの計算量とOのオーダ量の違いは何ですか?
- asuszenphonemax
- お礼率41% (2136/5137)
- Excel（エクセル）
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
ソートというのは、すべてのデータを比較して順番に並べる から、 n が大きくなるとそれより大きいオーダーで計算量は 大きくなるはずで、それより小さいことはあり得ない。 ソートというのは、最大値から最小値までの並べ替えなので、 最大値を求めるだけでデータの個数 n個を比較する必要がある。 すべての順番は、n*n の比較で求まるはずで、O(n^2)より 大きいのは無駄な処理があることになる。理論上、ソートの 計算量は O(n log n)より小さくなることはない。 まして、 O(n) よりも小さい O(log n) なんて、全データを 比較してないのに、ソートできるはずがない。 O(log n) < O(n) < O(n log n) < O(n^2) だから、ごまかせてるはずはない。 全然わかってないとバレてるはず。 計算量は、通常オーダーのレベルでします。 同じオーダーなら、個々のアルゴリズムの違いとかを比較します。
その他の回答 (1)
- asciiz
- ベストアンサー率70% (6636/9403)
＞計算量のlog nのnより早いのはあり得ないってどういう意味ですか? その発言は間違っているので、その人が面接に通ったかどうかわかりませんね。 以下のページに O(n) の話があるのご参考まで。 ＞一週間で身につくアルゴリズムとデータ構造|応用編第1日目：アルゴリズムと計算量 ＞http://sevendays-study.com/algorithm/ex-day1.html
関連するQ&A
- ソートの計算量などについて
こんにちは ソートに関することの質問です。 １．バブルソートの計算量を出す式ですが Ｏ(n^2)=Ｏ(n-1)*Ｏ(n/2)*Ｏ(1)=Ｏ(n)*Ｏ(n)=Ｏ(n^2) で合っていますでしょうか？ ２．クイックソートの（平均）計算量が ｎlog n(底は２)になるのは、なぜなのかを わかりやすく教えて下さい。（できれば式も） ３．クイックソートが最も高速に実行されるのは、ピボットの要素が真中にある場合で、反対に最も効率が悪いのはピボットが端にある場合ですが、この理由をやさしい言葉で教えて下さい。 どなたか教えて下さい。 よろしくお願いします
- ベストアンサー
- C・C++・C#
- シェルソートの計算量を求める方法について
シェルソートで最悪の場合の計算量を求めたいです。 オーダーがnの二乗になるは知っていますが、その求め方、式がしりたいです。 要素数を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(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#
- アルゴリズムの計算量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にできません。ひょっとしたら はさみうち等を使うのでしょうか？ よろしくお願いいたします。
- 締切済み
- 科学
- マージソートの計算量について-O(n*logn)
マージソートの計算量はO(n*logn)ですが、なぜそうなのかが理解出来ません。要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..となり、n=2^x, x=lognとなるところまでは理解出来ました。しかし更にnをかける必要があるのはどうしてでしょうか。要素数が１になるまで分割した後に、小さい順番に比較しながら統合して行く作業があり、これにも当然ランニングタイムがかかるのはわかりますがなぜこの要素の比較コスト？が*nなのでしょうか。 またウェブで調べると、他にもT(n)=2T(2/n)+O(n)という別の説明もあり、こちらも理解出来ません。この説明は上の説明とはまた別の角度から説明しているものなのでしょうか。わかる人がいたら教えて下さい。
- ベストアンサー
- C・C++・C#
- ステップ数と計算量？
ステップ数と計算量とは何でしょうか？ 問題で、 int x = 0; for(int c = 0; c < n; ++c) a += c との問題があり「これのステップ数と計算量をnについて求めよ。」との問題でした。 しかしステップ数と計算量というものがよくわかりません。 ステップ、つまり行数でいいのでしょうか？ 計算量もO（オーダ）を使うどうのと一応知人から教わったのですが、 知人自体もよくわかっていないようで結局何なのだか・・・。 ステップ数と計算量というものについて教えてください。 あとできれば上記の問題についても・・・
- ベストアンサー
- その他（プログラミング・開発）
お礼
ありがとう