ページ 1 ／ 1
プログラムの計算量の表記について
Posted: 2017年4月19日(水) 23:35
by ひげが伸びた
100以下の素数を全て画面に表示するプログラムを作りなさい．何を使っても良い．
そして、作成したプログラムの計算時間量はどのぐらいかをコメントとして
プログラムの最後に書き込みしなさい。
という課題が出ました。プログラムを作るのはできるのですが、計算時間量の求め方がわかりません。
この課題が出た講義で使ったのがO記法なので、これを使わなければならないと思います。
どういった具合にすれば求めることができるのでしょうか？
わかるかた、教えていただけると助かります。
Re: プログラムの計算量の表記について
Posted: 2017年4月19日(水) 23:48
by かずま
O記法による時間計算量は、入力データの個数によって、
計算時間がどのように増加していくかを表すものです。
100以下の素数をすべて画面に表示するプログラムは、
入力データがないので、O(1) ではないでしょうか？
Re: プログラムの計算量の表記について
Posted: 2017年4月20日(木) 00:10
by ひげが伸びてきた
#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;
}
このようにプログラムを組んだんですけどこの場合のプログラムの計算時間量もそれでいいんですかね？？
Re: プログラムの計算量の表記について
Posted: 2017年4月20日(木) 00:33
by かずま
n 以下の素数として、n が 100の場合、200の場合、1000の場合などとするなら、
その n に対して、計算量を求めることができます。
そのプログラムは、for文の二重ループで、どちらも nに比例する回数
回りますから、O(n2) でしょう。
Re: プログラムの計算量の表記について
Posted: 2017年4月22日(土) 15:44
by KRNKRS
返答ではなく申し訳ないですが、
ソースコードはcodeで囲みましょう
コード:
#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;
}