Aider à comprendre le codage «raisonnable» des intrants

Question

J'ai lu qu'un codage raisonnable des entrées est l'un des endroits où la longueur du codage n'est plus qu'un polynôme de la «représentation naturelle» de l'entrée.Par exemple, les codages binaires sont raisonnables, mais les codages uniques ne sont pas.

Mais disons que l'entrée est un graphique et sa représentation naturelle est une liste de sommets et de bords.Supposons que le graphique ait $ k $ sommets.Si j'utilise le cas pour coder, la longueur totale de l'entrée faisant référence à la liste de sommet serait $ o (k ^ 2) $ , c'est-à-dire $= | 1 ^ 1 | + | 1 ^ 2 | + | 1 ^ 3 | + ... + | + | 1 ^ k | $ .N'est-ce pas un codage unaire toujours un polynôme en ce qui concerne le nombre de sommets du graphique (qui est $ k $ )?

Qu'est-ce que je manque ici?

Answer 1

codage unaire pour les valeurs 0 <= k <= N prend o (n) espace.Le codage unaire d'un numéro N-bit prend $ \ theta (2 ^ n) $ espace.Voir la différence?