- ベストアンサー
Euclidの互除法の時間計算量について
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
入力サイズだそうです(多分aやbの2進数での桁数←勘) で、計算量については以下ご覧ください http://www.akita-pu.ac.jp/system/elect/comp1/kusakari/japanese/teaching/SoftTech/2005/note/2/Slide23.html んでもって http://kent.parks.jp/59/otona/bbs.cgi によると >ちなみに計算量を示すラージオーの表記では、（底の変換公式により、どんな底に変換したとしても高々定数倍ですので）底は関係なく（記述せず）、通常 O(log n)と書きます。 だそうです
関連するQ&A
- アルゴリズム:2分探索の時間計算量
アルゴリズムの参考書を読んでいて疑問に思ったんですが、教えてください。 /* ２分探索 */ #include <stdio.h> /*--- 要素数nの配列aからkeyと一致する要素を２分探索 ---*/ int bin_search(const int a[], int n, int key) { int pl = 0;/* 探索範囲先頭の添字【1】 */ int pr = n-1;/* 〃 末尾の添字 【2】*/ int pc; /* 〃 中央の添字 */ do { pc = (pl + pr) / 2;/*【3】*/ if (a[pc] == key) /* 探索成功【4】 */ return (pc);/*【5】*/ else if (a[pc] < key)/*【6】*/ pl = pc + 1;/*【7】*/ else /*【8】*/ pr = pc - 1;/*【9】*/ } while (pl <= pr);/*【10】*/ return (-1);/* 探索失敗【11】 */ } のプログラムがありますが、【1】から【11】までの 実行回数と計算量は次のようになるそうですが、 実行回数 計算量 【1】 1 O(1) 【2】 1 O(1) 【3】 logn O(logn) 【4】 logn O(logn) 【5】 1 O(1) 【6】 logn O(logn) 【7】 logn O(logn) 【8】 logn O(logn) 【9】 logn O(logn) 【10】 logn O(logn) 【11】 1 O(1) なぜ【3】や【4】がlognになるんでしょうか？ 詳しく教えてください。 よろしくお願いします。
- ベストアンサー
- 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)であるといえるか否かを示しなさい。 この二つの問題ですが、全然分かりません。 導出方法を教えてください。お願いします。
- ベストアンサー
- 数学・算数
- マージソートの計算量について-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#
- 離散フーリエによる時間計算量
分割統治法を用いて、N点離散フーリエ変換を計算するとき（高速フーリエ）、その時間計算量T(N)＝２T(N/2)＋Nを再帰的に代入して次数を下げていくことにより、Nを大きくしたときの漸近的な振る舞いは T(N)＝O（Nlog_2 N）となることを示そうと、代入を試みてやってみたのですが、まず T(N)＝O（Nlog_2 N）の右辺は何を意味しているのか分からず、またどのようにそれを導けばいいのか検討がつきません。 ヒントを教えてもらえないでしょうか？
- 締切済み
- 数学・算数
- Euclidの拡張互除法
Euclidの拡張互除法 互いに素な自然数A,Bがあるとき、Ax+By=1を満たす整数(x,y)が存在しますね。 また、この式からAB-BA=0をn倍して辺々引くと A(x-nB)+B(y+nA)=1 が成り立つので (x-nB,y+nA)も、Ax+By=1の整数解であると言えます。 これ以外に、Ax+By=1を満たす整数解は存在することはありますか? それと、Euclidの拡張互除法で Ax+By=1を満たす整数(x,y)を求めることができますが 無限に存在する(x,y)の組のうち、求まるのは 最も簡単なもののような気がしますが、それは正しいですか? 「最も簡単」というのは適当な表現が見つからないのですが 絶対値が一番小さい数の組み合わせといいますか 既約分数のようなイメージです。
- ベストアンサー
- 数学・算数
- 二分探索のアルゴリズム
分からない問題があります。 ・２分探索における計算量を答えなさい。また、なぜそのようになるのかについてわかりやすく説明しなさい。 ・線形探索の計算量と２分探索の計算量を比べるとどちらの方が計算量が大きいか。理由をつけて説明しなさい。 ２分探索の計算量が O(logn) 線形探索の計算量が O(n)となるのはわかりますが そのようになる説明をどのようにしたらいいか。また logn<n となるのは わかるのですが理由をどう説明したらいいのか分かりません。 どなたかお教え下さい。
- ベストアンサー
- 科学
- 2進アルゴリズムの時間計算量
ベキ乗計算を2進アルゴリズムで解いた場合の時間計算量を求める方法を教えてください。 x^nの時の時間計算量でn=2,3以外の時でn=2p,2p+1の時で場合わけして(pは整数)数学的帰納法で解いてあるのは見た事はあるのですが、どこからその仮定を持ってきたのか見当がつきません。 どうかお願いします。 n>3のときの時間計算量kは k<=(2*log(n))-1 となっていました。
- ベストアンサー
- その他（プログラミング・開発）
- ユークリッドの互除法
早急に解答求めています、 ご協力よろしくお願いします(>_<) 1.自分では簡単に素因数分解できない2つの整数(どちらとも9桁以上の整数)を決めてその最大公約数をeuclidの互除法で求め よ。 2.1で求めた数が最大公約数であることを示せ。 できれば途中式も省かないで書いていただきたいです。 よろしくお願い申し上げます。
- 締切済み
- 数学・算数
- 計算量のオーダについて
Ｏ(n＾2+nlogn） Ｏ(n√ｎ+nlogn） Ｏ(nlogn+n^2）+Ｏ(（n＾1.67）logｎ） Ｏ(nlogn+n^100）Ｏ(n＾0.7+logｎ） この４つの式をそれぞれ簡略化せよという問題なのですが、 考え方がよくわかりません。 どなたかご教授よろしくお願いします。
- ベストアンサー
- 情報処理技術者
