Trovare l'efficienza di un algoritmo.

[indovina]

Ho da giorni un dubbio fortissimo: come calcolare l'efficienza rispetto allo spazio e al tempo di un algoritmo.
A lezione si è detto che tutto dipende dal programma e quando calcoli lo pseudocodice devi mettere tipo: $o(n)$ $o(nlogn)$ e così via...
ma non riesco a capire bene se ci sia o meno una 'sequenza logica' per capire come si calcola.
Grazie.

[hamming_burst]

Ciao,
benvenuto nel mondo dell'algoritmica e della complessità computazionale

La complessità dipende da due cose:

- l'algoritmo
- il problema da risolvere

ti dico subito che per il problema non è sempre intuitivo calcolarne una complessità (limite inferiore), ma per la complessità di un algoritmo invece non è complesso.

Dipende dal tipo di algoritmo, se ricorsivo o meno, quelli iterativi sono quelli più intuitivi da comprenderne e calcolare la complessità.

Che problemi hai nel comprendere il calcolo, non capisci cosa fare?

Consiglio di leggere questo post:

https://www.matematicamente.it/forum/pos ... tml#474675

mostro un po' i passaggi e le idee per iniziare il ragionamento.

poi ti consiglio di leggere le dispense messe qua:

https://www.matematicamente.it/forum/pos ... tml#479901

sezione "Analisi degli algoritmi".

Se ha i problema basta chiedere.

[indovina]

Ho dato una sbirciatina ai link che mi ha segnalato, e nel primo ho notato che quelle cose non le abbiamo mai fatte, anche perchè questa branca dell'informatica non la facciamo, purtroppo a noi viene data più come una cosa 'se capisci, capisci', purtroppo vorrei in linea generale capire quando dire se un algoritmo è di tipo $o(n)$ o $o(nlogn)$
posto un mio codice:

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

main()
{
 	  int *p;
 	  
 	  p = (int *)malloc(10 * sizeof(int));
 	  if( p == NULL ){//verifica
	  	  printf("errore: memoria nn disponibile\n");
	  	  exit(1);
		  }
		  *p = 10;
		  printf("l'indirizzo di p e\': %x\n *p = %d\n", p, *p);
		  free(p); //libera la memoria allocata
		  getchar();
}

come dovrei 'operare'? Inoltre scrivere lo pseudocodice significa dire passo passo cosa si è fatto nel codice?
Scusa per questi dubbi banali, ma devo risolverli al più presto xD

[vict85]

"clever":Ho dato una sbirciatina ai link che mi ha segnalato, e nel primo ho notato che quelle cose non le abbiamo mai fatte, anche perchè questa branca dell'informatica non la facciamo, purtroppo a noi viene data più come una cosa 'se capisci, capisci', purtroppo vorrei in linea generale capire quando dire se un algoritmo è di tipo $o(n)$ o $o(nlogn)$
posto un mio codice:

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

main()
{
 	  int *p;
 	  
 	  p = (int *)malloc(10 * sizeof(int));
 	  if( p == NULL ){//verifica
	  	  printf("errore: memoria nn disponibile\n");
	  	  exit(1);
		  }
		  *p = 10;
		  printf("l'indirizzo di p e\': %x\n *p = %d\n", p, *p);
		  free(p); //libera la memoria allocata
		  getchar();
}

come dovrei 'operare'? Inoltre scrivere lo pseudocodice significa dire passo passo cosa si è fatto nel codice?
Scusa per questi dubbi banali, ma devo risolverli al più presto xD

Direi che è costante. Ma d'altra parte non c'è neanche un n su cui calcolare il comportamento... E' un esempio di cui ha poco senso calcolare la complessità.