[C] complessità tempo e spazio

[Metallica]

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);
}

[infinitejustice]

Sembra Bubblesort con sentinella (k) e limite (p)
:master: perche entrambi?


Spaziale è Θ(n) (in loco)
Temporale direi Ω(n) O(n²)

Qualcuno piu fresco su algoritmi e struct di dati magari puo confermare o correggere

[Metallica]

io con la complessità di spazio mi trovo 7 interi e un array float. sbaglio?

[infinitejustice]

se stai facendo Algoritmi e quindi studi la complessità asintotica le singole variabili e le costanti (nel tempo) nn si calcolano

[Metallica]

Originariamente inviato da infinitejustice
se stai facendo Algoritmi e quindi studi la complessità asintotica le singole variabili e le costanti (nel tempo) nn si calcolano

sto facendo programmazione A....

[infinitejustice]

A... che ?

Io di analisi spazio/tempo di un algoritmo ho sempre solo sentito quella asintotica, anche perchè se no dovresti calcolare tutta una serie di costanti temporali che dipendono direttamente dalla macchina (tempo necessario ad eseguire una singola istruzione)

Generalmente si fa invece in funzione di n, per n suff. grande e si guarda come cresce la funzione temporale/spaziale al crescere di n.