- ベストアンサー
ソートに関する計算量について。
処理時間Tが、それぞれT＝５Ｎ T＝Ｎの２乗/10 T＝Ｎlog2Ｎ （←log2の2は小さい2） の3つのプログラムがあります。 ここでＮはプログラムで処理されるデータ数であります。 これらのプログラムのデータ数と処理時間について比較考察をせよ という問題があるのですが分かりません。 教えてください！ お願いします！
- C・C++・C#
- 回答数3
- ありがとう数0
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
エクセルでやるなら A2～A適当に１～適当の数字を入れて B2に =5*A2 C2に =(A2^2)/10 D1に =A2*log(A2,2) といれて夫々下方向にコピーしてやれば表が出来る。 （1行目はタイトル） あとはグラフにするだけ。
その他の回答 (2)
- itinohana
- ベストアンサー率41% (58/139)
問題の意味すらわからないということでしょうか？ それとも、問題の意味は分かるけれども、説明の 仕方がわからないということでしょうか？ とりあえず、TとNに関するグラフを書いてみれば問題の意図も、説明方法も見えてくると思います。
- Trick--o--
- ベストアンサー率20% (413/2034)
横軸をN、縦軸をTにしてグラフを描いてみよう。 NによってTがどのように変化するか一目で分かる。 あとはそれを日本語で書くだけだ。
関連するQ&A
- 離散フーリエによる時間計算量
分割統治法を用いて、N点離散フーリエ変換を計算するとき（高速フーリエ）、その時間計算量T(N)＝２T(N/2)＋Nを再帰的に代入して次数を下げていくことにより、Nを大きくしたときの漸近的な振る舞いは T(N)＝O（Nlog_2 N）となることを示そうと、代入を試みてやってみたのですが、まず T(N)＝O（Nlog_2 N）の右辺は何を意味しているのか分からず、またどのようにそれを導けばいいのか検討がつきません。 ヒントを教えてもらえないでしょうか？
- 締切済み
- 数学・算数
- マージソートの計算量
データ構造とアルゴリズムのテストでこんな問題が出てきました。 マージソートにおける値の比較回数は、C(n)は次のように表すことができる。C(4)は幾らか。 C(n) = 1 (n = 1のとき) C(n) = 2 C(n/2) + n (n > 1のとき) この問題の解答は１２でした。 この問題を解くプロセスを教えていただけませんか？ よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- マージソートの計算量について-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の系列に対して3nμ秒で探索を完了する線形プログラムと 4log_2(n)μ秒で探索を完了する二分探索プログラムと 2nlog_2(n)μ秒で整列を完了するプログラムがある。 これらのプログラムを利用して、長さが1024の未整列のデータ系列Sに対し、ある要素が含まれているかどうか探索したい。このとき以下の問いに答えよ。ここでの検索要求とは「系列Sにある要素Xが含まれているかどうか判定すること」とする。」 ・検索要求が1回、5回、10回の場合それぞれの最も速い探索方法とその時間を述べよ。 計算方法と答えを教えてください。
- 締切済み
- 情報処理技術者
- 対数の計算
Ω=(1/N!)*(V^N/h^3N)*{π(2π^2*mE)^[(3/2)N-(1/2)]}/Γ[(3/2)N+1] として Ωの対数をとって計算していくと Γ(n+1)!=n! logN!=NlogN-N を用いて logΩ=log1-logN!+logV^N-logh^3N+[(3/2)N-(1/2)]logπ(2π^2*mE)-logΓ[(3/2)N+1] =log1-NlogN+N+NlogV-3Nlogh+[(3/2)N-(1/2)]logπ(2π^2*mE)-logΓ[(3/2)N+1] =・・・・・と計算していけるんですが どうしてもlogΩ=NlogV+(3/2)Nlog(2E/3N)+・・・・・・ （・・・はVとEを含まない項) 教科書によれば最終的にはlogΩ=NlogV+(3/2)Nlog(2E/3N)+・・・・・・ （・・・はVとEを含まない項)という式なるはずで、この式をを導きたいんですが、計算でうまくいかないんです。 なかなかlogΩ=NlogV+(3/2)Nlog(2E/3N)+・・・・・・ （・・・はVとEを含まない項)に もっていけないんで、それの計算過程を教えていただきたいです。
- ベストアンサー
- 数学・算数
- ソートの時間計算について
ソートの時間計測について以下のようなプログラムを作成したのですが、ソートはうまく動きますが何度試しても処理時間が0.00000秒となってしまいます。どのように改良すればこのような問題を解決できるのでしょうか。ご回答よろしくお願いいたします。 #include <stdio.h> #include <time.h> #define SIZE 100 void swap(int data[], int s, int t){ int tmp = data[s]; data[s] = data[t]; data[t] = tmp; } void Bsort(int data[], int size) { int i, j; for(i=1; i<size; i++){ for(j=(size-1); j>0; j--){ if(data[j] < data[j-1]){ swap(data, j, j-1); } } } } void Ssort(int data[], int size){ int i, j, k, tmp; for(i=1; i<size; i++){ k = data[i-1]; for(j=i; j<size; j++){ if(k>data[j]){ tmp = k; k = data[j]; data[j] = tmp; } } tmp = k; k = data[i-1]; data[i-1] = tmp; } } void printArray(int ar[], int size) { int i; for (i = 0; i < size; i++) printf("%4d", ar[i]); printf("\n"); } int main(void) { int i, x; int data[SIZE]= {412, 54, 595, 329, 24, 488, 313, 272, 129, 210, 670, 516, 342, 541, 491, 640, 167, 117, 726, 206, 474, 762, 153, 292, 1000, 607, 151, 661, 93, 270, 737, 531, 641, 548, 299, 287, 547, 394, 550, 475, 443, 261, 707, 503, 403, 739, 226, 646, 778, 588, 427, 169, 477, 572, 413, 300, 88, 321, 55, 779, 542, 680, 211, 273, 288, 276, 405, 307, 424, 668, 756, 255, 190, 449, 35, 435, 91, 486, 58, 408, 4, 63, 534, 330, 701, 65, 256, 311, 586, 404, 459, 254, 291, 333, 42, 343, 418, 512, 164, 56}; clock_t t1,t2; printf("番号を入力してください。\n1,Bubble Sort\n2,Selection Sort\n"); scanf("%d", &x); switch(x){ case 1: printf("before:"); printArray(data, SIZE); t1 = clock(); Bsort(data, SIZE); t2 = clock(); printf(" after:"); printArray(data, SIZE); printf("処理時間:%f[ms]¥n", (double)(t2 - t1) / CLOCKS_PER_SEC); break; case 2: printf("before:"); printArray(data, SIZE); t1 = clock(); Ssort(data, SIZE); t2 = clock(); printf(" after:"); printArray(data, SIZE); printf("処理時間:%f[ms]¥n", (double)(t2 - t1) / CLOCKS_PER_SEC); break; } return 0; }
- ベストアンサー
- C・C++・C#
- ソートに関する質問です
C言語でのプログラム作成の課題が解けなくて困っています。 バブルソートを使って、1000000個の整数データを昇順に並べ替えるプログラムを作成するというものです。 自分なりに作成したプログラムは、mallocでデータを格納する動的領域を確保して、後はシンプルにバブルソートの処理を行っています。 データ数が5，6万程度なら正常な動作が確認できるのですが、それより大量のデータ数だと、処理に時間が掛かりすぎるせいか、もしくは処理しきれずに動かなくなってしまったのか分かりませんが、プログラムの処理がいつまでたっても終わりません。 おそらくバブルソートの2重ループのあたりで、膨大な処理になってしまうのだと思うのですが、この問題についての改善策をどなたかご教授いただけませんでしょうか。
- ベストアンサー
- C・C++・C#
- SSEからAICやBICを求められるのはなぜ？
次のようにしてSSE（二乗和誤差）からAICやBICを求められるという記述を見かけましたが納得できません。 AIC= nlog(SSE/n) + 2(k+2) BIC= nlog(SSE/n) + (k+2)log(n) n:観測値数 k:パラメーター数 第１項のSSEは観測値のスケールの影響を受けるように思います。しかし第２項は観測値のスケールの影響を受け内容に見えます。その結果、スケールによって選ばれるモデルが変わってしまうような事が起きると思うのですが問題ないのでしょうか？それともSSEを求めるときに何らかのスケーリングを行うのでしょうか？ よろしくお願いします。
- ベストアンサー
- 数学・算数
- シェルソートの計算量を求める方法について
シェルソートで最悪の場合の計算量を求めたいです。 オーダーがnの二乗になるは知っていますが、その求め方、式がしりたいです。 要素数をN、感覚を４、２、１でお願いします。 考え方として各間隔のときのソート結果を無視して、各間隔時に単純挿入ソートと同様にして計算するのでしょうか？ それとも、各間隔でのソート結果を考慮するべきなのでしょうか？ できれば計算式と考え方、両方教えていただければありがたいです。 回答よろしくお願いします。
- 締切済み
- 科学
