Complexité temporelle d'un algorithme de tri

Question

Les deux programmes ci-dessous obtiennent n entiers à partir du fichier et calculent la somme de ath à bth entiers q (nombre de questions) fois. Je pense que le programme supérieur a une complexité de temps pire que la plus faible, mais j'ai des problèmes pour calculer la complexité temporelle de ces deux algorithmes.

[input sample] 
5 3 
5 4 3 2 1 
2 3 
3 4 
2 4 

[output sample] 
7 
5 
9 

Programme 1:

#include <stdio.h> 

FILE *in=fopen("input.txt","r"); 
FILE *out=fopen("output.txt","w"); 

int n,q,a,b,sum; 
int data[1000]; 

int main() 
    int i,j; 
    fscanf(in,"%d%d",&n,&q); 
    for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]); 
    for i=0;i<q;i++) 
    { 
     fscanf(in,"%d%d",&a,&b); 
     sum=0; 
     for(j=a;j<=b;j++) sum+=data[j]; 
     fprintf(out,"%d\n",sum); 
    } 
    return 0; 
} 

Programme 2:

#include <stdio.h> 

FILE *in=fopen("input.txt","r"); 
FILE *out=fopen("output.txt","w"); 

int n,q,a,b; 
int data[1000]; 
int sum[1000]; 

int main() 
{ 
    int i,j; 
    fscanf(in,"%d%d",&n,&q); 
    for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]); 
    for(i=1;i<=n;i++) sum[i]=sum[i-1]+data[i]; 
    for(i=0;i<q;i++) 
    { 
     fscanf(in,"%d%d",&a,&b); 
     fprintf(out,"%d\n",sum[b]-sum[a-1]); 
    } 
    return 0; 
} 

Les programmes ci-dessous obtient n entiers de 1 à m et les trie. Encore une fois, je ne peux pas calculer la complexité du temps.

[input sample] 
5 5 
2 1 3 4 5 

[output sample] 
1 2 3 4 5 

Programme:

#include <stdio.h> 
FILE *in=fopen("input.txt","r") 
FILE *out=fopen("output.txt","w") 

int n,m; 
int data[1000]; 
int count[1000]; 

int main() 
{ 
    int i,j; 
    fscanf(in,"%d%d",&n,&m); 
    for(i=0;i<n;i++) 
    { 
     fscanf(in,"%d",&data[i]); 
     count[data[i]]++ 
    } 
    for(i=1;i<=m;i++) 
    { 
     for(j=0;j<count[i];j++) fprintf(out,"%d ",i); 
    } 
    return 0; 
} 

Il est ironique (ou non) que je ne peux pas calculer la complexité temporelle de mes propres algorithmes, mais je passions à apprendre, donc s'il vous plaît gourous de programmation, aide-moi!

Answer 1

Ce que vous devez faire est de faire attention aux boucles, en particulier combien de fois les boucles se répètent, et combien de temps est passé à l'intérieur des boucles. Vous devez multiplier le nombre de répétitions de la boucle externe par le temps qu'il faut à l'intérieur de la boucle ... s'il y a une boucle interne, multipliez le nombre de répétitions de la boucle externe par le nombre de répétitions de la boucle interne boucle, par exemple, pour obtenir la complexité du temps.

Dans votre premier programme, vous avez une boucle qui prend le temps O (n) suivi d'une boucle qui prend le temps O (q * (ba)) ... je ne comprends pas exactement ce que b et représenter ... mais si vous pouvez lier ba (disons, vous savez que ba < n), alors vous pouvez exprimer cela plus simplement (par exemple si ba < n, alors vous diriez que c'était O (q * n)). Le temps d'exécution global serait la somme de ces deux termes, ou, si un terme est toujours plus grand que l'autre, utilisez le terme plus grand. Dans le second programme, vous avez deux boucles, chacune prenant l'heure O (n), suivie d'une boucle qui prend l'heure O (q). Donc, l'exécution globale est O (n + q). Notez que si un terme domine l'autre, vous pouvez supprimer le terme qui est plus petit. Même sans connaître la valeur de (b-a), il est déjà évident que c'est mieux que le premier. Dans le troisième programme, l'exécution globale est O (n + m), car vous avez une boucle qui prend l'heure O (n) suivie d'une boucle qui prend l'heure O (m). Si vous savez que m < n ou vice-versa, vous pouvez simplifier l'expression en supprimant le terme dominant. S'ils peuvent varier de sorte que vous ne sachiez pas que l'un domine l'autre, alors l'écrire comme O (m + n) est ce que vous pouvez faire de mieux en termes de temps-complexité.

Je devrais également souligner que même si une boucle est effectuée plus d'une fois, mais il est effectué un nombre fixe de fois (par exemple dans le programme 2, vous avez deux boucles qui prennent O (n) temps), il doesn n'affecte pas la complexité temporelle, car O (2n) est identique à O (n); en d'autres termes, les facteurs constants n'ont pas d'importance dans l'analyse de complexité. De plus, si vous avez une boucle interne qui varie en fonction du nombre de fois où elle est exécutée, si vous effectuez une analyse de complexité «dans le pire des cas», vous n'avez besoin que de connaître la pire valeur possible.

Par exemple, considérons la boucle suivante:

 
for (int i = 0; i < n; i++){ 
    for (int j = i+1; j < n; j++){ 
     // something taking O(1) time 
    } 
} 

La boucle prend au-dessus de O (n^2) le temps, même si toutes les boucles internes prendront O (n).

Je voudrais également ajouter que vous devriez faire un meilleur travail de formatage de votre programme. Même si les accolades ne sont pas strictement requises lorsqu'une instruction if/for/while n'a qu'une seule instruction dans le corps, il est beaucoup plus facile d'utiliser les accolades et d'utiliser une nouvelle ligne. Par exemple, il est beaucoup plus lisible si vous écrivez:

 
for (int i=1; i<=n; i++) { 
    sum[i]=sum[i-1]+data[i]; 
} 

que d'écrire comme for (i=1; i<=n; i++) sum[i]=sum[i-1]+data[i];. Aussi, je dois préciser que même si vous avez étiqueté cette question comme C++, vous utilisez du code C ... en C++, vous pouvez déclarer des variables dans l'initialisation de la boucle for (je vous suggère de le faire). Egalement, en C++, les iostreams library (std::cin, std::cout, , std::ostringstream, std::istringstream, etc.) sont préférés aux objets C FILE *.

Vous pouvez également être intéressé par la ressource suivante:

• Stanford University: Analysis of Algorithms de Google Code University