データ構造とアルゴリズムI実習(2限目)


以下の課題を解け. 必要に応じて講義資料を参考にすること.講義資料は ここにある. 課題の提出期限および提出方法は以下の通りとする.

課題3(提出不要):

線形探索アルゴリズムの速度を体感してみよう. 課題1のプログラムの main 関数を以下のように書換えよ.
書換えが完了したらコンパイルしてプログラムを実行してみる. レコードの数を1から10000までの範囲で適当に変えてみて,実行速度が変化することを確かめよ.

main() {
    int n = 0, i;
    int key, data;
    long j;
    clock_t start;

    printf("レコードの数(n)を入力してください:");
    scanf("%d", &n);

    /* n個のレコードをランダムに登録 */
    for (i = 0; i < n; i++) {
        key = (int)(rand() * n);
        data = (int)(rand() * 100);
        regist(key, data);
    }

    /* ランダムなkeyで1000000回探索を行う */
    start = clock();
    for (j = 0; j < 1000000; j++) {
        key = (int)(rand() * n);
        data = search(key);
    }

    /* 所要時間を表示 */
    printf("処理に%f秒かかりました\n", (clock() - start) / (double)CLOCKS_PER_SEC);    
}

課題4(提出不要):

二分探索アルゴリズムの速度も体感してみよう.
課題2のプログラムの main 関数も課題3と同様に書換え,コンパイルして実行してみよ.
課題3同様,レコードの数によって実行速度が変化することを確かめよ.

課題5(要提出):

線形探索アルゴリズムと二分探索アルゴリズムの時間計算量を比較したい.
課題3および課題4のプログラムそれぞれに対して,レコード数を適当に変えながら実行速度を測定し, 比較結果をExcelのグラフ(散布図)にまとめよ.
レコード数の変更は手入力で行ってもかまわないが,main() 関数を以下のように書き換えるとより便利である.

main() {
    int n = 0, i;
    int key, data;
    long j;
    clock_t start;

    for (n = 1; n < 10000; n *= 2) {
        for (i = 0; i < n; i++) {
            key = (int)(rand() * n);
            data = (int)(rand() * 100);
            regist(key, data);
        }
    
        /* ランダムなkeyで1000000回探索を行う */
        start = clock();
        for (j = 0; j < 1000000; j++) {
            key = (int)(rand() * n);
            data = search(key);
        }
    
        /* 所要時間を表示 */
        printf("%d, %f\n", n, (clock() - start) / (double)CLOCKS_PER_SEC);    
    }
}