計算時間量、平均時間量について教えてください（ＴＴ）

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

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: 計算時間量、平均時間量について教えてください（ＴＴ）

Re: 計算時間量、平均時間量について教えてください（ＴＴ）

#2

by 白い変人 » 8年前

まず、Nが100と定数なので、O(1)と考える事が妥当と言えるでしょう。

また、仮にNが可変である変数だったとしても、rand()関数に関しては、その手続きまでは実は厳密には規定されていません。

ですから、あるコンパイラではrand()の結果を得る為に要するステップ数が一定である物が、別なコンパイラでは、1回目,2回目,3回目と呼び出すに従い、要するステップ数が増加する可能性すら否定できないと言えるでしょう。

そういう意味では、コンパイラによりけりな部分もあるので、rand()のソースも提示するべきでしょう。

ただ、憶測で言うのなら、rand()が線形合同法である場合、一回の呼び出しに要するステップ数は恐らくO(1)と見積もれるでしょう。

ですから、Nが可変であり、rand()がO(1)ならば、そのプログラムの時間計算量はO(N)で良いでしょう。(但し、アルゴリズムとして、Nがあらゆる自然数をとり得るとするならば、厳密にはO(N)も間違いと言えるでしょう。)

平均時間計算量は、考え得るあらゆる入力が与えられた場合、手続きの動作が終了するまでに至る平均の時間計算量を求めれば良いだけです。

ですから、その定義上、この場合は平均時間計算量もO(N)で変わらないと言えるでしょう。(常にNステップ発生する手続きなので。)

この質問に依存しない平均時間計算量の求め方という事でしたら、その計算量を求めるアルゴリズムによりけりな部分があるので、一概にこれがやり方と言うのはありません。

但し、学術目的等で、厳密な計算量を算出するソフトウェア等も存在はするらしいです。(私はそんな物に頼った事はありませんし、この程度の小規模な手続きでその様なソフトウェアに頼らなければならない程なら論外だと思います。 但し、質問者様は恐らく初学者と思えますので、現時点では初歩的な部分で混乱してしまうのも仕方がないのは理解出来る部分はあります。)

計算時間量、平均時間量について教えてください（ＴＴ）

#1

by 馬鹿です。 » 8年前

コード: 

#include<stdio.h>
#include<stdlib.h>

void maxmin(int a);
#define N 100

int ar[N];
int main(void)
{
	int i;
	
	for(i = 0;i < N;i++){
		ar[i] = rand();
		printf("%d\n",ar[i]);
	}
	maxmin(N);
	
	return 0;
}

void maxmin(int a)
{
	int max,min,i;
	max = 0;
	min = RAND_MAX;
	for (i = 0;i < a; i++) {
		if (max < ar[i]) 
			max = ar[i];
	}
	for (i = 0;i < a; i++) {
		if (min > ar[i])
			min = ar[i];
	}
	printf("最大値は%dです。\n",max);
	printf("最小値は%dです。\n",min);
}
このプログラムの計算時間量はO(n)出会ってますでしょうか？
また、平均時間量はどのように求めるのでしょうか？

ページトップ