[C++] Complessità asintotiche di funzioni che effettuano elaborazioni su liste

[pcg4m3s]

salve ragà... ho fatto un programma che deve fare due elaborati sulla stessa lista.
secondo voi è meglio (in termini di complessità) se faccio tutto nel main o se faccio 2 funzioni separate? secondo me è uguale... voi che dite?

[deleted_26]

io penso ke con due funzioni separate ti è più facile gestire eventuali modifiche future.
ovviamente dipende anke dal numero di istruzioni presenti. se poi puoi raggruppare tutto in una sola funzione (usando dei parametri per variare) è anke meglio...

[devil89]

non ha senso parlare di complessità (sempre se intendi complessità computazionale) nel tuo caso.
Casomai di tratta di strutturare il codice che è una cosa diversa

[ivanet]

In termini di complessità, dipende da che tipo di costrutti usi e nel caso di funzioni se vi è ricorsione si deve tenere conto dell'esecuzione delle linee di codice comuni a tutti i richiami più il tempo speso per la chiamata ricorsiva....
Dipende a parer mio come strutturi l'algoritmo per la risoluzione del problema.

[pcg4m3s]

vi faccio un esempio.

Meglio così:

void main()
{
	// bla bla bla
        ...

	Lista* l = new Lista[300000];

	// riempio la lista

       ...
 		while( condizione )
		{
			...
			
			while(condizione)
			{
				...

				while(condizione)
				{
					...
						while(condizione)
						{
							...
						}
						...			
				}
			}
		} 

                ...

		while( condizione )
		{
			...
			while( condizione )
			{
				...
				while( condizione )
				{
					...
				}
			}
		}
		...
                delete [] l;
}

o così:

void funzione1(Lista[],int&,int&,char[]);
void funzione2(Lista[],int&);

void main()
{
	// bla bla bla
        ...

	Lista* l = new Lista[300000];

	// riempio la lista

       funzione1(l,i,n,nome);
       funzione2(l,n);
       

       delete [] l;
}

void funzione1(Lista[] l,int& i,int& n,char[] nome)
{
while( condizione )
		{
			...
			
			while(condizione)
			{
				...

				while(condizione)
				{
					...
						while(condizione)
						{
							...
						}
						...			
				}
			}
		} 
}

void funzione2(Lista[] l,int& n)
{
while( condizione )
		{
			...
			while( condizione )
			{
				...
				while( condizione )
				{
					...
				}
			}
		}
}

Io penso che in termini di TEMPO DI ESECUZIONE non ci sia differenza, o uno dei due modi è più veloce?

[scancode]

Calcola il tempo di esecuzione... e avrai la risposta!

In scienza si formula un ipotesi e poi si verifica!

[pcg4m3s]

Originariamente inviato da scancode
Calcola il tempo di esecuzione... e avrai la risposta!

In scienza si formula un ipotesi e poi si verifica!

a intuito mi verrebbe da dire che il primo metodo è più veloce... perchè richiamando le due funzioni andrei a fare delle copie delle liste (fa le copie delle liste o le passa per riferimento??)..


come lo calcolo scusa?

[nomida]

beh spero bene che non ci siano tutti i while che hai scritto perche' altrimenti avrebbe una complessita' computazionale un pelo "alta"!


Poi non si calcola mai il tempo di esecuzione di un programma in tempo e' sbagliato!!!!!!
Ci sono abbastanza cose da studiare pero' non sono gran difficili il famoso "O grande"!pero' tutto dipende a che ti serve questo programma o algoritmo

[scancode]

Originariamente inviato da pcg4m3s
a intuito mi verrebbe da dire che il primo metodo è più veloce... perchè richiamando le due funzioni andrei a fare delle copie delle liste (fa le copie delle liste o le passa per riferimento??)..


come lo calcolo scusa?

Così si calcola:

t1=clock;
for i=computa
...code
next
t2=clock;
tTot1=t2-t1;

t1=clock;
while{
...code
}
t2=clock;
tTot2=t2-t1;

t1=clock;
while(condizione)
{
while(condizione)
{
while(condizione)
{
}
}
}
t2=clock;
tTot3=t2-t1

printf(tTot1, tTot2, tTot3);

Ora hai i risultati in ms. Per vederne le ore i minuti i secondi e perchè no i millisecondi... ti fai la conversione nel formato hh:mm:ss e ms.

chiaro?

Il temp preso è perfetto... anche se ad alcuni utenti sembra che il compilatore nel momento che è avviato perda alcuni millessimi di secondo ma questo è dato solo dal fatto dal caricamento dei dati in memoria da parte del compilatore. Il tempo, una volta avviato il prg, è assolutamente perfetto.

[nomida]

ma perche' questo c'e' una teoria sotto per il calcolo della complessita' computazionale!!!!non si dovrebbe far cosi!!!eh che cavoli!!!le cose si studiano a tavolino e poi al max si calcola il tempo andando a modificare parti di codice per renderlo piu' performante!!!