Calcolo complessità algoritmi

[drakend]

Salve,
volevo sapere se esiste un programma che, dato un certo sorgente in ingresso, restituisca la complessità delle varie funzioni: mi interessa soprattutto per il C.

[Ziosilvio]

Se stai chiedendo se c'e' un programma che, data una funzione, restituisce il suo ordine di complessita' temporale: credo che non possa proprio esistere (a naso, direi che la sua esistenza implicherebbe la decidibilita' per il problema della fermata di Turing).

Una cosa un po' piu' pratica --- e utile: una funzione complicata che viene chiamata una volta sola, incide meno di una funzione piccola che viene chiamata tantissime volte --- e' tener conto del tempo di processore impiegato dalle singole funzioni durante un'esecuzione di un programma: credo che parecchi debugger lo facciano...

[drakend]

Originariamente inviato da Ziosilvio
Una cosa un po' piu' pratica --- e utile: una funzione complicata che viene chiamata una volta sola, incide meno di una funzione piccola che viene chiamata tantissime volte --- e' tener conto del tempo di processore impiegato dalle singole funzioni durante un'esecuzione di un programma: credo che parecchi debugger lo facciano...
Parecchi debugger tipo quali? Io sono ancora inchiodato al Turbo C :D
Sì lo so è vecchio e vetusto, però è l'unico che conosco che ha compilatore e debugger integrato...
C'è anche il dev-c, ma non ho ben capito come usarlo... conosci qualche tutorial online in merito?

[ball12]

Bè, la complessità la puoi verificare in base al numero di operazioni di assegnamento, incremento, decremento, ecc ecc incrementando delle variabili e facendo la stampa del numero di volte che viene chiamata.

Ciao