Pour la sélection dans l'ambiguïté de temps linéaire pire des cas en contrepartie de N $ N $ pour lesquels $ T (n)= O (1) $ et $ T (n) \ Leq cn $

Question

Je traversais le texte Introduction aux algorithmes de Cormen et. Al. où je suis tombé sur la relation de récurrence pour analyser la complexité temporelle de l'algorithme de sélection linéaire et j'ai ressenti cette inadéquation probablement par rapport à la plage de $ n $ , le Taille d'entrée pour laquelle $ t (n) $ est suppose $ o (1) $ et $ CN $ dans la méthode de substitution.

Les détails du texte sont les suivants:

---

Nous pouvons maintenant développer une récurrence pour le temps de fonctionnement du pire des cas $ t (n) $ de l'algorithme sélectionnée. Les étapes 1, 2 et 4 prennent $ O (n) $ heure. (Étape 2 consiste en $ O (N) $ Appels d'insertion Trier sur des ensembles de taille $ O (1) $ < / SPAN> L'étape 3 prend du temps $ t (\ lceil n / 5 \ rcil) $ et l'étape 5 prend du temps au plus $ T (7n / 10 + 6) $ , en supposant que t augmente monotoniquement. Nous faisons l'hypothèse, qui semble non démotivée à la première partie, que toute entrée de moins que 140 $ éléments nécessite $ o (1) $ temps; l'origine de la constante magique 140 $ sera clair sous peu. $ ^ \ Dagger $ Nous pouvons donc obtenir la récurrence

$$ t (n) \ Leq \ commence {cas} O (1) & \ quad \ texte {si $ n <140 $ $ ^ \ ddagger $} \\ T (\ lceil n / 5 \ rcil) + t (7n / 10 + 6) + O (n) & \ quad \ texte {si $ n \ geq 140 $ $ ^ \ | \ \\ \ fin {cas} $$

Nous montrons que le temps de fonctionnement est linéaire par substitution. Plus spécifiquement, nous montrerons que $ T (N) \ LEQ CN $ Pour une constante de manière appropriée $ C $ et tout $ n> 0 $ . Nous commençons par supposer que $ t (n) \ leq $ cn $ pour une constante de constante de manière appropriée $ C $ et tout $ n <140 $ $ ^ {\ Dagger \ Dagger} $ ; Cette hypothèse détient si $ C $ est suffisamment grand. Nous choisissons également une constante de telle de telle que la fonction décrite par la $ O (n) $ terme ci-dessus (qui décrit le composant non récursif de la durée de fonctionnement de l'algorithme ) est délimité ci-dessus par un N> 0 $ . Substituant cette hypothèse inductive dans le côté droit de la récurrence

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

$$ \ Leq cn / 5 + c + 7cn / 10 + 6c + a $$

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

$$= CN + (- CN / 10 + 7C + a). $$

qui est au plus $ cn $ si

$$ - CN / 10 + 7C + AN \ LEQ 0. \ TAG 1 $$

$$ \ iff c \ geq 10a (n / (n-70)) \ quad \ texte {quand n> 70} $$

Parce que nous supposons que $ n \ geq 140 $ $ ^ {\ ddagger \ ddagger} $ Nous avons $ n / (n-70) \ leq 2 $ et donc choisir $ c \ geq 20a $ satisfera l'inégalité $ (1) $

---

$$ \ Dagger \ quad \ Text {L'instruction ici est conforme à la $ \ ddagger $ dans la relation de récurrence} $$

$$ \ Dagger \ Dagger \ quad \ Text {L'instruction ici ne respecte pas le $ \ | $ dans la relation de récurrence} $$

$$ \ ddagger \ ddagger \ quad \ text {la déclaration ici est conforme à la relation $ \ | $ dans la relation de récurrence} $$

---

Je ne pouvais pas bien comprendre cette divergence, mais je n'ai pas inclus l'algorithme entier (disponible dans la section CLRS 9,3 $ ) mais si elle est nécessaire, veuillez dire alors J'y comprendra aussi.

Answer 1

Il semble que $ \ dague \ dague $ $ est cohérent avec $ \ | $ .Vous avez juste besoin de choisir une constante $ C $ plus gros ou égale à la constante $ \ gamma $ caché dans la $ o (1) $ notation dans la définition de $ t (n) $ pour $ N <140 $ (c'est-à-dire la ligne marquée de $ \ ddagger $ ).

Ensuite, pour tout $ n \ in \ \ \ \ \ \ \ \ \ points, 139 \} $ , vous avez $T (n) \ le \ gamma \ le c \ le cn $ , comme vous le souhaitez.