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

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
ひげが伸びた

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

#1

投稿記事 by ひげが伸びた » 8年前

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

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

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

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

かずま

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

#2

投稿記事 by かずま » 8年前

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

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

ひげが伸びてきた

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

#3

投稿記事 by ひげが伸びてきた » 8年前

#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: プログラムの計算量の表記について

#4

投稿記事 by かずま » 8年前

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

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

KRNKRS
記事: 40
登録日時: 12年前
連絡を取る:

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

#5

投稿記事 by KRNKRS » 8年前

返答ではなく申し訳ないですが、
ソースコードは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;
}

返信

“C言語何でも質問掲示板” へ戻る