Recorrência para classificação de inserção recursiva

Eu tentei esse problema no CLRS (página 39, 2.3-4)

Podemos expressar a classificação por inserção como um procedimento recursivo da seguinte maneira. Para classificar A[1... n], classificamos recursivamente A[1... n-1]e depois inserimos A[n]na matriz classificada A[1... n-1]. Escreva uma recorrência para o tempo de execução desta versão recursiva da classificação por inserção.

A recorrência que formei foi

T (n) = {\begin{cases} Θ (1) & if n = 1, \\ T (n - 1) + Θ (n) & if n > 1. \end{cases}

$T(n) = \begin{cases}\Theta(1) & \textrm{if } n = 1,\\ T(n-1) + \Theta(n) & \textrm{if } n > 1. \end{cases}$

Meu raciocínio

No caso base de a lista é classificada para que não haja trabalho, portanto, tempo constante. $n = 1$
Para todos os outros casos, o tempo depende da classificação da sequência A[1...n-1]e depois da inserção nessa sequência. Portanto, deve ser sua soma, isto é, . $T(n-1) + \Theta(n)$

Eu queria saber se a relação de recorrência está correta. Se não, quais são os erros e como formular corretamente uma relação de recorrência?

algorithm-analysis runtime-analysis recurrence-relation sorting Aseem Bansal
fonte

Você pode estar interessado em nossas perguntas de referência . Em particular, a noção de "tempo de execução" é nebulosa, a recorrência com -terms não é a maneira mais agradável de colocar as coisas e vários tipos de resolução de recorrências foram discutidos. Observe que as perguntas "sim-não" geralmente são indesejadas aqui. (Faço notar que a questão é antiga, deixando o recado para referência.)

Θ

$\Theta$

Raphael

Respostas:

De acordo com a descrição que você forneceu, a recorrência está correta.
você pode pensar que deveria ser
T (n) = porque você pode encontrar o local de inserção usando a Pesquisa binária, no entanto, para inserir o elemento, você precisará afastar todos os elementos no pior caso.

{\begin{matrix} 1 & , n = 1 \\ T (n - 1) + Θ (l o g n) & , o t h e r w i s e \end{matrix}}

$\begin{Bmatrix} 1 & ,\ n=1\\ T(n-1)\ +\ \Theta(log\ n) & ,\ otherwise \end{Bmatrix}$

hcf
fonte

Pesquisando linearmente leva O(n)e fazendo pesquisa binária é O(log n). Mas não é o pior dos casos o movimento de todos os elementos que devem levar O(n), tornando a complexidade geral O(n)? Então, por que o termo in n != 1é em O(log n)vez de ser O(n)?

Aseem Bansal

Você está certo, foi exatamente o que eu disse. A fórmula acima está errado exactamente porque o movimento dos elementos leva O (n)

HCF

Eu deveria estar lendo com mais cuidado. Obrigado por responder.

Aseem Bansal