Какова временная сложность следующей программы?

Question

#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) возвращает количество тактов времени, прошедших с момента запуска программы. Чтобы получить количество секунд, используемых процессором, вам необходимо разделить на CLOCKS_PER_SEC.

В 32-битной системе, где CLOCKS_PER_SEC равно 1000000, эта функция будет возвращать одинаковое значение примерно каждые 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 или нет.