- ベストアンサー
ハミルトン閉路の計算量についての質問です。
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
その記述の前後に理由は書かれていないのですか?
関連するQ&A
- 時間計算量とオーダーに関する問題がわかりません
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#
- 多倍長演算における実行時間と計算量の差
数学の論文において数値実験が必要だったため， 多倍長演算をC++で実行したところ，計算量とのギャップが生じました． その原因をコンピュータに詳しい方にアドバイスを頂きたいと思って質問させていただきました． 具体的には，n,m を同ビット として 以下の二つの演算を考えます． 演算(1) n * m 演算(2) n^2 % m (n^2は先に計算しておき，% (mod)の演算のみ) -------------------------------------------------- ■計算量評価 大雑把に(1)と(2)の計算量を比較すると (1) lg n * lg m = (lg n)^2 (2) (2*lg n - lg m) * lg m = (lg n)^2 となるので，(1) と (2)はほぼ同じ計算量となります． -------------------------------------------------- しかしながら，実際に計算をしてみると， n,m が 1000bit ほどまでは，ほぼ同じ計算時間なのですが， 2000bit, 4000bit ,..., と数を大きくしていくと，大きくしただけ (2) の速度が遅くなります． 具体的な実験結果は画像で添付いたします． 画像 (http://puu.sh/6iBQf.png) (1) と (2)の実行時間のギャップは何処から生じたものなのか，何かわかるかたがいらっしゃいましたら教えていただけたら嬉しいです． よろしくお願い致します． 予想： コンピュータの知識があまりないですが，自分なりの予想では，(2)のn^2という数が大きすぎるため，演算においてメモリ間とのデータのやり取りで何かのオーバーヘッドが生じているのではないかと予想していますが，確証がもてません．
- ベストアンサー
- 情報工学
- 半導体における光の取り出し量の計算
タイトルのように、半導体における光の取り出し量の計算方法がわかりません。 たとえば参考URLのページにはGaNからの光の取り出せる量は全体の4%程度と書いてありますが、これは臨界角𝜽=𝐬𝐢𝐧^(－𝟏)(𝒏_𝒂𝒊𝒓∕𝒏_𝑮𝒂𝑵 )=23°からなどから計算できるのでしょうか？ ネットで調べたところ、立体角などを考慮するようですが… 具体的な計算式などを教えていただけたら助かります。 参考URL http://www.aist.go.jp/aist_j/press_release/pr2010/pr20100318/pr20100318.html
- 締切済み
- 物理学
- アルゴリズム
アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。 ある問題において、大きさ(データ量)nに対して、アルゴリズムA、B、Cの時間計算量が、それぞれn、n^2(nの2乗)、2^n(2のn乗)であるとする。 (1)アルゴリズムAを用いて10秒間にn=100の問題が解けた。20秒かけるとき扱える問題の大きさnの値を求めよ。 解) n=100*2 =200 (2)ある計算機を用いてアルゴリズムBで10秒間にn=100の問題が解けた。100倍早い計算機を用いたとき、10秒間に扱える問題の大きさを求めよ。 解) 求める問題の大きさをxとおくと n=(100^2)*100 =10000*100 =1000000 (3)アルゴリズムCを用いて1時間にn=20の問題が解けた。n=40の問題を解くのに何時間かかるか。 解) 2^40=(2^20)*(2^20) =1*(2^20) =2^20[時間]
- ベストアンサー
- その他（プログラミング・開発）
- 素数判定アルゴリズム内の剰余計算
今勉強している任意倍長精度整数の素数を判定するアルゴリズム内で x^q mod n という計算をするところがあるのですが、 正確に計算しようとすると計算量が膨れ上がってしまって 高速にできなくて困っています。 参考にしている文献に "x^q mod nの計算ではx^q mod nを正確に求める必要は無く、 x^q ≡ x^q' (mod n)となる x^q'でよい"という記述があるのですが どういう意味なのかよくわかりません。 どなたか教えていただけないでしょうか？
- 締切済み
- その他（プログラミング・開発）
- 二分探索アルゴリズムの問題の解法
二分探索アルゴリズムを用いて、N件のレコードを持つ表の中からキーの値がkに一致するレコードを探し出す探索を考える。この探索について以下の問いに答えよ。 1）このアルゴリズムにおいて最も計算時間が短くなるのは、どのような場合か？ 2）このアルゴリズムにおいて最も計算時間が長くなる場合の時間計算量をNのオーダーで表せ。 全くわからないので教えていただいたら、ありがたいです。 一応二分探索なのでO（logN）だけはわかります。 宜しくお願いします。
- 締切済み
- その他（プログラミング・開発）
- 順列の列挙の方法
順列の列挙の方法といっても辞書式順序のやつではありません。別の制約です。 グレイコードというのをご存知でしょうか。例えばビット列のグレイコードは次のようになります。 0:000 1:001 2:011 3:010 4:110 5:111 6:101 7:100 これがどんな制約を満たしているかと言うと、 1、となりのビット列に変換するには1ビット反転すれば良い。 2、すべてのビット列がちょうど1回現れる。 この2つです。グレイコードの正確な定義はさておき、とりあえず今はこれと言うことにします。 この順序でビット列を列挙する関数をC言語で書くと次のような感じになります。 f(int n) { if(n==-1)return; f(n-1); 第nビットを反転； 出力； f(n-1); } さて順列の話ですが、次のような制約を満たす順序で順列を列挙するアルゴリズムは どんな感じになるのでしょうか。 1、となりの順列に変換するには1回スワップ(2つの要素を入れ換える)すれば良い。 2、すべての順列がちょうど1回現れる。 この条件を満たすような順列の列はたくさんあると思いますが、 できるだけ法則性のあるやつ、というかプログラムに書きやすいやつを お願いします。 ビット列のアルゴリズムをちょこっと変えれば出来るかなーと思っていたのですが 数学的センスが無いせいか、苦戦しています。数学的センスのある方、ぜひご教示ねがいます。
- ベストアンサー
- 数学・算数
補足
全数検索であるため、というような内容の文章があるだけでした。 具体的にO(2＾n)になる理由の説明はありませんでした。 誠に申し訳ありません。 まだ、解決できておりませんが、回答を締め切らせて頂きます。 急ぐ必要がなくなりましたので、図書館などで、他の書籍をみて 調べてみたいと思います。 せっかく回答を頂いたのにすみません。