Hilfe beim Verstehen der "vernünftigen" Kodierung von Eingängen

Question

Ich lese, dass eine angemessene Kodierung von Eingängen eine, bei der die Länge der Kodierung nicht mehr als ein Polynom der "natürlichen Darstellung" des Eingangs ist.Zum Beispiel sind Binärkodierungen angemessen, aber ungehundige Kodierungen sind nicht.

aber sagen Sie, dass der Eingang ein Diagramm ist, und seine natürliche Darstellung ist eine Scheitelpunkt- und Kantenliste.Angenommen, die Grafik hat $ K $ Ecken.Wenn ich Unary zu codieren, wäre die Gesamtlänge der Eingabe der Vertex-Liste $ O (K ^ 2) $ , dh $= | 1 ^ 1 | + | 1 ^ 2 | + | 1 ^ 3 | + ... + | 1 ^ k | $ .Ist dies nicht einheitliches Kodierungen in Bezug auf die Anzahl der Scheitelpunkte des Diagramms (der $ k $ ) ist?

Was vermisse ich hier?

Answer 1

Unary-Kodierung für Werte 0 <= k <= n nimmt o (n) Platz.Unary Codierung einer N-Bit-Nummer dauert $ \ theta (2 ^ n) $ raum.Sehen Sie den Unterschied?