Dark_Tranquillity
16-02-2004, 10:45
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;
}
}
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;
}
}