Esistono strumenti in grado di determinare l'esecuzione di analisi del codice per la complessità di Big-O?

Question

Non ho visto nulla là fuori e sospetto la difficoltà con la definizione di " n " poiché per l'analisi generale di una funzione complessa ci sarebbero più di una o due variabili per la definizione.

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

Idealmente ci sarebbe qualcosa di simile alla complessità generale per l'applicazione (che definisce diversi possibili "n") nonché per ogni metodo nell'app

Modifica: quindi sembra che una soluzione esatta sia impossibile a causa del Halting Problem , tuttavia, è possibile una sorta di approssimazione euristica? Mi rendo conto che ai fini pratici un buon profiler fornirà informazioni molto più utili, ma sembra un problema interessante.

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

Answer 1

Sfortunatamente c'è questo problema chiamato Problema di arresto ...

Answer 2

No, questo non è possibile a causa del problema di arresto.

Se desideri farlo per migliorare le tue applicazioni, potresti prendere in considerazione la profilazione. Ti consentirebbe di individuare ciò che sta realmente impiegando più tempo. In questo modo non perdi tempo a ottimizzare un algoritmo O (n ^ 3) che viene eseguito solo su piccoli set di dati.

Answer 3

Alcune considerazioni:

I computer reali sono macchine a stati finiti approssimativamente deterministici, quindi il problema di arresto non è in realtà una limitazione pratica. Una limitazione pratica è un algoritmo che richiede più tempo per l'esecuzione di quanto si senta di aspettare, escludendo qualsiasi metodo di analisi della forza bruta.

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

L'analisi della complessità temporale degli algoritmi può essere abbastanza complicata, richiedendo alcuni passaggi creativi. (Vedi ad esempio analisi di quicksort). Il problema è strettamente legato alla dimostrazione del teorema logico e alla verifica del programma. Potrebbe essere fattibile costruire uno strumento utile che consenta una soluzione semiautomatica della complessità, ovvero uno strumento che cerca sistematicamente soluzioni fornite dai suggerimenti di un essere umano, ma certamente non è facile.

Answer 4

Non ho mai visto uno strumento per farlo, ma utilizziamo strumenti di profilazione per avere un'idea migliore di dove siano i colli di bottiglia. Non è sempre ovvio e sono stato sorpreso alcune volte da cose che pensavo impiegassero molto tempo in realtà prendendo pochissimo e viceversa. Nel mondo .NET, ho usato ANTS e il < a href = "http://www.jetbrains.com/profiler/" rel = "nofollow noreferrer"> strumenti JetBrains .