Mi è stato chiesto di creare un profilo (utilizzando alcuni strumenti, come YourKit o JVisualVM) un paio di implementazioni del Problema del venditore ambulante (trovare il percorso minimo che visita tutto il gruppo dato di città), nel contesto di un'analisi degli algoritmi e corso di laurea in Design.
Considerando l'approccio della forza bruta dell'algoritmo, mi chiedo, tuttavia, come utilizzare al meglio gli strumenti (ad esempio, JVisualVM) per analizzare le complessità spaziali e temporali dell'algoritmo. Se non sono in errore, l'algoritmo ha una complessità spaziale di O (n), in quanto cresce sostanzialmente in modo lineare con il numero di città, mentre è O (n!) Nella complessità temporale.
La matematica non è il problema qui.
Dopo aver giocato un po 'con entrambi gli strumenti di riferimento, ho difficoltà a capire come possono essere utili al mio problema.
Certo, posso vedere quali metodi vengono utilizzati di più e quale% del tempo viene utilizzato in ognuno di essi, e qual è l'effettivo footprint di memoria, in modo che tutti possano essere considerati suggerimenti su dove ottimizzare.
Ma a parte questo, oltre a vedere la% della CPU che viene effettivamente utilizzata (o gli accessi IO, che non si verificano mai in questo programma), non riesco a vedere come posso imparare qualcosa sull'algoritmo con questi strumenti rispetto alla matematica prima di cui non ha fatto.
Quali dovrebbero essere le mie principali preoccupazioni quando utilizzo i profiler per l'analisi degli algoritmi? Inoltre, ho inserito le funzionalità di registrazione del tempo di base incorporate nel mio programma. Forse potrei usare gli strumenti di profilazione per fare meglio quel lavoro?
Grazie