c - 以下程序的时间复杂度是多少？

Question

这个问题已经有答案了:

Observing quadratic behavior with quicksort - O(n^2) (3 个回答)

已关闭 8 年前。

#include <stdio.h>

void partition(int a[],int p,int r)
{

    int q;
    if(p<r)
    {
        q=quicksort(a,p,r);
        partition(a,p,q-1);
        partition(a,q+1,r);
    }
}

int quicksort(int a[],int p,int r)

{

    int pivot=p;
    int f=p,temp;
    int l=r;

    while(f<l)
    {
        while(a[f]<=a[pivot])
        f++;
        while(a[l]>a[pivot])
        l--;
        if(f<l)
        {
            temp=a[f];
            a[f]=a[l];
            a[l]=temp;
        }
    }
    temp=a[pivot];
    a[pivot]=a[l];
    a[l]=temp;
    return l;
}

int main(void)

{

    // your code goes here
    int n;
    scanf("%d",&n);
    int a[n];
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    partition(a,0,n-1);
    for(i=0;i<n;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

这是一种快速排序算法，我的问题是它是否需要比 O(nlogn) 更多的时间复杂度。

Answer 1

您可以使用clock()函数来计算代码执行所需的时间。

C 库函数clock_t Clock(void) 返回自程序启动以来经过的时钟周期数。要获取 CPU 使用的秒数，您需要除以 CLOCKS_PER_SEC。

在 CLOCKS_PER_SEC 等于 1000000 的 32 位系统上，此函数大约每 72 分钟返回相同的值。

示例代码:

#include <time.h>
int main()
{
    clock_t begin, end;

    begin = clock();

    //your code here

    end = clock();

    printf("Elapsed: %f seconds\n", (double)(toc - tic) / CLOCKS_PER_SEC);

    return 0;
}

为了凭经验测量程序的时间复杂度，您需要多个数据点。针对n的多个值运行程序，然后制作n与时间的图表。看看它是否类似于nlogn图。