limite superiore, limite inferiore

Question

Cosa significa dimostrare un limite superiore o inferiore a un algoritmo?

Answer 1

Fornire un limite superiore significa che hai dimostrato che l'algoritmo utilizzerà non più di un limite su una risorsa.

Fornire un limite inferiore significa che hai dimostrato che l'algoritmo utilizzerà non meno di un limite su una risorsa.

" Resource " in questo contesto potrebbe essere tempo, memoria, larghezza di banda o qualcos'altro.

Answer 2

I limiti superiore e inferiore hanno a che fare con il minimo e il massimo "complessità". di un algoritmo (uso questa parola in modo consapevole poiché ha un significato molto specifico nell'analisi della complessità).

Prendi, ad esempio, il nostro vecchio amico, il tipo di bolla. Nel caso ideale in cui tutti i dati sono già ordinati, il tempo impiegato è f (n), una funzione dipendente da n , il numero di elementi nell'elenco. Questo perché devi solo fare un passaggio del set di dati (con zero swap) per assicurarti che il tuo elenco sia ordinato.

In un caso particolarmente negativo in cui i dati sono ordinati in senso contrario all'ordine desiderato, il tempo impiegato diventa f (n ² ). Questo perché ogni passaggio sposta un elemento nella posizione corretta e sono necessari i passaggi n per eseguire tutti gli elementi.

In tal caso, i limiti superiore e inferiore sono diversi, anche se la complessità della grande O rimane invariata.

A parte questo, il tipo di bolla è molto diffamato (di solito per buone ragioni) ma può avere senso in determinate circostanze. In realtà lo uso in un'applicazione in cui la maggior parte dei dati è già ordinata e solo uno o due elementi tendono ad essere aggiunti alla fine dell'elenco. Per l'aggiunta di un elemento e con un ordinamento a bolle inverso, è possibile garantire che il nuovo elenco verrà ordinato in un passaggio. Ciò illustra il concetto del limite inferiore.

In effetti, è possibile effettuare un'ottimizzazione dell'ordinamento a bolle che imposta il limite inferiore su f (1), semplicemente fornendo un dato aggiuntivo che indica se l'elenco è ordinato. Dovresti impostarlo dopo l'ordinamento e cancellarlo quando aggiungi un elemento alla fine.

Answer 3

Qualunque sia il limite (superiore o inferiore), parliamo sempre dell'input del caso peggiore che possiamo considerare. Ad esempio, nell'ordinamento, assumiamo che il caso peggiore sia un elenco di input non ordinato.

La mia comprensione è che i problemi hanno un limite inferiore. Ad esempio, diciamo che il limite inferiore dell'ordinamento basato sul confronto è \ Omega (n log n); non facciamo ipotesi su quale particolare algoritmo di ordinamento basato su confronto algoritmo utilizziamo. Qualunque sia l'algoritmo (unisci ordinamento, ordinamento rapido, ecc.), Non possiamo fare meglio di questo limite di \ Omega (n log n). I limiti inferiori ci dicono intuitivamente quanto sia difficile un particolare problema .

Quando parliamo di un algoritmo specifico , allora parliamo di limiti superiori. Ad esempio, diciamo che il limite superiore dell'ordinamento a bolle è O (n ^ 2) e il limite superiore dell'ordinamento a fusione è O (n log n). I limiti superiori, intuitivamente, ci dicono quanto è bravo un particolare algoritmo a risolvere il problema.