[C] Complessità di spazio

[Metallica]

Qualcuno mi saprebbe dire qual'è la complessità di spazio di questo algoritmo:

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

[infinitejustice]

Se quella di ris[] è costante indipendentemente da n, allora è n (la dim di A).

[Metallica]

ris[] è sempre di size 3, perchè la iniziallizzo a 3 nella funzione....

quindi dovrebbe essere sempre 3 e quindi dovrebbe esse sempre S(n)=n, giusto?

[Metallica]

up

[infinitejustice]

Ma nn l'hanno spiegata la complessità asintotica spaziale?

Tu devi trovare la complessità di spazio e tempo di un algoritmo in funzione di un certo numero di dati di input n (quando è abb. grande).

Visto che tutti i valori li sono o costanti o singole istruzioni (complessita 1) ti conta solo n.

Ad esempio il Mergesort non ha n perche utilizza un array supplementare la cui dimensione varia a seconda di n.