calcolare la complessità non è in genere un gran lavoro (se l'algoritmo è semplice): basta guardare a occhio il numero di operazioni che verranno fatte e cercare di dare una stima... O(n) significa che verranno fatte un numero di operazioni che aumenta in maniera lineare all'aumentare della dimensione del dato da trattare n.
il programma in questione è composto da molte funzioni... non credo che abbia senso calcolare il caso ottimo e quello pessimo del programma intero, andrebbero piuttosto prese in esame le singole funzioni!
secondo me,trattandosi di operazioni su matrici, se l'algoritmo è ottimo, le funzioni inserimento, lettura, calcolo media, valoremax e valoremin non specificamente un caso ottimo e pessimo... la loro complessità aumenta con l'aumentare della dimensione della matrice e diminuisce se la dimensione della matrice è più ridotta.
per il prodotto tra matrici invece il discorso è diverso, e un po' più complesso... la complessità del calcolo può variare permutando l'ordine delle matrici che si stanno moltiplicando... da quel che mi ricordo dall'esame di algoritmi è una questione di programmazione dinamica, ma nn so se c'entra in questo caso.
se una funzione comtiene due cicli for nidificati,
uno che va da 1 a l e l'altro da 1 a m, quei cicli faranno circa n * l iterazioni... da qui ne deriva la complessità.
secondo me non ci sono dei casi di minimo e massimo molto eclatanti.. se non quelli intrinseci nel concetto matematico della funzione implementata.
Ultima modifica effettuata da eddiewrc il 17/01/2009 alle 14:36 |