- 締切済み
幅優先探索の計算量
グラフG=(V, E)における幅優先探索の計算量について質問です． ある頂点rから幅優先探索で頂点tを探すとき，何冊かの本を見ると「計算量は(|E|)」となっています．これを理解できません． ある頂点に対して，その隣接頂点にtが含まれるかどうかを検索する関数を作ったとします．各頂点に対してこの関数を高々一度ずつ呼び出すことで，その頂点に接続している辺が高々一度ずつ検索されるので，計算量はO(|V|+|E|)になるのではないのでしょうか? |E|>|V|を仮定しているのかとも思ったのですが，それ以降にも「O(|V|^2|E|)」というような記述が出てきます． どなたかご教授下さい．
- magicoflove
- お礼率1% (11/757)
- 数学・算数
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- gakutensoku
- ベストアンサー率35% (14/40)
G=(V,E)をSimpleな連結無向グラフとすると、以下の関係が成り立ちます。 |V|-1 ≦ |E| ≦ |V|*(|V|-1)/2 この関係により、計算量O(|V|+|E|)は漸近的な意味において O(|E|)と等しくなります。 O(n^2+n) = O(n^2)みたいな関係です。
関連するQ&A
- 二分探索のアルゴリズム
分からない問題があります。 ・２分探索における計算量を答えなさい。また、なぜそのようになるのかについてわかりやすく説明しなさい。 ・線形探索の計算量と２分探索の計算量を比べるとどちらの方が計算量が大きいか。理由をつけて説明しなさい。 ２分探索の計算量が O(logn) 線形探索の計算量が O(n)となるのはわかりますが そのようになる説明をどのようにしたらいいか。また logn<n となるのは わかるのですが理由をどう説明したらいいのか分かりません。 どなたかお教え下さい。
- ベストアンサー
- 科学
- アルゴリズム: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#
- 二分探索アルゴリズムの問題の解法
二分探索アルゴリズムを用いて、N件のレコードを持つ表の中からキーの値がkに一致するレコードを探し出す探索を考える。この探索について以下の問いに答えよ。 1）このアルゴリズムにおいて最も計算時間が短くなるのは、どのような場合か？ 2）このアルゴリズムにおいて最も計算時間が長くなる場合の時間計算量をNのオーダーで表せ。 全くわからないので教えていただいたら、ありがたいです。 一応二分探索なのでO（logN）だけはわかります。 宜しくお願いします。
- 締切済み
- その他（プログラミング・開発）
- 再帰呼び出しの計算量
再帰呼び出しを用いた関数の計算量を求める方法がわからないので質問させていただきます． 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#
- 化学の計算がわからなくて困ってます(>_<)
初めて質問させて頂きます。 今、公務員試験の勉強中なんですが どうしてもわからない問題があり、 教えて頂ければと思います。 同温、同体積の水素と酸素の重さをはかったら 同じであった。 水素の圧力を1気圧とするなら、 酸素の圧力は何気圧か? ただし、原子量はH=1、O=16 とする。 という 問題で 水素の分子量=2 酸素の分子量=32 温度=T 体積=V 重さ=ω 気体定数=R 求める圧力=p として 気体の状態方程式を利用して 1×V=ω／2×R×T、 p×V=ω／32×R×T という 2式までは出せるんですが その2式から p=1／16 という 答えを導きだす 計算過程がわかりません(>_<) 長々と申し訳ないのですが 化学、数学が 得意な方 ぜひ 計算過程を教えて 頂けないでしょうか？ よろしくお願いいたします。
- ベストアンサー
- 化学
- この計算式の途中の式教えてください！
t=(V-Vo)/a の式を、ｘ＝Voｔ＋1/2at^2に代入してできる途中の計算式を教えて欲しいのです。。さっきから何回やっても２ax＝V^2-V^2oの答えにたどりつかないのです。。どうかお願いします。。
- 締切済み
- 物理学
- 離散フーリエによる時間計算量
分割統治法を用いて、N点離散フーリエ変換を計算するとき（高速フーリエ）、その時間計算量T(N)＝２T(N/2)＋Nを再帰的に代入して次数を下げていくことにより、Nを大きくしたときの漸近的な振る舞いは T(N)＝O（Nlog_2 N）となることを示そうと、代入を試みてやってみたのですが、まず T(N)＝O（Nlog_2 N）の右辺は何を意味しているのか分からず、またどのようにそれを導けばいいのか検討がつきません。 ヒントを教えてもらえないでしょうか？
- 締切済み
- 数学・算数
- ホール起電力を求める計算について
こんにちは、 下記は、ある本に記載されているホール起電力を求める問題です。 計算したのですが、答えは下記で正しいのでしょうか？ ホール起電力って、単位は「ボルト」なのでしょうか？それとも「エネルギー」のなのでしょうか？ 幅が２５ｍｍで厚さが０．５ｍｍの長方形断面で、無限に長い銅の棒に５０Aの電流が流れている。この幅広の面に垂直に２Tの磁界が与えられたとき、この銅棒に生じるホール起電力を求めよ。ただし、電子の電荷量を１．６×１０＾（－１９）C単位体積当たりの電子数を８．４×１０＾２８とせよ 式 e = 1.6/10^19; (*電子の電荷量*) n = 8.4*10^28; (*単位体積当たりの電子数*) B = 2; (*磁界*) I1 = 50; (*電流*) t = 0.5/10^3; (*厚さ*) w = 25/10^3; (*幅*) V = (1/(e*n))*B*(I1/t); (*ホール起電力[V]*) Print["ホール起電力[V]"]; Print[V]; E1 = e*V; (*ホール起電力[V]による電子1個のエネルギー[eV]*) Print["ホール起電力[V]による電子1個のエネルギー[eV]"]; Print[E1]; F = e*v*B; (*ローレンツ力[N]*) Print["ローレンツ力[N]"]; Print[F]; 計算結果 ホール起電力[V] 0.000014881 ホール起電力[V]による電子1個のエネルギー[eV] 2.3809523809523812*10^(-24) ローレンツ力[N] 9.523809523809526*10^(-23) 追伸 本に問題を載せたら、答えもいっしょに載せてほしいです。何で、答えを記載しないのか？理解できません。
- ベストアンサー
- 物理学
- カール量の計算
下記条件時のカール（曲率またはカール量）量は計算で概算できますか？ 計算式をご教授願います。 ?２層のフィルムである。 ?１層目と２層目は貼り合わせており、１層目と２層目のヤング率は同じ である（接着層のヤング率や熱収縮は無視する）。 ?フィルムの厚み（ｔ）が１層目と２層目で異なる。（幅は同じ） ?１層目の熱収縮率と２層目の熱収縮率が異なる。 通常、１層目と２層目の厚みとヤング率が同じである場合は、１層目と２層目の熱収縮差を?L、熱処理後の全長（１層目と２層目を比べて長い方の全長）をL、１層目と２層目の加算厚みをｔ、カール曲率をRとすると、 ε＝?L÷L R＝（３×ε）÷（２×ｔ） となると思いますが（違っている場合は訂正願います）、１層目と２層目で厚みが異なる場合の計算式が分かりません。ご教示願います。
- 締切済み
- その他（開発・設計）
- 経路探索の問題
http://www.i.u-tokyo.ac.jp/edu/course/m-i/pdf/2002imim.pdf の、問題3について質問なのですが、 問1は、 (1) 線形リストとして、n回で到達できるセルの情報を与えると、n+1回で到達できる線形リストを返す関数を考える。返すリストの作成方法は、n回で到達できるセルの前後左右を調べて、すでに調べたセルや障害物のセルでなければ、そのセルをn+1回で到達できるセルとしてメモし、返す線形リストに追加する。 (2) int l[M][N];//特定のセルまでの距離をメモする配列。最初にすべて-1をいれておく。障害物には-2を入れておく。 class list{ int i,j; list *next; list(){ next=0; } } //n回で到達できるセルのリストをpl、n+1階で到達できるセルのリストを返すポインタをnlとする。 void getNextCellsList(list *pl,list *nl){ list *tt=pl; list *t; int i,j; nl=0; while(tt){ i=tt->i; j=tt->j; if(i>0&&l[i-1][j]==-1){ l[i-1][j]=l[i][j]+1; t=nl; nl=new list; nl->i=i-1; nl->j=j; nl->next=t; } if(j>0&&l[i][j-1]==-1){ l[i][j-1]=l[i][j]+1; t=nl; nl=new list; nl->i=i; nl->j=j-1; nl->next=t; } if(i<M-1&&l[i+1][j]==-1){ l[i+1][j]=l[i][j]+1; t=nl; nl=new list; nl->i=i+1; nl->j=j; nl->next=t; } if(j<N-1&&l[i][j+1]==-1){ l[i][j+1]=l[i][j]+1; t=nl; nl=new list; nl->i=i; nl->j=j+1; nl->next=t; } tt=tt->next; } } と、したのですが、このgetNextCellsList関数を一回使う時間計算量は、O(n)としていいのでしょうか？ また、もしそうなら問2の時間計算量は、 (getNextCellsList関数を一回使う時間計算量)*M*N=O(n)*O(n^2)=O(n^3) 空間計算量は、 (セルまでの距離をメモする配列の数)+(n回で到達できるセルの情報)=O(n^2)+O(n)=O(n^2) となるのでしょうか？ あと、この問題の(M,N,D)のオーダーで評価せよというのはどういう意味として捉えればいいのでしょうか？O(n^3)などと書いておくだけで良いのでしょうか？ 問3の時間的及び空間的に効率化する方策としてはどのようなものが考えられるのでしょうか？これは、自力では全然ろくな方法が思い付きませんでした。。。 宜しくお願いします。
- ベストアンサー
- C・C++・C#
