Come calcolare la complessità esatta di un algoritmo?

Question

Senza ricorrere alla notazione asintotica, è noioso fare il conteggio dei passi l'unico modo per ottenere la complessità temporale di un algoritmo? E senza il conteggio dei passi di ogni riga di codice possiamo arrivare a una rappresentazione O grande di qualsiasi programma?

Dettagli: cercando di scoprire la complessità di diversi algoritmi di analisi numerica per decidere quale sarà più adatto per risolvere un particolare problema. E.g. - dal metodo Regula-Falsi o Newton-Rhapson per la risoluzione di eqns, l'intenzione è di valutare l'esatta complessità di ciascun metodo e poi decidere (mettendo il valore di 'n' o qualunque argomento ci sia) quale metodo è meno complesso.

Answer 1

L'unico modo, non il modo "facile" o difficile, ma l'unico modo ragionevole, per trovare la complessità esatta di un algoritmo complicato, è rappresentarlo. Una moderna implementazione di un algoritmo ha un'interazione complessa con le librerie numeriche e con la CPU e la sua unità in virgola mobile. Ad esempio, l'accesso alla memoria in-cache è molto più rapido dell'accesso alla memoria out-of-cache, e per di più potrebbe esserci più di un livello di cache. Il conteggio delle fasi è davvero molto più adatto alla complessità asintotica che tu dici non è sufficiente per il tuo scopo.

Ma, se si desidera contare automaticamente i passaggi, ci sono anche dei modi per farlo. È possibile aggiungere un comando di incremento del contatore (come "bloof ++;" in C) a ogni riga di codice e quindi visualizzare il valore alla fine.

Si dovrebbe anche conoscere l'espressione di complessità temporale più raffinata, f (n) * (1 + o (1)), che è anche utile per i calcoli analitici. Per esempio n^2 + 2 * n + 7 si semplifica in n^2 * (1 + o (1)). Se il fattore costante è quello che ti infastidisce della solita notazione asintotica O (f (n)), questa raffinatezza è un modo per tenerne traccia e comunque eliminare termini trascurabili.

Answer 2

Il "modo semplice" è quello di simularlo. Prova i tuoi algoritmi con molti valori di n e molti dati diversi, traccia i risultati e poi abbina la curva del grafico a un'equazione.

I risultati potrebbero non essere strettamente corretti e sono validi solo quanto la tua capacità di generare buoni dati di test, ma per la maggior parte dei casi questo funzionerà.

Answer 3

E.g. - dal metodo Regula-Falsi o Newton-Rhapson per la risoluzione di eqns, l'intenzione è di valutare l'esatta complessità di ciascun metodo e poi decidere (mettendo il valore di 'n' o qualunque argomento ci sia) quale metodo è meno complesso.

Non credo sia possibile rispondere a questa domanda in generale per i risolutori non lineari. È possibile un numero esatto di calcoli per iterazione, ma non si saprà mai in generale quante iterazioni occorreranno affinché ogni solver converga. Ci sono altre complicazioni come il bisogno di Jacobian per Newton, che potrebbe rendere ancora più difficile il calcolo della complessità.

Per riassumere, il risolutore non lineare più efficiente dipende sempre dal problema che stai risolvendo. Se la varietà di problemi che stai risolvendo è molto limitata, fare una serie di esperimenti con diversi solutori e misurare il numero di iterazioni e il tempo della CPU probabilmente ti darà più informazioni utili.