Para la selección, en el peor de los casos, la ambigüedad lineal en consideración de $ n $ por la cual $ t (n)= o (1) $ y $ t (n) \ leq cn $

Question

Estaba pasando por el texto Introducción a los algoritmos de Cormen ET. Alabama. donde me encontré con la relación de recurrencia para analizar la complejidad del tiempo del algoritmo seleccionado lineal y sentí que pocas cosas probablemente no coinciden con respecto al rango de $ n $ , el Tamaño de entrada para el cual $ t (n) $ se asume $ o (1) $ y $ CN $ en el método de sustitución.

Los detalles del texto son los siguientes:

---

Ahora podemos desarrollar una recurrencia para el tiempo de ejecución en el peor de los casos $ t (n) $ del algoritmo Seleccione. Pasos 1, 2 y 4 Tomar $ o (n) $ tiempo. (Paso 2 consiste en $ o (n) $ Llamadas de inserción Ordenar en conjuntos de tamaño $ o (1) $ < / span> Paso 3 lleva tiempo $ t (\ lceil n / 5 \ rceil) $ , y el paso 5 lleva tiempo a la mayoría $ T (7N / 10 + 6) $ , suponiendo que T está aumentando monótonamente. Hacemos el supuesto, que parece desmotivado a primera vista, que cualquier entrada de menos de $ 140 $ los elementos requiere $ o (1) $ tiempo; el origen de la constante magia $ 140 $ serán claros en breve. $ ^ \ daga $ podemos obtener la recurrencia

$$ t (n) \ leq \ comienzan {casos} O (1) & \ quad \ text {si $ n <140 $ $ ^ \ ddagger $} \\ T (\ LCEIL N / 5 \ RCEIL) + T (7N / 10 + 6) + O (N) & \ quad \ texto {si $ n \ geq 140 $ $ ^ \ | $} \\ \ End {casos} $$

Demostramos que el tiempo de funcionamiento es lineal por sustitución. Más específicamente, mostraremos que $ t (n) \ leq cn $ para un poco adecuadamente grande constante $ C $ y all $ n> 0 $ . Comenzamos asumiendo que $ t (n) \ leq cn $ para un poco adecuadamente grande constante $ C $ y todos $ n <140 $ $ ^ {\ daga \ daga} $ ; Este supuesto sostiene si $ C $ es lo suficientemente grande. También elegimos una constante a tal que la función descrita por el $ o (n) $ Término anterior (que describe el componente no recursivo del tiempo de ejecución del algoritmo ) está limitado por encima de un para todos $ n> 0 $ . Sustituyendo esta hipótesis inductiva en el lado derecho de la recurrencia

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

$$ \ leq cn / 5 + C + 7CN / 10 + 6c + an $$

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

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

que está en la mayoría de $ cn $ si

$$ - CN / 10 + 7C + A \ Leq 0. \ TAG 1 $$

$$ \ IFF C \ GEQ 10A (N / (N-70)) \ quad \ texto {cuando n> 70} $$

Porque asumimos que $ n \ geq 140 $ $ ^ {\ ddagger \ ddagger} $ Tenemos $ n / (n-70) \ leq 2 $ y así elegir $ C \ GEQ 20A $ Satisfacerá la desigualdad $ (1) $

---

$$ \ dagger \ quad \ text {La declaración aquí cumple con el $ \ ddagger $ en la relación de recurrencia} $$

$$ \ daga \ dagger \ quad \ text {la declaración aquí no cumple con el $ \ | $ en la relación de recurrencia} $$

$$ \ ddagger \ ddagger \ quad \ text {la declaración aquí cumple con los $ \ | $ en la relación de recurrencia} $$

---

No pude entender muy bien esta discrepancia, sin embargo, no incluyó todo el algoritmo (disponible en la sección de CLRS $ 9.3 $ ), pero si se necesitan, por favor diga entonces Lo incluiré también.

Answer 1

Parece que $ \ daga \ daga $ es consistente con $ \ | $ .Solo necesita elegir una constante $ c $ que sea mayor o igual que la constante $ \ gamma $ Oculto en el $ o (1) $ notación en la definición de $ t (n) $ para $ n <140 $ (es decir, la línea marcada con $ \ ddagger $ ).

Luego, para cualquier $ n \ in \ {1, \ dots, 139 \ \ \ \ \ span>, tiene $T (n) \ le \ gamma \ le c \ le cn $ , según lo desee.