计算算法的执行时间

Question

我正在用 C 编写算法 Mergesort。我需要找到不同大小数组的算法执行时间。但总是当我打印时间时，我得到 0.0000.

我搜索了这个问题并阅读了与此相关的其他 Whosebug 问题，但它没有帮助我。我还是一样。

我的代码-

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

void swap(int *a, int *b);
void print_array(int *a, int length);
void merge(int *a, int low, int mid, int high);
void merge_sort(int *a, int low, int high);

int swaps = 0;
int comparisons = 0;
int operations = 0;

int main()
{
    int total_operations[1001];
    int num[1001];
    int nlogn[1001];
    double time[1001];

    FILE *input_file = fopen("UniformDis.txt", "r");
    int n = 1;
    for (n = 1; n <= 100; n++)
    {
        int a[n];
        for (int i = 0; i < n; i++)
        {
            fscanf(input_file, "%d", &a[i]);
        }

        clock_t t;
        t = clock();
        merge_sort(a, 0, n - 1);
        print_array(a, n);
        t = clock() - t;
        double time_taken = (t * 1000.0) / CLOCKS_PER_SEC;
        total_operations[n] = operations + comparisons + swaps;
        num[n] = n;
        nlogn[n] = n * log(n);
        time[n] = t;
        printf("%.50fms\n", t);

        operations = 0;
        comparisons = 0;
        swaps = 0;
    }

    fclose(input_file);
    return 0;
}

void merge_sort(int *a, int low, int high)
{
    operations += 2;
    if (low < high)
    {
        int mid = low + (high - low) / 2;
        merge_sort(a, low, mid);
        merge_sort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
}

void merge(int *a, int low, int mid, int high)
{
    int l, r;
    l = mid - low + 1;
    r = high - mid;
    operations += 2;
    int left[l + 1], right[r + 1];
    for (int i = 0; i < l; i++)
    {
        left[i] = a[low + i];
    }
    operations += l;
    for (int i = 0; i < r; i++)
    {
        right[i] = a[mid + 1 + i];
    }
    operations += r;
    int i = 0, j = 0, k = low;
    while (i < l && j < r)
    {
        comparisons++;
        if (left[i] < right[j])
        {
            a[k] = left[i];
            i++;
        }
        else
        {
            a[k] = right[j];
            j++;
        }
        k++;

        operations += 6;
    }
    while (i < l)
    {
        a[k] = left[i];
        i++;
        k++;
        operations += 3;
    }
    while (j < r)
    {
        a[k] = right[j];
        j++;
        k++;
        operations += 3;
    }
}

void print_array(int *a, int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void swap(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

输出-

0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms
0.00000000000000000000000000000000000000000000000000ms

Answer 1

代码有一个错误：printf("%.50fms\n", t); 你为 %f 转换传递了一个 clock_t 参数，它期望它的参数来自不同的地方，即浮点寄存器，对于某些人来说原因包含 0.0。您应该改为 printf("%.3fms\n", time_taken);。

停止时钟后也移动printf("%.3fms\n", time_taken);。打印数组可能比排序它的成本更高。

计算算法的执行时间

Calculate time of Execution for an Algorithm

c

algorithm

double

time

mergesort