[C] Ancora sulla complessità di tempo e spazio

[Dark_Tranquillity]

Avendo un algoritmo di exchage sort indicato sotto qualcuno mi direbbe su che valori è la complessità di tempo e spazio??? Grazie

#include <stdio.h>
#include <malloc.h>

/* PROTOTIPO FUNZIONE */
void ex_sort(float *A, int n);

main() {

/* DICHIARAZIONE VARIABILI */
int i, n, c;
float *A;

	/* LETTURA GRANDEZZA ARRAY */
	printf("Inserire la grandezza n dell'array: ");
	scanf("%d",&n);

	/* ALLOCAZIONE DINAMICA DELLA MEMORIA */
	if(!(A = (float *)malloc(n*sizeof(float))))
	abort();

	/* LETTURA DI TUTTI GLI ELEMENTI DELL' ARRAY A */
	printf("\nInserire uno per uno tutti gli elementi dell'array...\n");
	   for (i=0; i<n; i++){
	      printf("Inserire il %d° elemento: ", c=i+1);
	      scanf("%f", &A[i]);
	   }

	/* RICHIAMO DELLA FUNZIONE */
	ex_sort(A, n);

	/* STAMPA A VIDEO DELL'ARRAY ORDINATO */
	printf("\nL'array A è ora ordinato come segue:\n");
	for (i=0; i<n; i++)
	printf("%f\n", A[i]);
}

/****************** SPECIFICHE FUNZIONE *************************/
void ex_sort(float *A, int n){
int p,K,i,var;
	p = n;
	do {
	   K = 0;
	   for(i=0; i<n-1; i++)
	   {
	      if(A[i]>A[i+1])
	      {
	      var = A[i];
	      A[i] = A[i+1];
	      A[i+1] = var;
	             K = 1;
	             p = i+1;
	      }
	   }
	n = p;
	   } while (K==1);
}

[cionci]

Per la complessità di tempo è facile...

Prendi il caso peggiore... Cioè quello in cui tutto il vettore sia ordinato nel senso opposto... E per sapere la complessità di tempo l'istruzione il pezzo di codice fondamentale (cioè quello che contribuisce alla complessità) è l'if che da il via allo scambio...

Ora ci dovresti arrivare da solo altrimenti non impari niente Ovviamente invito anche gli altri, per il suo bene, a non spiattegliare la soluzione... Almeno per la complessità di tempo...

[Dark_Tranquillity]

no no ma io credo di esserci arrivato dovrebbe essere la dimensione n-1 giusto?
in quanto dovrebbero essere n-1 confronti... toppato?

o forse n^2

[cionci]

ok per n-1 confronti, ma quante volte viene eseguito l'intero ciclo for ?

[Dark_Tranquillity]

n-1 volte

[cionci]

Quindi in totale quante volte viene eseguito l'if interno al for se viene eseguito n-1 uno volte dal for e il for viene eseguito n-1 votle ?

[Dark_Tranquillity]

n-1 volte al quadrato?

[cionci]

Sì...e quindi ? (n-1)*(n-1) ha complessita di ordine O(n^2)

[Dark_Tranquillity]

Originariamente inviato da cionci
Sì...e quindi ? (n-1)*(n-1) ha complessita di ordine O(n^2)

grazie mille
per la complessità di spazio invece 7 interi ed un float in tutto il prgramma.

[Luc@s]

[OT]
ma sei Metallica di html.it?????
Ti ricordi di me???

Ciauz

[cionci]

Originariamente inviato da Dark_Tranquillity
grazie mille
per la complessità di spazio invece 7 interi ed un float in tutto il prgramma.

Ma devi individuare quali dipendono da n...quindi per la complessità di spazio direi n

[Dark_Tranquillity]

Originariamente inviato da Luc@s
[OT]
ma sei Metallica di html.it?????
Ti ricordi di me???

Ciauz

sì sono metallica di HTML.it