Newsgroup: it.comp.lang.c
Titolo: Funzione Empirica (???)

Devo finire un cavolo di "progettino" per l'Univ. Per chi fosse interessato
lo trova a
http://www.mat.uniroma2.it/~giammarr/Teaching-0203/LabInf2/Esercizi/index.ht
ml in basso.
Il mio problema nasce sulla seguente frase:
"Eseguire il programma su array di varie lunghezze e cercare di calcolare
empiricamente le funzioni complessità relativamente al numero di confronti
e/o al numero di scambi effettuati dall'algoritmo. "
Tutto ok per il numero di confronti e  il numero di scambi...ma poi Trovo
difficoltà con l'implementazione (ma anche con la teoria :_(   ) in C per le
funzioni di complessità. Non credo che il prof. voglia solamente una
descrizione del tipo: "L'algoritmo ha un andamento asintotico dell'ordine di
O(n^2) etc etc etc" ... ma lo voglia calcolato *precisamente* sul
caso particolare:
Esempio: su un vettore ordinato di lunghezza 10 il numero di confronti è 9,
il numero di scambi è 0 allora la funzione è di ...(boh non so cosa
aggiungere)???
Ringrazio chi vorrà illuminarmi
Buon proseguimento a tutt l'NG!

 aggiungere)???
La cosa migliore, per esperienza, e' sempre chiedere al prof. cosa vuole...
a volte e' difficile indovianare ;-)
Poi la mia personale interpretazione e':
scegli uno dei due algoritmi proposti, testalo con un array ordinato, uno
ordinato al contrario, uno con numeri in ordine casuale e se vuoi qualche
altro caso. Usa una variabile per contare il numero di scambi (o confronti o
entrambi, ma inizia con gli scambi).
int numero_scambi=0; poi per ogni swap fai ++numero_scambi.
Ricordati di usare array abbastanza grandi (ma puoi fare anche un test con
un array piccolo), e' importante pero' che tu non ti limiti ai 10 elementi
di cui parli, sono pochi pochi!
Usa questi dati per comporre un tabella e raffigurarli in modo chiaro con un
grafico.
Tendenzialmente cerca di mostrare il caso migliore, peggiore ed il caso
medio.
Successivamente usar tutti i dati per arrivare empiricamente (dalla pratica)
a definire le complessita' computazionali dell'algoritmo scelto (cone le
varie notazioni studiate).
Per finire magari mostra che applicando i metodi insegnati per calcolare
(non empiricamente) la complessita' computazione di un algoritmo danno
risultati simili (o identici). E' sempre utile mischiare teoria e pratica.
Ora un esempio BANALE:
Se ti faccio vedere il seguente algoritmo e' facile capire che l'istruzione
++count verra' eseguita M_MAX*N_MAX volte.
#include <stdio.h>
#define M_MAX 100
#define N_MAX 75
int main()
{
      int m,n;
      int count=0;
      for(m=0;m<M_MAX;++m){
            for(n=0;n<N_MAX;++n){
                  ++count;
            }
      }
      printf("Count is %d\n",count);
      return 0;
}
La tecnica di moltiplicare i cicli nidificati (in parole molto povere) e' la
regola piu' semplice. Bene questa e' una regola teorica...
La vuoi empirica?!? Esegui il programma e a schermo troverai scritto 7500.
Proca con M_MAX 2 e N_MAX 500 e troverai scritto 1000. Ecco che teoria e
pratica si trovano d'accordo ;-)
Il tuo esercizio e' leggermente piu' difficile. Avrai best-case, worst-case,
average-case e qualche altra complicazione... ma... in pratica il principio
e' molto simile! Spero di non averti annoiato con questo esempio fin troppo
banale.
Se hai problemi posta pure.
Tommy

"Shaden" <simonet...@virgilio.it.LEVATE.STO.MAIUSCOLO> ha scritto nel
messaggio news:nXxta.45809$3M4.1...@news1.tin.it...

Penso che voglia una cosa del genere:
int n = 0;
while(i < 1000) {
    n++;
    ...
}
all fine n ti dirà quanti confronti, operazioni ecc sono stati fatti,
dipende da dove metti gli n++.
Poi confrontalo con la lunghezza del vettore e traine le conseguenze sulla
complessità dell'algoritmo in quel caso particolare ovviamente.
Ciao.
Alberto.

 Grazie di cuore per le risposte!
Farò un pò di mente locale con i preziosi consigli, e , vedo se riesco a
tirarne fuori qualcosa.
Se mi troverò nel panico totale mi farò risentire:-)
Ma penso che ormai mi dovrete subire ogni settimana :(
Buon Proseguimento!