Da qui , so che è un algoritmo che ...
...is said to be solvable in polynomial time if the number of steps required to complete the algorithm for a given input is O(n^k) for some nonnegative integer k, where n is the complexity of the input.
Alcuni di voi possono offrire esempi di strutture dati comuni per spiegare il tempo polinomiale? L'ho cercato ma le informazioni disponibili sono scarse.
Che cosa significa "tempo polinomiale" significa che se si calcola una formula che descrive quanto tempo ci vorrà per completare l'algoritmo su un set di dati con elementi n , il termine di grandezza maggiore nella formula sarà sotto forma di n^x .
Ecco alcuni esempi di classi di runtime:
O(1) : il runtime non aumenta quando il set di dati aumenta di dimensioni. Esempio: accesso alla matrice. Il recupero di un elemento arbitrario in una matrice avviene altrettanto velocemente, indipendentemente dalla grandezza della matrice. (In teoria, in pratica, se l'array trabocca la memoria fisica e deve essere impaginato sul disco, questo può cambiare, ma la teoria della complessità non si occupa di dettagli del genere.) O(log n) : il runtime aumenta come il log della dimensione del set di dati, un numero che cresce più lentamente del set di dati stesso. Esempio: una ricerca binaria attraverso un array o albero bilanciato. Poiché ogni controllo taglia a metà il restante numero di elementi considerati, saranno necessari 2 controlli per cercare tra 3 elementi, 3 controlli per cercare 7 elementi, 4 controlli per cercare 15 elementi ... e così via. Con 32 assegni, puoi cercare oltre 4 miliardi di elementi con una ricerca binaria. O(n) : il runtime aumenta ad una velocità direttamente proporzionale alla dimensione del set di dati. Esempio: una ricerca lineare attraverso una matrice. Saranno necessari 10 controlli per iterare oltre 10 elementi o 4 miliardi di assegni per iterare oltre 4 miliardi di elementi. O(n log n) : il tempo di esecuzione aumenta più rapidamente della dimensione del set di dati, ad una proporzione proporzionale alla dimensione del log della dimensione. Esempio: algoritmi di ordinamento divide e conquista come Quicksort e Mergesort, in cui i valori da cercare vengono divisi in gruppi sempre più piccoli, proprio come nella ricerca binaria di cui sopra. O(n^2) : questo è tempo polinomiale , in cui il tempo di esecuzione aumenta proporzionalmente al quadrato del set di dati. Qualsiasi classe in cui il tempo di esecuzione aumenta in base a n^x , per qualsiasi valore di x , è considerata tempo polinomiale. Esempio: Algoritmi di ordinamento lineare in cui i valori da cercare non vengono divisi in gruppi più piccoli, ad esempio Bubble Sort e Insertion Sort. Per trovare dove ogni elemento appartiene, l'algoritmo deve cercare nell'intero array, quindi il runtime generale è n (il numero di elementi) volte n (il numero di elementi da cercare per ogni elemento). Il tempo di esecuzione effettivo sarà più basso, poiché non dovrai cercare l'intero array per ogni singolo elemento, ma la teoria della complessità riguarda le generalizzazioni, e in pratica la quantità di ricerche che hai finito per fare non essere abbastanza per compensare la maggiore complessità derivante dall'aumento delle dimensioni. Il tempo polinomiale è importante, perché è considerato la classe più alta che è ancora "veloce" dalla teoria della complessità. Esistono classi di complessità più elevate in cui la complessità diventa molto ingestibile molto rapidamente e comprendono alcune delle domande più interessanti in informatica e teoria dell'informazione.
Ad esempio, il problema del venditore ambulante , che può determinare l'ordine più efficiente in cui eseguire una serie di attività , richiede tempo esponenziale per risolvere: O(2^n) . Questo è molto diverso da O(n^2) ; 32 ^ 2 = 1024, ma 2 ^ 32 è oltre 4 miliardi, il che spiega perché la complessità degli algoritmi NP ( Tempo polinomiale non deterministico , o algoritmi non noti per avere una soluzione che funziona in polinomio -time o meglio) esplode una volta superati insiemi di dati banali!
Uno dei modi più comuni per esprimere il tempo polinomiale, O (n k ), è cicli annidati dove n è usato come input per calcolare le iterazioni massime di ogni ciclo e k è il livello dei cicli nidificati.
Ad esempio, questo ciclo è O (n 2 ) perché è un ciclo doppio nidificato dove n è il numero di iterazioni:
int n = ...;
int x = 0;
for (int i = 0; i < n; ++i) {
for (int i = j; j < n; ++j) {
++x;
}
}
Se aggiungi un terzo ciclo, sarebbe O (n 3 ).
Considera di trovare l'elemento più piccolo in una raccolta non ordinata. Mentre è possibile utilizzare un array o un elenco collegato per contenere i dati, la complessità temporale sarà O (n) poiché ogni elemento deve essere esaminato in quanto potrebbe essere il più piccolo che non sia ancora stato conosciuto.
Un classico esempio di algoritmo O (n³) è moltiplicazione di matrice . La moltiplicazione di due matrici 10x10 richiede una moltiplicazione di 10 ^ 3.
In pratica, tuttavia, algoritmi moderni come l'algoritmo di Coppersmith-Winograd possono portare l'ordine a circa 2.37.
Leggi altre domande sui tag performance runtime data-structures algorithms complexity