Para seleção em pior caso a ambiguidade de tempo linear em consideração de $ n $ para qual $ t (n)= o (1) $ e $ t (n) \ leq cn $

Question

Eu estava passando pela introdução de texto para algoritmos por Cormen ET. al. onde me deparei com a relação de recorrência para analisar a complexidade de tempo do algoritmo selecionado linear e senti que poucas coisas provavelmente incompatibilidade em relação ao alcance da $ n $ , o Tamanho da entrada para o qual $ t (n) $ é assumido $ o (1) $ e $ cn $ no método de substituição.

Os detalhes do texto são os seguintes:

---

.

Agora podemos desenvolver uma recorrência para o tempo de execução do pior caso $ T (n) $ do algoritmo Selecionar. Etapas 1, 2 e 4 Take $ O (n) $ tempo. (Passo 2 consiste em $ o (n) $ chamadas de inserção classificar em conjuntos de tamanho $ O (1) $ < / span> etapa 3 leva tempo $ t (\ lceil N / 5 \ rceil) $ , e a etapa 5 leva tempo no máximo $ T (7n / 10 + 6) $ , assumindo que T é monotonicamente aumentando. Nós fazemos a suposição, que parece desmotivada no primeiro a ser inferior a $ 140 $ elementos requer $ O (1) $ tempo; a origem da constante mágica $ 140 $ será claro em breve. $ ^ \ adaga $ podemos, portanto, obter a recorrência

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

Mostramos que o tempo de execução é linear por substituição. Mais especificamente, vamos mostrar que $ t (n) \ leq cn $ para alguma constante adequadamente grande $ c $ e toda $ n> 0 $ . Começamos assumindo que $ t (n) \ leq cn $ para alguma constante adequadamente grande $ c $ e toda $ n <140 $ $ ^ {\ endaga \ Dagger} $ ; Esta suposição mantém se $ c $ é grande o suficiente. Também escolhemos uma constante A tal que a função descrita pela $ O (n) $ termo acima (que descreve o componente não recursivo do tempo de execução do algoritmo ) é limitado acima por um para todos $ n> 0 $ . Substituindo esta hipótese indutiva no lado direito da recorrência

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

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

$$= 9CN / 10 + 7C + A $$

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

Qual é no máximo $ cn $ se

$$ - CN / 10 + 7C + A \ LEQ 0. \ Tag 1 $$

$$ \ iff c \ geq 10a (n / 70)) \ quad \ text {quando n> 70} $$

Porque assumimos que $ n \ GEQ 140 $ $ ^ {\ ddger \ ddagger} $ Nós temos $ n / (N-70) \ LEQ 2 $ e assim escolher $ c \ geq 20a $ satisfará a desigualdade $ (1) $

---

.

$$ \ Dagger \ Quad \ Text {A declaração aqui está em conformidade com o $ \ DDAGGAGE $ na relação de recorrência} $$

$$ \ Dagger \ Dagga \ Quad \ Text {A instrução aqui não está em conformidade com o $ \ | $ na relação de recorrência} $$

$$ \ DDagger \ DDagger \ Quad \ Text {A declaração aqui cumpra com a relação $ \ | $ na relação de recorrência} $$

---

.

Eu não consegui entender essa discrepância, no entanto, eu não incluí todo o algoritmo (disponível na seção CLRS $ 9.3 $ ) mas se for necessário, por favor diga Eu também incluirei.

Answer 1

Parece que $ \ Dagger \ Dagger $ é consistente com $ \ | $ .Você só precisa escolher uma constante $ c $ que é maior que ou igual à constante $ \ gamma $ Escondido na $ O (1) $ Notação na definição de $ t (n) $ para $ n <140 $ (ou seja, a linha marcada com $ \ ddagger $ ).

Então, para qualquer $ n \ in \ {1, \ DOTS, 139 \} $ , você tem $T (n) \ le \ gamma \ le c \ le cn $ , conforme desejado.