Zur Auswahl im Worst-Case-Linearzeit-Zweideutigkeit in Betracht ziehen von $ N $, für die $ T (n)= o (1) $ t (n) \ leq cn $

Question

Ich ging durch den Text Einführung in Algorithmen von Cormmen et. al wo ich auf die Rezidivbeziehung gestoßen bin, um die Zeitkomplexität des linearen Select-Algorithmus zu analysieren, und ich hatte das Gefühl, dass nur wenige Dinge in Bezug auf den Bereich der $ n $ , der Eingabegröße, für die $ T (n) $ übernimmt $ O (1) $ und $ CN $ in der Substitutionsmethode.

Die Details des Textes sind wie folgt:

---

Wir können jetzt ein Wiederauftreten für die Worst-Case-Laufzeit $ t (n) $ von der Algorithmus auswählen. Die Schritte 1, 2 und 4 nehmen $ o (n) $ Zeit. (Schritt 2 besteht aus $ O (n) $ Anrufe der Einfügungssorgart auf Sätzen der Größe $ o (1) $ < / span> Schritt 3 dauert die Zeit $ t (\ lceil n / 5 \ RCEIL) $ , und Schritt 5 dauert in den meisten $ T (7n / 10 + 6) $ , vorausgesetzt, dass t monoton steigt. Wir machen die Annahme, die auferst unmotiviert erscheint, dass jede Eingabe weniger als $ 140 $ Elements erfordert $ O (1) $ Uhrzeit; der Ursprung der Magic Constant $ 140 $ wird in Kürze klar sein. $ ^ \ Dagger $ Wir können daher das Wiederauftreten von

erhalten.

$$ t (n) \ leq \ beginn {hüllen} O (1) & \ Quad \ Text {if $ n <140 $ $ ^ \ ddagger $} \\ T (\ lceil n / 5 \ RCEIL) + t (7n / 10 + 6) + o (n) & \ quad \ text {if $ n \ geq 140 $ $ ^ \ | $} \\ \ ENDE {Hüllen} $$

Wir zeigen, dass die Laufzeit durch Substitution linear ist. Weitere speziell, zeigen wir, dass $ T (n) \ leq cn $ für einige geeignet große Konstante $ C $ und alle $ n> 0 $ . Wir fangen an davon aus, dass $ t (n) \ leq cn $ für einige geeignet große Konstante $ C $ und alle $ n <140 $ $ ^ {\ dolch \ Dolch} $ ;; Diese Annahme gilt, wenn $ C $ groß genug ist. Wir wählen auch eine konstante A so aus, dass die von der SCHNECKUNG "MATH-CONTAINE"> SCHNECKE-SPRECH-FUNKTION (der nicht rekursive Komponente der Laufzeit des Algorithmus beschrieben wird ) ist oben von einem für alle $ n> 0 $ begrenzt. Ersetzen dieser induktiven Hypothese in die rechte Seite des Wiederauftretens

$$ T (n) \ LEQ C \ LCEIL N / 5 \ RCEIL + C (7N / 10 + 6) + A $$

$$ \ LEQ CN / 5 + C + 7CN / 10 + 6C + A $$

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

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

das ist höchstens $ cn $ wenn

$$ - cn / 10 + 7c + An \ leq 0. \ Tag 1 $$

$$ \ IFF C \ GEQ 10A (N / (N-70)) \ Quad \ Text {Wann n> 70} $$

weil wir annehmen, dass $ n \ geq 140 $ $ ^ {\ ddagger \ ddagger} $ Wir haben $ N / (N-70) \ LEQ 2 $ und wählen Sie also $ C \ GEQ 20A $ wird die Ungleichung $ (1) $

---

$$ \ Dagger \ Quad \ Text {Die Anweisung hier entspricht dem $ \ ddagger $ in der Wiederholungsrelation} $$

$$ \ Dagger \ Dagger \ Quad \ Text {Die Anweisung hier entspricht nicht dem $ \ | $ in der Wiederholungsrelation} $$ .

$$ \ DDagger \ DDagger \ Quad \ Text {Die Anweisung hier entspricht dem $ \ | $ in der Wiederholungsrelation} $$

---

Ich konnte diese Diskrepanz nicht ganz verstehen, aber ich habe den gesamten Algorithmus nicht aufgenommen (verfügbar in CLRS-Abschnitt $ 9.3 $ ), aber wenn es notwendig ist, sagen Sie bitte dann Ich werde es auch auch einschließen.

Answer 1

Es scheint, dass $ \ Dagger \ Dagger $ in Einklang mit $ \ | $ .Sie müssen nur einen konstanten $ C $ auswählen, der größer oder gleich dem konstanten $ \ gamma $ versteckt in der $ o (1) $ Notation in der Definition von $ t (n) $ für $ n <140 $ (dh die mit $ \ ddagger $ markierte Zeile).

dann für jeden $ n \ in \ {1, \ dots, 139 \} $ , Sie haben $T (n) \ le \ gamma \ le c \ le cn $ , wie gewünscht.