Ajude a entender a codificação "razoável" de insumos

Question

Eu li que uma codificação razoável de insumos é aquela em que a duração da codificação não é mais do que um polinômio da "representação natural" da entrada.Por exemplo, codificações binárias são razoáveis, mas as codificações unérias não são.

Mas diga que a entrada é um gráfico, e sua representação natural é uma lista de vértice e borda.Suponha que o gráfico tenha $ k $ vértices.Se eu usar unário para codificar, o comprimento total da entrada referente à lista de vértice seria $ o (k ^ 2) $ , ou seja, $= | 1 ^ 1 | + | 1 ^ 2 | + | 1 ^ 3 | + ... + | 1 ^ k | $ .Não é essa codificação unéria ainda um polinômio em relação ao número de vértices do gráfico (que é $ k $ )?

)?

O que estou perdendo aqui?

Answer 1

Codificação unmarária para valores 0 <= k <= n leva o (n) espaço.Codificação unéria de um número de N-bit leva $ \ theta (2 ^ n) $ espaço.Veja a diferença?