問題： 以下の2つのプログラムを実装し、時間計算量を実験的に評価せよ。

質問

問題：　以下の2つのプログラムを実装し、時間計算量を実験的に評価せよ。
　　　　(1)１から１万までの整数ちをランダムに１千個生成するプログラム
　　　　(2)シェルソートプログラム

質問内容

プログラム（）をやったんですが、「時間計算量を実験てきに評価せよ」というのは分かりません。
教えてください。

/* ランダムプログラ*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 1000
void main(){
FILE *fp;
int i,rnd;
fp=fopen("data.dat","w");
srand((int)time(NULL));
for(i=1;i<=N;i++){
rnd = (int)rand()% 10000 + 1;
fprintf(fp,"%d\n ", rnd);
}
fclose(fp);
}

/* シェルソートプログラム*/
#include <stdio.h>
#include <stdlib.h>
#define DATA_NUM 1000
void ShellSort(int num[ ], int n) ;
void InsSort(int num[ ], int gap, int n);
void ShowData(int num[ ], int n);
void main(void);

/* n 個のデータのシェルソートを行う */
void ShellSort(int num[ ], int n)
{
int gap;

for (gap = n / 2; gap > 0; gap /= 2)
InsSort(num, gap, n);

}

/* n 個のデータの単純挿入ソートを行う */
void InsSort(int num[ ], int gap, int n){
int i, j, temp;

for (i = gap; i < n; i ++) {
for (j = i - gap; j >= 0; j -= gap) { /* このループで */
if (num[j] <= num[j + gap]) /* j 番目とj + gap 番目と比較 */
break; /* ここにbreak;を挿入。*/
else {
temp = num[j]; /* 要素の入れ替え */
num[j] = num[j + gap];
num[j + gap] = temp;
ShowData(num,DATA_NUM); /* 途中経過を表示 */
}
}
}
printf("\n"); /* InsSort( ) を抜ける時改行 */
}
/* n 個のデータの表示 */
void ShowData(int num[ ], int n)
{
while (n--)
printf("%d ", *num++);
printf("\n");
}

void main(void)
{
FILE *fp;
int data[DATA_NUM];
int i;
fp = fopen("data.dat","r");
if(fp == NULL){
printf("data.dat cannot be opened");
exit(1);
}
for(i=0;i<DATA_NUM;i++){
if(fscanf(fp,"%d",&data[i])== NULL){
break;
}
}
printf("ソート前\n");
ShowData(data, DATA_NUM);
printf("\n");

/* シェルソート */
ShellSort(data, DATA_NUM);
printf("\n");

printf("ソート後\n");
ShowData(data,DATA_NUM);
printf("\n");
fclose(fp);
}

回答No.3

和泉 博（@hiroshi09s）

単純に、要した時間を知る。
ソースはgccです。使い方は
　　./a.out 2>/dev/null
を奨励します。
Windowsは、データを見たければ、「#define FLAG 0」に設定してください。
データ型は１万以下ということで２バイトの short にしてみました。それによれば１万データでは20kバイト、d[] と temp[] の２配列で40kバイトですから省メモリとして、そのままメモリ上でコピーしながらソートしています。

/* Gcc on Mac OSX */
#include <stdio.h>
#include <stdlib.h> //qsort()
#include <string.h> //memcpy()
#include <sys/time.h>
#include <time.h>
#define N 10000
#define FLAG -1 // データのリスト参照は -1 → 0

void shell_sort(short *, int);
int comp(const void *, const void *);
void pri_out(char *, short *, int, double);
double second(void);

int main(void) {
int i;
short d[N+1], temp[N+1];
double start;

// 乱数データの生成
srand(time(NULL));
for(i=0;i<N;i++)
d[i] = (int)rand() % N + 1;

// 各データ数におけるソート時間
for (i = N/10; i <= N; i += N/10) {
// 採用乱数データ
pri_out("Making sort data", d, i, 0.0);

// シェルソート
memcpy(temp, d, sizeof(d));
start=second();
shell_sort(temp, i);
pri_out("Shell sort", temp, i, second() - start);

// クイックソート
memcpy(temp, d, sizeof(d));
start=second();
qsort(temp, i, sizeof(short), comp);
pri_out("Quick sort", temp, i, second() - start);
}

return 0;
}

void shell_sort(short d[], int n) {
int i, j;
short temp;
for (i = 1; i < n; i++) {
temp = d[i];
for (j = i - 1; j >= 0 && d[j] > temp; j--)
d[j + 1] = d[j];
d[j + 1] = temp;
}
}

int comp(const void *_a, const void *_b) {
short a = *(short *)_a;
short b = *(short *)_b;
if ( a > b)
return 1;
else if (a < b)
return -1;
else
return 0;
}

void pri_out(char *comment, short d[], int n, double its_time) {
int i;
if (its_time != 0.0)
printf("%s (n = %d) = %f second\n", comment, n, its_time);
else
fprintf(stderr, "%s (n = %d)\n", comment, n);
if (!FLAG) {
for(i=0;i<n;i++)
fprintf(stderr," %d", d[i]);
fprintf(stderr, "\n");
}
}

double second() {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec / 1.0e6;
}

参考URL：

http://sugi.sakura.ne.jp/ecc/reps_s.html

回答No.2

salsberry

「時間計算量を実験的に評価せよ」の内容については、課題を出した人に訊いてください。

あと、時間を測定する方法はOSによって異なるので、使っているOSやコンパイラの情報も書いたほうがいいでしょう。No.1さんのtimeGetTime関数はWindows専用です。

回答No.1

cyacya2000

時間を測定するだけでよいのならtimeGetTime関数を使えばよいのでは？
使用例は以下の通りです。
#include <mmsystem.h>
#pragma comment(lib,"winmm.lib")
：
DWORD StartTime,EndTime;
：
timeBeginPeriod(1);
StartTime=timeGetTime();
時間を計測する処理
EndTime= timeGetTime();
timeEndPeriod(1);
　EndTime-StartTimeを表示

ただし、あなたの掲載したプログラムでは、乱数をファイルに書き出したり、ソートの途中結果を表示したりしています。この部分は本来の乱数発生処理やソート処理に対して時間のかかる部分ですから、この部分を除いて、計測した方が良いと思います。

補足

cyacya2000さん
シェルソートプログラムにtimeGetTime関数をすべて書いてくださいませんか？

お願いします。