- 締切済み
計算量について
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
malloc や配列などを使わないで, 「単純な変数」を使うだけなら O(1) になります. 例えば double x = 0; for (i=0; i < n; ++i) { for (j=0; j < n; ++j) { x += a[i] * b[j]; } } なんかだと, 結局 (入力の他に) x しか使っていないので O(1). これがリストに結果を全部保存したりすると O(n^2) になっちゃいます.
- Tacosan
- ベストアンサー率23% (3656/15482)
この形だと「処理」のところで使うメモリを使い回せるのが普通なので O(1) になりそうな雰囲気はありますが, 厳密には「処理」がどのようなことをしているかわからないのでなんともいえません. 空間計算量は時間計算量より常に小さいので O(n^2) であることは確実なんですが....
お礼
返答ありがとうございます。メモリを使い回せるときと新たにメモリを使う場合というのは具体的にどのような処理になるのでしょうか？毎回メモリを新たに使う場合だとO(n^2)になるという解釈でよろしいのでしょうか?
関連するQ&A
- 計算量オーダーについて 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#
- 時間計算量とオーダーに関する問題がわかりません
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)であるといえるか否かを示しなさい。 この二つの問題ですが、全然分かりません。 導出方法を教えてください。お願いします。
- ベストアンサー
- 数学・算数
- 2進アルゴリズムの時間計算量
ベキ乗計算を2進アルゴリズムで解いた場合の時間計算量を求める方法を教えてください。 x^nの時の時間計算量でn=2,3以外の時でn=2p,2p+1の時で場合わけして(pは整数)数学的帰納法で解いてあるのは見た事はあるのですが、どこからその仮定を持ってきたのか見当がつきません。 どうかお願いします。 n>3のときの時間計算量kは k<=(2*log(n))-1 となっていました。
- ベストアンサー
- その他（プログラミング・開発）
- ソートの計算量などについて
こんにちは ソートに関することの質問です。 １．バブルソートの計算量を出す式ですが Ｏ(n^2)=Ｏ(n-1)*Ｏ(n/2)*Ｏ(1)=Ｏ(n)*Ｏ(n)=Ｏ(n^2) で合っていますでしょうか？ ２．クイックソートの（平均）計算量が ｎlog n(底は２)になるのは、なぜなのかを わかりやすく教えて下さい。（できれば式も） ３．クイックソートが最も高速に実行されるのは、ピボットの要素が真中にある場合で、反対に最も効率が悪いのはピボットが端にある場合ですが、この理由をやさしい言葉で教えて下さい。 どなたか教えて下さい。 よろしくお願いします
- ベストアンサー
- C・C++・C#
- 漸化的計算量のオーダー記法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・C++・C#
- ステップ数と計算量？
ステップ数と計算量とは何でしょうか？ 問題で、 int x = 0; for(int c = 0; c < n; ++c) a += c との問題があり「これのステップ数と計算量をnについて求めよ。」との問題でした。 しかしステップ数と計算量というものがよくわかりません。 ステップ、つまり行数でいいのでしょうか？ 計算量もO（オーダ）を使うどうのと一応知人から教わったのですが、 知人自体もよくわかっていないようで結局何なのだか・・・。 ステップ数と計算量というものについて教えてください。 あとできれば上記の問題についても・・・
- ベストアンサー
- その他（プログラミング・開発）
- 再帰呼び出しの計算量
再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． xのn乗を再帰呼び出しを用いて求める関数に関して，計算量を求める問題なのですが，どのような方針で求めればよいのでしょうか？ int exponent(int x, int n) { if(n == 0){ return 1; }else{ return x * exponent(x, n-1); } } exponentがn回呼ばれるからO(n)というのは間違いでしょうか？
- ベストアンサー
- C・C++・C#
- ハミルトン閉路の計算量についての質問です。
ハミルトン閉路の計算量についての質問です。 教科書で、ハミルトン閉路の計算量が２のｎ乗となっていたのですが、 なぜ、その計算量なのか、ということがよくわかりません。 自分的には、ハミルトン閉路の最良アルゴリズムが、全数検索アルゴリズムであるので、 節点の順列すべてに対してハミルトン閉路か否かを調べる必要があるから、というような 理由を考えたのですが、 具体的になぜ２のｎ乗なのかがいまいちわかりません。 分かる方おられましたらお教え下さい。 お願いし致します。
- ベストアンサー
- 数学・算数
- Ｏ記法の値について
アルゴリズムの計算量を示すのにＯ記法というのがありますが、Ｏ記法って定数係数や次数の低い係数を無視しますよね。 例えば、計算量が次の式になる場合とか。 １．３ｎ＋２ → Ｏ（ｎ） ２．５ｎ''＋３ｎ＋５ → Ｏ（ｎ''） （ｎ''はｎの２乗） ３．２ｎ'''－４ｎ＋３ → Ｏ（ｎ'''） （ｎ'''はｎの３乗） どうして、定数係数や次数の低い係数を無視するのでしょうか？
- ベストアンサー
- その他（プログラミング・開発）
お礼
返答ありがとうございます。 結果をx[i][j]などの行列に格納していくようならO(N^2)になるということですか。なるほどわかりました。ありがとうございます。