Per la selezione nell'ambiguità del tempo lineare del caso peggiore in considerazione di $ N $ per quale $ t (n)= o (1) $ e $ t (n) \ leq cn $

Question

Stavo attraversando l'introduzione del testo agli algoritmi di Cormen et. al. dove mi sono imbattuto nella relazione di ricorrenza per analizzare la complessità del tempo dell'algoritmo di selezione lineare e ho sentito che poche cose probabilmente non corrispondono alla gamma di $ n $ , il Dimensioni di ingresso per quale $ t (n) $ si assume $ o (1) $ e $ cn $ nel metodo di sostituzione.

I dettagli del testo sono i seguenti:

---

.

Possiamo ora sviluppare una recidiva per il tempo di esecuzione peggiore $ t (n) $ dell'algoritmo Seleziona. Passi 1, 2 e 4 Take $ o (n) $ tempo. (Il passaggio 2 è composto da $ o (n) $ chiamate di insertion ordinamento su serie di dimensioni $ o (1) $ < / span> Passaggio 3 richiede tempo $ t (\ lceil n / 5 \ rceil) $ e il passaggio 5 richiede tempo al massimo $ T (7N / 10 + 6) $ , supponendo che T sia monotonicamente aumentando. Facciamo l'ipotesi, che sembra immotivata al primo posto, che qualsiasi input di meno della classe $ 140 $ elementi richiede $ o (1) $ tempo; l'origine della costante magica $ 140 $ sarà chiaro a breve. $ ^ \ pugnale $ possiamo quindi ottenere la ricorrenza

$$ t (n) \ leq \ begin {casi} O (1) & \ quad \ testo {se $ n <140 $ $ ^ \ ddagger $} \\ T (\ lceil n / 5 \ rceil) + t (7n / 10 + 6) + o (n) & \ quad \ text {se $ n \ geq 140 $ $ ^ \ | $} \\ \ end {casi} $$

Mostriamo che il tempo di esecuzione è lineare per sostituzione. Più specificamente, mostreremo che $ t (n) \ leq cn $ per un po 'opportunamente grande costante $ c $ E Tutto $ N> 0 $ . Iniziamo assumendo che $ t (n) \ leq cn $ per un po 'opportunamente grande costante $ c $ e Tutto $ n <140 $ $ ^ {\ pugnale \ pugnale} $ ; Questa assunzione tiene se $ c $ è abbastanza grande. Scegliamo anche una costante una tale che la funzione descritta dalla $ o (n) $ termine sopra (che descrive il componente non ricorsivo del tempo di esecuzione dell'algoritmo ) è limitato sopra da un $ n> 0 $ . Sostituendo questa ipotesi induttiva nel lato destro della recidiva

$$ t (n) \ leq c \ lceil n / 5 \ rceil + c (7n / 10 + 6) + un $$

$$ \ leq cn / 5 + c + 7cn / 10 + 6c + un $$

$$= 9cn / 10 + 7c + un $$

$$= cn + (- cn / 10 + 7c + an). $$

che è al massimo $ cn $ se

$$ - cn / 10 + 7c + an \ leq 0. \ tag 1 $$

$$ \ IFF C \ GeQ 10A (N / (N-70)) \ quad \ testo {quando n> 70} $$

Poiché assumiamo che $ n \ geq 140 $ $ ^ {\ ddagger \ ddagger} $ Abbiamo $ N / (N-70) \ Leq 2 $ e quindi scegliendo $ c \ geq 20A $ soddisferà la disuguaglianza $ (1) $

---

.

$$ \ DAGGER \ quad \ text {La dichiarazione qui è conforme al $ \ ddagger $ nella relazione di ricorrenza} $$

$$ \ DAGGER \ DAGGER \ quad \ text {la dichiarazione qui non è conforme ai $ \ | $ nella relazione di recidiva} $$ $$ \ ddagger \ ddagger \ quad \ text {la dichiarazione qui è conforme ai $ \ | $ nella relazione di recidiva} $$

---

.

Non ho potuto capire questa discrepanza, tuttavia non ho incluso l'intero algoritmo (disponibile nella sezione CLRS $ 9.3 $ ) Ma se è necessario, è necessario, per favore, allora Io includerò anche lui.

Answer 1

Sembra che $ \ dagger \ pugnale $ è coerente con $ \ | $ .Hai solo bisogno di scegliere una costante $ c $ che è più grande o uguale alla costante $ \ gamma $ Nascosto nella $ o (1) $ notazione nella definizione di $ t (n) $ per $ N <140 $ (cioè la linea contrassegnata con $ \ ddagger $ ).

quindi, per qualsiasi classe $ n \ in \ {1, \ dots, 139 \} $ , hai $T (n) \ le \ gamma \ le c \ le cn $ , come desiderato.