問題： 以下の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);
}
