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

9

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)={Θ(1)if n=1,T(n1)+Θ(n)if n>1.

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(n1)+Θ(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?

Aseem Bansal
fonte
11
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.)Θ
Raphael

Respostas:

6

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.

{1, n=1T(n1) + Θ(log n), otherwise}

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
2
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