100以下の素数を全て画面に表示するプログラムを作りなさい.何を使っても良い.
そして、作成したプログラムの計算時間量はどのぐらいかをコメントとして
プログラムの最後に書き込みしなさい。
という課題が出ました。プログラムを作るのはできるのですが、計算時間量の求め方がわかりません。
この課題が出た講義で使ったのがO記法なので、これを使わなければならないと思います。
どういった具合にすれば求めることができるのでしょうか?
わかるかた、教えていただけると助かります。
プログラムの計算量の表記について
Re: プログラムの計算量の表記について
O記法による時間計算量は、入力データの個数によって、
計算時間がどのように増加していくかを表すものです。
100以下の素数をすべて画面に表示するプログラムは、
入力データがないので、O(1) ではないでしょうか?
計算時間がどのように増加していくかを表すものです。
100以下の素数をすべて画面に表示するプログラムは、
入力データがないので、O(1) ではないでしょうか?
Re: プログラムの計算量の表記について
#include <stdio.h>
int main(void)
{
int i,j,yaku;
for(i=1;i<=100;i++)
{
yaku=0;
for(j=1;j<=i;j++)
{
if(i%j==0) yaku++;
}
if(yaku==2) printf("%d ",i);
}
printf("\n");
return 0;
}
このようにプログラムを組んだんですけどこの場合のプログラムの計算時間量もそれでいいんですかね??
int main(void)
{
int i,j,yaku;
for(i=1;i<=100;i++)
{
yaku=0;
for(j=1;j<=i;j++)
{
if(i%j==0) yaku++;
}
if(yaku==2) printf("%d ",i);
}
printf("\n");
return 0;
}
このようにプログラムを組んだんですけどこの場合のプログラムの計算時間量もそれでいいんですかね??
Re: プログラムの計算量の表記について
n 以下の素数として、n が 100の場合、200の場合、1000の場合などとするなら、
その n に対して、計算量を求めることができます。
そのプログラムは、for文の二重ループで、どちらも nに比例する回数
回りますから、O(n2) でしょう。
その n に対して、計算量を求めることができます。
そのプログラムは、for文の二重ループで、どちらも nに比例する回数
回りますから、O(n2) でしょう。