合計 昨日 今日

プログラムの計算量の表記について

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Name: ひげが伸びた
[URL]
Date: 2017年4月19日(水) 23:35
No: 1
(OFFLINE)

 プログラムの計算量の表記について

100以下の素数を全て画面に表示するプログラムを作りなさい.何を使っても良い.
そして、作成したプログラムの計算時間量はどのぐらいかをコメントとして
プログラムの最後に書き込みしなさい。

という課題が出ました。プログラムを作るのはできるのですが、計算時間量の求め方がわかりません。

この課題が出た講義で使ったのがO記法なので、これを使わなければならないと思います。

どういった具合にすれば求めることができるのでしょうか?
わかるかた、教えていただけると助かります。

Name: かずま
[URL]
Date: 2017年4月19日(水) 23:48
No: 2
(OFFLINE)

 Re: プログラムの計算量の表記について

O記法による時間計算量は、入力データの個数によって、
計算時間がどのように増加していくかを表すものです。

100以下の素数をすべて画面に表示するプログラムは、
入力データがないので、O(1) ではないでしょうか?

Name: ひげが伸びてきた
[URL]
Date: 2017年4月20日(木) 00:10
No: 3
(OFFLINE)

 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;
}


このようにプログラムを組んだんですけどこの場合のプログラムの計算時間量もそれでいいんですかね??

Name: かずま
[URL]
Date: 2017年4月20日(木) 00:33
No: 4
(OFFLINE)

 Re: プログラムの計算量の表記について

n 以下の素数として、n が 100の場合、200の場合、1000の場合などとするなら、
その n に対して、計算量を求めることができます。

そのプログラムは、for文の二重ループで、どちらも nに比例する回数
回りますから、O(n2) でしょう。

Name: KRNKRS
[URL]
初心者(5,259 ポイント)
Date: 2017年4月22日(土) 15:44
No: 5
(OFFLINE)

 Re: プログラムの計算量の表記について

返答ではなく申し訳ないですが、
ソースコードはcodeで囲みましょう

コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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;
}


Return to C言語何でも質問掲示板

オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[13人]