- ベストアンサー
多倍長演算における実行時間と計算量の差
ur2cの回答
- ur2c
- ベストアンサー率63% (264/416)
> 入出力量については > (1)入力 n+n = 2n，出力 n^2なので 2n > (2)入力 2n + n= 3n ，出力 1n > で総合的には4nとなって同じになりそうな気がします． 「入出力」の意味に誤解があるようです。大きな計算は 入力 -> 演算-> 出力 という風に進むのではありません。「入出力」は内部記憶装置と外部記憶装置とのやりとりを指しており、上記「演算」の中で複数回、行われるはずです。それをするのは多分、application program ではなく OS でしょう。 上の意味での入出力が１回行われるとき、(1) は n 桁を 2 つ書くとか読むとかします。ですから 2n に比例です。それに対して (2) は 2n 桁が 1 つと n 桁が 1 つです。ですから 3n に比例です。 plot で n が小さいときに立ち上がりが急なのは、n に比例せずに入出力の準備や後始末に関する固定部分が効いているのだろうという解釈です。
関連するQ&A
- 計算量の少ないｎ乗根の求め方
現在C++であるクラスのインスタンスaのN乗根を求める関数を作成中なのですが、どうしても実行時間が長くなってしまいます。 現在ニュートン法に則って X(m+1)=((N-1)(Xm)^N+a)/(N*(Xm)^(N-1)) という漸化式を回して変化量が一定値以下になったら終了という関数なのですが、 値によっては累乗計算のところで時間を大幅にロスしてしまうようです。 原因としては累乗計算が同じ数をN回掛けるという単純な仕組みなため、 Nが大きすぎるとループがなかなか終わらないということがわかっています。 もしご存知であれば 1.極力累乗計算を使わないN乗根の求め方 2.計算量の少ない累乗計算の仕方 のどちらかを教えていただけないでしょうか？ なお、クラスを使っている関係上powなどの既存の関数は使えません。 よろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- 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#
- 演算対象の数字と演算子を入力して計算させる
数字と演算子をそれぞれ入力し、優先順位の高い順に四則演算させるにはどのような考え方をすればよいのでしょうか。 数字をa［7］とおいて、演算子をop［7］としてそれぞれ配列に格納しましたが、そこから先に進めません。 オペランドと演算子の組み合わせならば優先順に計算してくれるのはわかっていますが、オペランドと演算子を格納した配列では上手く行きません。 実は既に全ての演算子の組み合わせをIfで表示させるプログラムを根性で作ったのですが、最適解を知りたいです。 言語はCでvisualstudioを使っております。 条件はn回数字を入力したらn-1回演算子を入力し、n回目に=を入力する。nの最大値は7とする。です。 だらだらと見辛い文章で申し訳ありませんが、何卒宜しくお願いします。
- 締切済み
- C・C++・C#
- ステップ数と計算量？
ステップ数と計算量とは何でしょうか？ 問題で、 int x = 0; for(int c = 0; c < n; ++c) a += c との問題があり「これのステップ数と計算量をnについて求めよ。」との問題でした。 しかしステップ数と計算量というものがよくわかりません。 ステップ、つまり行数でいいのでしょうか？ 計算量もO（オーダ）を使うどうのと一応知人から教わったのですが、 知人自体もよくわかっていないようで結局何なのだか・・・。 ステップ数と計算量というものについて教えてください。 あとできれば上記の問題についても・・・
- ベストアンサー
- その他（プログラミング・開発）
- 計算量の下界の計算
ある論文中の回路計算量の下界を求めようと思うのですが、どうも計算がうまくいかないので知恵をお貸しください。 l=√(k)(切り捨て) p=10√(k)log_{2}n(切り上げ) m=(p-1)^{l}*l! この時、size(C)・m^2・(n-l-1)Choose(k-l-1)≧(n)choose(k) という式からsize(C)の下界がn^{Ω(√(k))}と定まるらしいのですが、この導出がわからないのです。 Ωは下界オーダーの記号です。 size(C)≧～という式にしてこの右辺がn^{Ω(√(k))}で表せる式になればよいと思うのですがいまいちうまくいきません。 お分かりの方がいらっしゃいましたら教えていただけると幸いです。 よろしくお願いします。
- 締切済み
- 数学・算数
- 計算時間の問題
基本情報技術者試験に出題された問題についての質問です。 ---------------------------------------- 問５ コンピュータで連立一次方程式の解を求めるのに，式に含まれる未知数の個数の３乗に比例する計算時間がかかるとする。あるコンピュータで １００元連立一次方程式の解を求めるのに２秒かかったとすると，その４倍の演算速度をもつコンピュータで１，０００元連立一次方程式の解を求めるときの計算時間は何秒か。 ア ５ イ ５０ ウ ５００ エ ５，０００ ---------------------------------------- 上記の問題において、某問題集の解説には次のような説明がありました。 ---------------------------------------- 未知数が１，０００個ある場合の計算時間は１００個のときと比べると(1000の3乗)÷(100の3乗)＝1000倍になる。未知数が１００個のとき２秒だから、同じコンピュータで計算した場合、１，０００個のときは2×1000＝2000秒かかる。ただし、コンピュータの演算速度は４倍なので、2000÷4＝500秒になる。 ---------------------------------------- 私がよく理解できないのは、コンピュータの演算速度が４倍になるとどうして単純に４倍早い時間になるのですか？問題には計算時間が未知数の個数の３乗に比例するとありますが、解説の最後(2000÷4＝500秒)で３乗が考慮されないのは何故なのかわかりません。 ご教授をお願い致します。
- ベストアンサー
- 情報処理技術者
- 離散フーリエによる時間計算量
分割統治法を用いて、N点離散フーリエ変換を計算するとき（高速フーリエ）、その時間計算量T(N)＝２T(N/2)＋Nを再帰的に代入して次数を下げていくことにより、Nを大きくしたときの漸近的な振る舞いは T(N)＝O（Nlog_2 N）となることを示そうと、代入を試みてやってみたのですが、まず T(N)＝O（Nlog_2 N）の右辺は何を意味しているのか分からず、またどのようにそれを導けばいいのか検討がつきません。 ヒントを教えてもらえないでしょうか？
- 締切済み
- 数学・算数
- 計算量(PやNP)について
ネット上で計算量理論に関する説明を読んでいますが、いまいち理解ができません。 例えば、木の形で表せれる問題で、一つのノードに対する子がN個(定数)あり、深さX(未知、変数)に答えがある場合、計算量は N^X(NのX乗) になると思います。 N^Xは計算量のクラス(NP困難やNP完全等)でいうと何に属するのでしょうか？
- ベストアンサー
- 数学・算数
お礼
ご回答ありがとうございます >入出力量 なるほど，なんとなく理解ができました． (1)は2n (2)は3nに比例するので，差がどんどん広がってくるということですね．