Dato un pezzo di codice, potrei usare uno dei tanti metodi per determinare manualmente la grande complessità O del codice (runtime e memoria).
Ma, per un dato pezzo di codice, come posso determinare se ciò che ho trovato prima sia corretto o no? Sono disponibili strumenti in cui fornisco un EXE, fornisco casi di test e ottengo un output che dice che il runtime è O (n ^ 2) e l'utilizzo della memoria è O (1) per esempio?
AFAIK, non ci sono tali strumenti. Google non ne ha trovato uno per me. Ma sentiti libero di guardare di nuovo :-)
In realtà, non mi aspetto che uno strumento autonomo sia accurato ... o generalmente utile.
È improbabile che sia accurato perché ci sono tutti i tipi di fattori in un'applicazione tipica che distorcono i dati sulle prestazioni che è possibile misurare "dall'esterno". Ad esempio, il comportamento di un garbage collector tipico.
È improbabile che sia utile per un paio di motivi:
Le misure di complessità Big-O sono generalmente applicate a parti specifiche di un programma piuttosto che a un programma nel suo insieme.
Per un programma tipico, i parametri di ridimensionamento implicano la dimensione dei file di input. Nella maggior parte dei casi, non è possibile per uno strumento generale di "misurazione della complessità" generare file di input significativi di varie dimensioni.
Infine, quando abbiamo un'applicazione completa / funzionante, la complessità di O-O è in gran parte di interesse accademico. Ciò che è veramente interessante sono le reali misure performance ; vale a dire quanto tempo e spazio effettivi sono necessari per eseguire l'applicazione per un determinato set di dati / parametri. La complessità del Big-O non lo prevede.
Leggi altre domande sui tag complexity