- ベストアンサー
アルゴリズムの実行時間
関数f(n)と時間tに対して アルゴリズムが問題を解くためにf(n)マイクロ秒 かかるとき、各時間で解くことができる最大の問題サイズを教えてください nlgnのとき1秒と１分 2^nのとき１秒と１分 n！のとき１秒と１分 教えてください できれば考え方も教えてください お願いします
- saya19
- お礼率7% (20/264)
- その他（プログラミング・開発）
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
#1 です。すいません。 > 1秒は1000マイクロ秒、1分は60000マイクロ秒なのだから、 1秒は1000000マイクロ秒 (10^6) １分は60000000マイクロ秒(60x10^6) の間違いでした。
その他の回答 (1)
- a_kwn
- ベストアンサー率34% (8/23)
1秒は1000マイクロ秒、1分は60000マイクロ秒なのだから、 n・ln(n) = 1000 n・ln(n) = 60000 2^n = 1000 2^n = 60000 n! = 1000 n! = 60000 となるnをそれぞれ求めればいいのではないでしょうか？
関連するQ&A
- アルゴリズム
アルゴリズムの勉強をしていて、時間計算量に関する問題があり、解いたのですが、解答が載ってなく困ってます。正誤の判断と、もし間違っているなら、何が間違っているのかを教えて頂けると助かります。 ある問題において、大きさ(データ量)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[時間]
- ベストアンサー
- その他（プログラミング・開発）
- 時間計算量とオーダーに関する問題がわかりません
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)であるといえるか否かを示しなさい。 この二つの問題ですが、全然分かりません。 導出方法を教えてください。お願いします。
- ベストアンサー
- 数学・算数
- 再帰アルゴリズム
再帰アルゴリズムの練習のため問題に取り組んでいるのですが、問題集に解答がついておらずイマイチ理解できていないので教えていただけると助かります。 d個の毎インデックスで(0,0,...,0)から(n,n,...,n)まで反復させるアルゴリズムを反復アルゴリズムと再帰アルゴリズムの両方考えよ です。 (0,0,0,...,0) (1,0,0,...,0) (1,1,0,...,0) (1,1,.....,1) ... (n,n,.....,n) と表示を繰り返すプログラムでいいのかな、と思い反復の方は二十ループを用いてプログラムかけたんですが、再帰の法がアルゴリズムがどうも理解できていません。 ご教授願えればと思い、お願いします。
- 締切済み
- 科学
- ２分探索法 『成功・不成功探索一回の実行時間を求める』
Ｃ言語の授業で課題が出たのですが、自分が思っているような値が出なくて困っています。よろしければヒントだけでも頂ければなと思います。 ----------課題---------- 整列されているＮ個のデータに対して、その中にｖがあるかどうかを判断する２分探索プログラムを実行する Ｎの値を10^6、5×10^6、10^7、5×10^7、10^8 と変化させたとき、成功探索、不成功探索一回の実行時間をそれぞれ求めよ。 このとき、Ｎと実行時間の関係はどのようになっているか（１００字程度で） Ｎ 成功探索 不成功探索 10^6 ＊＊＊秒 ＊＊＊秒 5×10^6 ＊＊＊秒 ＊＊＊秒 10^7 ＊＊＊秒 ＊＊＊秒 5×10^7 ＊＊＊秒 ＊＊＊秒 10^8 ＊＊＊秒 ＊＊＊秒 ---------------------------------------- ～↑を元に作成したプログラム（成功探索の場合）～ #include <stdio.h> #include <stdlib.h> #include <time.h> #define T 1000000 #define N 100000000 int a[N]; int main(void) { clock_t t1,t2; int t; int i; int l, r, k, v, m; for (i = 0; i < N; i++) a[i] = i; t1=clock(); for (t = 0; t < T; t++) { v = rand() % N; l=0; r=N-1; k=-1; while (r >= l) { m = (l+r)/2; if (v == a[m]) { k=m; break; } if (v < a[m]) r = m-1; else l = m+1; } } t2=clock(); printf("cpu time=%10.6f[micro sec]\n",(double)(t2-t1)*1000000/(CLOCKS_PER_SEC*T)); return 0; } ↑a[i]すべてに０～Ｎ－１を代入し、ｖにランダムに０～Ｎ－１の値を代入する。２分探索法で、ｖ＝a[i]となったら終了する。 実行時間は、↑の操作を10^6回行い、その平均を実行時間をする…単位：マイクロ秒 として、コンパイルして動いたんですが実行時間の値にずれがありどの値が一番適切か分からなくて困っています。 ↑のプログラムをそれぞれのＮで実行したところ Ｎ＝ 10^6で実行・・・1.016 0.891 0.969 1.155 1.14 [micro sec] 5×10^6で実行・・・1.422 1.500 1.563 1.250 1.406 1.297 10^7で実行・・・1.750 1.360 1.37 1.407 1.672 1.531 5×10^7で実行・・・1.859 1.797 1.812 1.800 10^8で実行・・・2.062 2.140 2.320 2.500 このような結果になりました。 これで正しいのでしょうか？もう少しずれの幅が小さいと決められそうなのですが…そもそもプログラムが間違ってるんでしょうか？ でも、Ｎが大きくなるにつれて実行時間が増えてるのでこちらはまだいいんですが・・・問題は不成功探索の方です。 次に 不成功探索では↑のプログラムの 乱数ｖのところを変化させて v=rand() % N；という箇所を ｖ＝Ｎ;としました。 a[i]には０～Ｎ－１が入っているので、ｖ＝Ｎとすれば必ず不成功になるはずですよね？ こうして実行してみると Ｎ＝ 10^6、5×10^6、10^7、5×10^7、10^8と値を変化させても 0.719 0.54 0.625 0.534 [micro sec] に近い値ばかり出てしまい、正しい値とは到底思えません。 不成功探索は成功探索より時間がかかるはずですよね？なのになぜこのようになってしまったのでしょうか？ 後、Ｎと実行時間の関係とは、最終的に得られた結果を元にして「実行時間はlog2Nに比例している」と言えばいいんでしょうか？ こういうものってどのように回答したらいいのかヒントだけでももらえると非常に有難いです。 長々とスイマセン。 少し気づいたことなど些細なことでも全然かまわないので、どうかよろしくお願いします。
- ベストアンサー
- C・C++・C#
- うるう年判定のアルゴリズム
javaでうるう年判定のプログラムを作成しています。 プログラム自体はサーバにアップするときに実行結果が正しいかどうかテストされます。 仕様としては、 1.時間に関するAPIなどは一切使わずに完全に自作 2.入力される値はLong型の"秒"数(APIで提供されているのはミリ秒ですが) 3.60537895631062456L などの入力値に対して、年/月/日 (曜日) 時:分:秒 yday=元旦からの経過日数 を出力 最初は以下の関数を使用してループをかけていたのですが、仕様3の入力値に対して50秒近くかかってしまい、上手くいきませんでした。 public static int isLeap(int year){ if(year%4==0 && (year%100!=0 || year%400==0)) return 1; return 0; } 問題点はループ回数が多いことで、作る時点で分かってはいたのですが、ここまで遅くなるとは思っても見ませんでした。 これを使わない方法としては、一回だけうるう年(=n)を見つけ、その後は「(n+4)との比較+100で割り切れず400で割り切れる場合は別」という処理を行うことによって、処理時間を30秒付近にまで短縮することができたのですが、どうも10～15秒以内で終わらせなければテストにパスすることができないようです。 なんとか色々考えてはみたものの、上手いアルゴリズムは思いつきませんでした。 うるう年を処理するための"高速な"アルゴリズムはないのでしょうか。 お知恵を貸してください。よろしくお願いします。
- ベストアンサー
- Java
- うるう年判定のアルゴリズム
javaでうるう年判定のプログラムを作成しています。 プログラム自体はサーバにアップするときに実行結果が正しいかどうかテストされます。 仕様としては、 1.時間に関するAPIなどは一切使わずに完全に自作 2.入力される値はLong型の"秒"数(APIで提供されているのはミリ秒ですが) 3.60537895631062456(Long値) などの入力値に対して、年/月/日 (曜日) 時:分:秒 yday=元旦からの経過日数 を出力 最初は以下の関数を使用してループをかけていたのですが、仕様3の入力値に対して50秒近くかかってしまい、上手くいきませんでした。 public static int isLeap(int year){ if(year%4==0 && (year%100!=0 || year%400==0)) return 1; return 0; } 問題点はループ回数が多いことで、作る時点で分かってはいたのですが、ここまで遅くなるとは思っても見ませんでした。 これを使わない方法としては、一回だけうるう年(=n)を見つけ、その後は「(n+4)との比較+100で割り切れず400で割り切れる場合は別」という処理を行うことによって、処理時間を30秒付近にまで短縮することができたのですが、どうも10～15秒以内で終わらせなければテストにパスすることができないようです。 なんとか色々考えてはみたものの、上手いアルゴリズムは思いつきませんでした。 うるう年を処理するための"高速な"アルゴリズムはないのでしょうか。 お知恵を貸してください。よろしくお願いします。
- ベストアンサー
- C・C++・C#
- アルゴリズムについて（ちょい難問だと思います）
（a,b）が（a>b）かつ（b>=0）を満たすとき x = a; y = b; while(y>0){ r = (xをyで割った余り); x = y; y = r; } return x; (xを出力） というa,bの最大公約数を求めるアルゴリズムがあるとする。 ここでwhile文の実行回数（while文を行う回数）を L(a,b)とし、 F(n)をフィボナッチ数列とすると、 （つまり、F(0)=0,F(1)=1,F(2)=1, F(n+2)=F(n+1)+F(n) (n>=0)) 「L(a,b)＝n」 ならば 「a >= F(n+1)」であることを示せです。 どうフィボナッチとループ回数を比較できるのか？ うまく思いつきませんでした・・・ どなたかうまい方法思いついた方お願いします。
- ベストアンサー
- 数学・算数
- ◆アルゴリズムについて
◆アルゴリズムについて なるべく沢山の意見を寄せられると助かります。 関西にある某専門学校の事です。 俺は「初心者でもついていけますか？」と聞き、 受け付けは、「普通の問題だから初心者でもついていけます」と答えました。 それがアルゴリズムなのですが、その参考書を開くとわからないの桁が違い、自習のやり方すら何をすればいいのかわかりません。 勿論、授業もさっぱりわかりませんでした。 先生方や受け付けは、質問すればいい、とか、聞けばわかる、の返答ばかり・・・。 難しすぎて何を質問すればいいのか、わからないくらいのものでした。 授業料を無駄にしたくなく何とかついていこうとして、ついていけず、タガが外れてうつ病にかかりました。 事実上、リタイアしてしまいました。 自分のできる最大限の努力はしたのですが・・・ ・そこで聞きたいのですが、アルゴリズムは普通の問題なのでしょうか？ ・初心者でもついていける科目なのでしょうか？ ・またアルゴリズムを習得するには、大体何年かかりますか？
- ベストアンサー
- その他（学問・教育）
