Esistono strumenti che possono determinare l'esecuzione dell'analisi del codice per la complessità Big-O?

Question

Non ho visto niente là fuori, e sospetto la difficoltà con la definizione di "n" dato che generalmente per analizzare una funzione complessa ci sarebbe più di una o due variabili da definire.

Esistono strumenti di analisi per la complessità ciclomatica ma ce ne sono per la complessità del tempo (e/o dello spazio)? Se sì quali, se no, perché no? È impossibile? Impossibile? Qualcuno non ci è riuscito?

Idealmente ci sarebbe qualcosa di simile complessità generale per l'applicazione (che definisce diverse possibili "n" s), così come per ogni metodo in app

Edit: Così sembra che una soluzione esatta è impossibile perché del Halting Problem tuttavia, è possibile una qualche approssimazione euristica? Mi rendo conto che a fini pratici un buon profiler darà molte più informazioni utili, ma sembra un problema interessante.

Inoltre, che ne dici di uno che calcola per un certo sottoinsieme di programmi?

Answer 1

Purtroppo c'è questo problema chiamato il Halting problem ...

Answer 2

No, questo non è possibile, a causa del problema della terminazione.

Se si desidera eseguire questa operazione per migliorare le applicazioni, è possibile prendere in considerazione la creazione di profili. Ti permetterebbe di definire in modo preciso ciò che richiede più tempo. In questo modo non si spreca tempo a ottimizzare un algoritmo O (n^3) che funziona solo su piccoli set di dati.

Answer 3

Non ho mai visto uno strumento per farlo, ma utilizziamo strumenti di profilazione per avere un'idea migliore di dove sono i colli di bottiglia. Non è sempre ovvio e sono stato sorpreso un paio di volte da cose che ho pensato che impiegare molto tempo effettivamente prendendo molto poco e viceversa. Nel mondo .NET, ho usato ANTS e gli strumenti JetBrains.

Answer 4

Alcune thoughs:

computer reali sono circa deterministici macchine a stati finiti, così il problema della terminazione non è in realtà una limitazione pratica. Una limitazione pratica è un algoritmo che richiede più tempo per l'esecuzione di quanto tu voglia aspettare, escludendo i metodi di analisi della forza bruta.

Per avere un'idea approssimativa della complessità di un algoritmo, è sempre possibile eseguirlo su una serie di input casuali e misurare il tempo impiegato. Quindi traccia una curva attraverso i dati.

L'analisi della complessità temporale degli algoritmi può essere piuttosto complicata e richiede alcuni passaggi creativi. (Vedi ad esempio l'analisi di quicksort). Il problema è strettamente correlato alla dimostrazione teorica logica e alla verifica del programma. Potrebbe essere fattibile costruire uno strumento utile che consenta la soluzione semiautomatica della complessità, ovvero uno strumento che ricerca sistematicamente soluzioni fornite da suggerimenti umani, ma certamente non è facile.