こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

締切り済みの質問

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

問題: 以下の2つのプログラムを実装し、時間計算量を実験的に評価せよ。
    (1)1から1万までの整数ちをランダムに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);
}

投稿日時 - 2010-03-05 16:45:22

QNo.5727163

すぐに回答ほしいです

このQ&Aは役に立ちましたか?

2人が「このQ&Aが役に立った」と投票しています

回答(3)

ANo.3

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



/* Gcc on Mac OSX */
#include <stdio.h>
#include <stdlib.h>//qsort()
#include <string.h>//memcpy()
#include <sys/time.h>
#include <time.h>
#define N10000
#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

投稿日時 - 2010-03-09 20:10:46

ANo.2

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

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

投稿日時 - 2010-03-06 11:23:07

ANo.1

時間を測定するだけでよいのならtimeGetTime関数を使えばよいのでは?
使用例は以下の通りです。
#include <mmsystem.h>
#pragma comment(lib,"winmm.lib")

DWORD StartTime,EndTime;

timeBeginPeriod(1);
StartTime=timeGetTime();
時間を計測する処理
EndTime= timeGetTime();
timeEndPeriod(1);
 EndTime-StartTimeを表示

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

投稿日時 - 2010-03-05 19:06:38

補足

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

お願いします。

投稿日時 - 2010-03-09 01:31:52

あなたにオススメの質問