Differenza tra complessità e garanzia di prestazioni

"garanzia di prestazione" non è un termine tipicamente utilizzato nell'analisi degli algoritmi.

La complessità del tempo è misurata in termini di qualunque cosa tu voglia. Sei incappato in uno sporco segreto di CS: la notazione Big-O è spesso usata piuttosto sciatamente senza specificare che esattamente aumenta con la dimensione dell'input in quel modo. Generalmente è il numero di alcune operazioni primitive che si presume dominino gli altri nell'implementazione e si presume che prendano un tempo costante. Entrambe queste ipotesi spesso non sono universalmente vere. Ad esempio, per gli algoritmi di ordinamento la complessità del tempo è solitamente basata sul numero di confronti. Ma il confronto dei numeri non è in realtà un'operazione a tempo costante stesso se i numeri diventano veramente grandi

A volte c'è una differenza tra la grande O del tempo medio rispetto alla grande O del caso peggiore. Ad esempio, quicksort fa una media di N * Log (N), ma in teoria si può ottenere sfortunati sulla partizione ogni volta e finire con N ** 2.

Nel caso della selezione sort, la media e la peggiore delle ipotesi sono N ** 2, ma è comunque possibile che la "garanzia di prestazione" si riferisca alle prestazioni peggiori.

La complessità dell'algoritmo è in termini di qualsiasi operazione abbia la più alta complessità. Quindi, ad esempio, se un ordinamento richiede confronti O (n ^ 2) e scambi O (n log n), l'algoritmo complessivo è O (n ^ 2).

La logica di ciò è semplice: la notazione O grande è ciò che accade quando "n" va all'infinito. Dato che 'n' va all'infinito, qualunque operazione abbia l'ordine peggiore finirà per dominare il tempo di esecuzione.

Quindi un algoritmo richiede O (n ^ 2) di qualsiasi sotto-operazione al suo interno, la sua complessità complessiva non può essere inferiore a O (n ^ 2).

I'm a bit confused with the performance guarantee and complexity of selection sort.

I checked through internet and the complexity of selection sort is O(n^2). This O(n^2) is in terms of time complexity, am i right?

destro. È il numero totale di operazioni a tempo costante a fattore costante * dipendente dalla dimensione di input (questa è ancora semplificata) .

So how about performance guarantee? Is the performance guarantee in my case measured in terms of swapping or in time complexity as well? If the performance guarantee is in terms of swapping, so best case of swapping is zero swaps (the array is already sorted) and the worst case of swapping is n-1 step? The performance guarantee is then equal to (n-1)/0=undefined, am I correct?

Non so cosa consideri una garanzia di prestazioni, ma la notazione O grande ci garantisce che un algoritmo O (n ^ 2) non verrà eseguito più lentamente di quanto indicato da questo limite. Una garanzia di esecuzione non dovrebbe essere data solo in termini di scambio, devi guardare all'intero algoritmo. Ma puoi chiedere esplicitamente una garanzia di performance per lo swapping in uno specifico algoritmo, se questo ti interessa (per qualsiasi motivo). Per la selezione sort questo è Theta (n) poiché si scambia sempre n-1 volte con l'ordinamento di selezione classico, l'algoritmo somtimes scambia un oggetto con se stesso (che non è ancora un'operazione a tempo zero, perché dubito che il compilatore possa ottimizzarlo in ogni caso).

Please correct me if im wrong...or is the performance guarantee is in terms of running time? Then performance guarantee will be (n-1)/(n-1) = 1?

A mio parere, la garanzia di prestazione è una misura per il grado di soluzioni di algoritmi euristici. È sufficiente confrontare la soluzione approssimata con la soluzione ottimale nota e calcolare quanto è vicina. Però non ne sono completamente sicuro.

Se dovessi applicare questo tipo di pensiero agli algoritmi di ordinamento che si scambiano, allora direi che il caso migliore per lo swapping è sempre O (n). E poichè la selezione sort scambia Theta (n) volte la "garanzia di prestazioni per lo scambio" è probabilmente 1. Quando voglio garantire qualcosa, di solito sono preoccupato per i peggiori tipi di comportamento. Quindi nel caso peggiore una soluzione ottimale scambia n-1 volte e così fa la selezione. Sarebbe inutile prendere il miglior caso di una soluzione ottimale.