[C] Complessità di Spazio

[Dark_Tranquillity]

qualcuno mi saprebbe dire qual'è la complessità di spazio dell'algoritmo seguente:
Si considera solo la complessità della Funzione o di tutto l'algoritmo?
Se mi rispondete mi fte un grande piacere visto che è per l'esame di programmazione

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

/* PROTOTIPO FUNZIONE */
void bin_search(int *A, int n, int chiave, int ris[3]);

/* PROGRAMMA CHIAMANTE */
main()
{
	/* DICHIARAZIONE VARIABILI */
	int *A, out[3], chiave;
	int i, c;
	int n, posiz;

	/* LETTURA ELEMENTI ARRAY */
	printf("Inserire il numero di elementi formanti l'array: ");
	scanf("%d",&n);

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

	/* LETTURA ELEMENTI ARRAY */
	printf("\n");
	for (i=0; i<=n-1; i++){
	printf("Inserire il valore dell'elemento %d: ", c=i+1);
	scanf("%d", &A[i]);
	}

	/* NUMERO DA RICERCARE */
	printf("\nInserire il numero che si desidera individuare: ");
	scanf("%d", &chiave);

	/* RICHIAMO FUNZIONE E STAMPA RISULTATO */
	bin_search(A, n, chiave, out);

	/* VERIFICO SE L’ELEMENTO E’ STATO TROVATO (ovvero se out[0]==1) */
	if(out[0]==1){
	        printf("\nIl valore %d è presente ed è l'elemento %d dell'array!\n", out[1], out[2]+1);}
	else {
        printf("\nIl valore %d non è presente nell'array!\n",out[1]);}

	/* RILASCIO DELLA MEMORIA OCCUPATA DALL’ ARRAY */
	free(A);
return 0;
}

/****************** SPECIFICHE FUNZIONE *************************/
void bin_search(int *A, int n, int chiave, int ris[3]) {
int alto, basso, centro, pos;
	alto = 0; 
	basso = n-1;
	pos = -1;
		do {
		centro = (alto+basso)/2;
			if (A[centro]==chiave)
				{pos = centro;}
			else if (A[centro]<chiave)
				{alto = centro+1;}
			else
				{basso = centro-1;}
			}
		while(alto<=basso && pos==-1);
if(pos!= -1){
	ris[0] = 1;
	ris[1] = chiave;
	ris[2] = pos; }
else {
	ris[0] = 0;
	ris[1] = chiave;
	}
}

[cionci]

Slitamente la complessità si calcola su un algoritmo...in questo caso realizzato in una funzione... Il resto sono informazioni a corredo... Comunque puoi decidere di calcolare la complessità anche di tutto il programma...

Non so (o non mi ricordo) cosa tu intenda per complessità di "spazio"...comunque la complessità computazionale della ricerca binaria è O(log(n))...

E' log(n) perchè si suddivide sempre in due il campo di ricerca...fino ad arrivare al punto in cui non possiamo più suddividere...

Nota che gli elementi inseriti devono essere ordinati in ordine crescente...

[maxithron]

vedi se ti è di aiuto:

http://digilander.libero.it/unno2/sort/complessita.htm

[Dark_Tranquillity]

C'è la complessità di tempo e la complessita di spazio....
quella di tempo è: T(n)=O(log base 2 n), e su questo sono sicuro

Invece la complessità di spazio S(n) di un algoritmo è la funzione che esprime il size totale delle strutture dati utilizzate per memorizzare dati di input, locali e di output, in dipendenza della dimensione computazionale n del problema....

Come agisco in questo caso?

PS: cionci bell' avatar e bella signature

[maxithron]

La complessità di spazio riguarda il numero delle variabili dichiarate e utilizzate dall'algoritmo, ed è proporzionale allo spazio di memoria occupato dai dati d'input, d'output e intermedi.


Un altro link che forse può esserti utile:
http://digilander.libero.it/nfragale...roduzione.html

[cionci]

Originariamente inviato da maxithron
La complessità di spazio riguarda il numero delle variabili dichiarate e utilizzate dall'algoritmo, ed è proporzionale allo spazio di memoria occupato dai dati d'input, d'output e intermedi.

Ora mi ricordo...come ci si dimenticano rpesto le cose

[maxithron]

Originariamente inviato da cionci
Ora mi ricordo...come ci si dimenticano rpesto le cose

Sinceramente anch'io l'avevo dimenticato, ho semplicemente riportato quello che è scritto sul link che ho segnalato

[a2000]

le dimenticate perché non le utilizzate.
poi c'è anche chi le utilizza senza ricordarsele.

[cionci]

Originariamente inviato da a2000
le dimenticate perché non le utilizzate.
poi c'è anche chi le utilizza senza ricordarsele.

Beh...sicuramente...almeno io... Piccola perla di saggezza di a2000

[a2000]

ah ecco, come nello sport, nella musica e nell'arte: imparare e dimenticare.

perle ai PC ?

[Luc@s]

 
/*
   Ricerca binaria O(lg n)
   Funzia su array ordinati precendentemente

*/

template<class T>
bool bin_search(const T a[], int last, T target, int& index, int first = 0);

template<class T>
bool bin_search(const T a[], int last, T target, int& index, int first)
{
    int centro;
    if (first > last) 
    	return false;
    else
    {
        centro = (first + last)/2;
        if (target == a[centro]) // META
        { 
 		        index = centro;
 		        return true;
        }
	      // PARTE SINISTRA
        else if (target < a[centro]) bin_search(a, first, centro - 1, target, index);
	       // PARTE DESTRA 
        else if (target > a[centro]) bin_search(a, centro + 1, last, target, index);
        
    }
    return true;		
}

[Dark_Tranquillity]

Nnn riesco a capire.
Qualcuno sarebbe così gentile da dirmi in questo caso quant'è la complessità di tempo del programma???

Grazie

[fpucci]

Originariamente inviato da Dark_Tranquillity
Nnn riesco a capire.
Qualcuno sarebbe così gentile da dirmi in questo caso quant'è la complessità di tempo del programma???

Grazie

La complessità temporale di un albero binario di ricerca è sempre log (base 2)(n).

Forse quella spaziale può essere data dal (numero_di_nodi * sizeof (singolo_nodo))

[Dark_Tranquillity]

ma quindi dovrebbe essere n la complessità di spazio?