$ \ Phi_1= 1 $ ou $ \ phi_1= 2 $ para o dinâmico $ \ texto {table-insert} $, onde $ \ phi_i $ é a função potencial após $ i $ th operação, como por clrs

Question

O seguinte vem da seção Tabelas dinâmicas , Introdução aos algoritmos por Cormen. ET. al.

---

.

No seguinte pseudocódigo, assumimos que $ t $ é um objeto representando a tabela. O campo $ Tabela [T] $ contém um ponteiro para o bloco de armazenamento representando a tabela. O campo $ num [T] $ contém o número de itens na tabela e o campo $ tamanho [t] $ é o número total de slots na tabela. Inicialmente, a tabela está vazia: $ num [t]= tamanho [t]= 0 $ .

.

$ \ text {table-insert (t, x)} $

$ 1 \ quad \ text {se $ tamanho [t]= 0 $} $

$ 2 \ Quad \ Quad \ Text {Em seguida Aloque $ Tabela [T] $ com $ 1 $ Slot} $

$ 3 \ Quad \ Quad \ Quad [t] \ \ \ \ $

$ 4 \ quad \ text {if} num [t]= tamanho [t] $

$ 5 \ Quad \ Quad \ Text {ENCLOCA $ NEW NEW {\ text {-}} Tabela $ com $ 2 \ Cdot Tamanho [T] $ slots} $

$ 6 \ Quad \ Quad \ Quad \ Text {Insira todos os itens na tabela $ [t] $ em $ NOVO {\ text {-}} tabela $} $

$ 7 \ Quad \ Quad \ Quad \ Text {Free $ Tabela [T] $} $

$ 8 \ Quad \ Quad \ Quad Tabela [T] \ Landdrow novo {\ text {-}} tabela $

$ 9 \ Quad \ Quad \ Quad Size [T] \ Landdrow 2 \ Cdot Tamanho [T] $

$ 10 \ quad \ text {inserir $ x $ para $ tabela [t] $} $

$ 11 \ Quad Num [T] \ Landdrow num [t] + 1 $

Para a análise amortizada para a seqüência de uma sequência de $ n $ $ \ texto {table-insert} $ A função potencial que escolhem é a seguinte,

.

$$ \ phi (t)= 2.num [t] -size [t] $$

analisar o custo amortizado da $ i $ th $ \ text {table-insert} $ Operação, deixamos $ num_i $ denotam o número de itens armazenados na tabela após a $ i $ th operação, $ size_i $ denotam o tamanho total da tabela após a $ i $ th operação, e $ \ phi_i $ denotam o potencial após a $ i $ th operação.

Inicialmente, temos $ num_0= 0, tamanho_0= 0 $ , e $ \ phi_0= 0 $ .

Se o $ i $ a operação de inserção de tabela não aciona uma expansão, então temos $ size_i= size_ {II} $ e $ num_i= num_ {i-1} +1 $ , o custo amortizado da operação é $ \ widehat {c_i} $ é o custo amortizado e $ c_i $ é o custo total.

.

$$ \ widehat {c_i}= c_i + \ phi_i- \ pHI_ {I-1}= 3 \ text {(detalhes não mostrado)} $$ < / p >.

Se o $ i $ th trigger uma expansão, então temos $ size_i= 2. size_ {I-1} $ e $ size_ {I-1}= num_ {I-1}= num_i -1 $ , então novamente, < / p >.

.

$$ \ widehat {c_i}= c_i + \ phi_i- \ pHI_ {I-1}= 3 \ text {(detalhes não mostrado)} $$ < / p >.

---

.

agora o problema é que eles não fazem cálculos para $ \ widehat {c_1} $ , a situação para a primeira inserção de um elemento na tabela (linha 1,2,3,10,11 de código só é executado).

Nessa situação, o custo $ c_1= 1 $ , $ \ phi_0= 0 $ e $ num_1= size_1= 1 \ implica \ phi_1= 2.1-1= 1 $

Vemos que $ \ phi_1= 1 \ tag 1 $

Então, $$ \ widehat {c_1}= c_1 + \ phi_1- \ pHI_0= 2 $$

Mas o texto diz que o custo amortizado é $ 3 $ (eu sinto que eles deveriam ter dito que o custo amortizado é no máximo $ 3 $ , do que posso entender)

Além disso, no enredo abaixo,

O texto representa graficamente a $ \ phi_1= 2 $ que tipo de contradizes

er "> $ (1) $ , mas conforme o gráfico se assumirmos $ \ phi_1= 2 $ então $ \ widehat {c_i}= 3, \ forall i $

Eu não recebo onde estou fazendo o equivocado.

Answer 1

Você pegou uma instância do infame erro off-by-one nesse livro popular cujo nome não deveremos mencionar novamente.

Para repetir, está correto que "o custo $ c_1= 1 $ , $ \ phi_0= 0 $ < / span> "", " $ num_1= size_1= 1 $ $ \ implica $ $ \ phi_1= 2 \ cdot1-1= 1 $ " e " $ \ hat {c_1}= $ $ c_1 + \ phi_1- \ phi_0 $ $= 2 $ ". É incorreto afirmar que $ \ widehat c_i= 3 $ para todos $ i $ .

a primeira $ \ text {t} {\ text {capaz}} \ pequeno \ text {-} \ scriptsize \ text {nsert} $ A operação é realmente muito especial. Não é considerado uma expansão, um evento que é definido como "em que linhas 5-9 são executados". No entanto, não mantém $ size_i= size_ {I-1} $ . Então nem computação para $ \ widehat {c_i} $ no livro didático é apto para $ \ widehat {c_1} $ .

Esse erro é confuso, dado que tendemos a confiar totalmente um livro didático exemplar, onde tantas atenção foram pagas a detalhes e correção.

Por outro lado, esse erro não é muito significativo, uma vez que, como você observou, ainda é detido que "o custo amortizado é no máximo 3".

A propósito, se você tiver uma olhada mais de perto na figura no final da pergunta, ela mostra o potencial no final da primeira $ \ text {t} {t} {t} {t} {t} \ scriptsize \ texto {capaz}} \ pequeno \ text {-i} \ scriptsize \ text {nsert} $ operação, $ \ phi_1= 1 $ , o valor correto.