Algorithmus-Zeitanalyse „Eingabegröße“ vs. „Eingabeelemente“

Ich bin immer noch ein bisschen verwirrt mit den Begriffen "Eingabelänge" und "Eingabegröße", wenn ich die asymptomatische Obergrenze für einen Algorithmus analysiere und beschreibe

Die Länge der Eingabe für den Algorithmus hängt anscheinend stark von der Art der Daten und dem Algorithmus ab, über den Sie sprechen.

Einige Autoren beziehen sich auf die Länge der Eingabe auf die Größe der Zeichen, die für die Darstellung der Eingabe erforderlich sind. Wenn also "abcde" als Eingabesatz in einem Algorithmus verwendet wird, hat dies eine "Eingabelänge" von 6 Zeichen.

Wenn wir anstelle von Zeichen eine Zahl haben (zum Beispiel ganze Zahlen), wird manchmal die Binärdarstellung anstelle von Zeichen verwendet, sodass die "Eingabelänge" als berechnet wird (wobei L die maximale Zahl in der Eingabemenge ist). .$N*log(L)$

Es gibt andere Probleme , dass selbst wenn der Eingangssatz Zahlen sind, sie die „Eingabelänge“ als „Entscheidungsvariablen“ beschreiben, so dass für einen Eingangssatz der Länge N mit Zahlen im Bereich die Eingabelänge ist nur N ( Teilmenge Summe zum Beispiel), oder noch komplizierter die Anzahl der binären Stellenwerte, die es braucht, um das Problem zu erklären (was ich glaube, ist genau das gleiche wie N ∗ l o g ( L ) )$0-2^{32}$$N*log(L)$

So:

• Kommt es auf den Algorithmus an?
• Was bedeutet und wann verwendet man die Eingabe Länge "Version"
• Gibt es eine Regel, nach der ich mich für eine entscheiden kann?

Im formalsten Sinne wird die Größe der Eingabe in Bezug auf eine Turing-Maschine-Implementierung des Algorithmus gemessen und es wird die Anzahl der Alphabetsymbole angegeben, die zum Codieren der Eingabe benötigt werden.

Dies ist natürlich eher abstrakt und in der Praxis sehr schwierig oder zumindest sehr ärgerlich - wir müssten uns überlegen, wie wir Delimeter usw. spezifizieren usw. In der Praxis passiert normalerweise, dass wir danach suchen Eine Proxy- Messung der Größe der Eingabe - etwas Bequemeres und Zugänglicheres, das jedoch keine mathematischen Probleme bei unserer Analyse verursacht.

Mit Ihrem "abcde" -Beispiel wäre es normalerweise so, dass das Alphabet, das wir für die Eingabe verwenden, klein ist. Selbst mit der Proxy-Messung von Zeichen wussten wir, dass wir selbst auf einer Turing-Maschine, wenn wir uns die Mühe machen, Geben Sie eine Eingabecodierung an, die "abcde" in eine codierte Form mit einer Länge von höchstens 5 × c für eine Konstante c konvertiert . Diese Erweiterung um eine Konstante würde in unserer asymptotischen Analyse normalerweise keinen Unterschied machen, da wir routinemäßig konstante Faktoren verwerfen.$5$$5\times c$ $c$

In einem anderen Fall messen wir häufig die Größe eines Eingabegraphen anhand der Anzahl der Scheitelpunkte . Wenn wir willkürlich große Graphen spezifizieren wollen, ist die Größe der codierten Eingabe nicht einfach n - was ist zum Beispiel mit den Kanten passiert? Was wir wissen, ist, dass wir ein vernünftiges Codierungsschema verwenden können, das den Graphen in N = c ⋅ n 2 log n Bits darstellt. Dies ist eher eine Erweiterung als eine Konstante, aber in vielen interessanten Fällen haben wir es nur mit einer Granularität von Polynomen zu tun, und Polynome lassen sich auf vielfältige Weise komponieren - insbesondere als Beispiel, wenn Wir stellen fest, dass unsere Laufzeit O ( p $n$$n$$N = c\cdot n^{2}\log n$ wo p ein Polynom ist, dann wissen wir, dass es ein Polynom p 'gibt, so dass O ( p ( n ) ) = O ( p ' ( N ) ) , also wenn wir zum formalen Maß der Eingabe zurückkehren Wir sind immer noch in der Polynomzeit.$O(p(n))$$p$$p'$$O(p(n)) = O(p'(N))$

Ein Ort, an dem dies herunterfallen könnte, ist, wenn Sie mit Zahlen arbeiten. Da eine Zahl mit der Größe in n = O ( log m ) Bits codiert werden kann , wäre dies, wenn unsere Laufzeit O ( m ) wäre, O ( 2 n ) - exponentiell in der tatsächlichen Eingangsgröße -, was die Größe ergeben würde m eine schlechte Wahl für einen Proxy für die Eingabegröße, wenn wir zum Beispiel über die Zugehörigkeit zu P sprechen wollten (wenn Sie zu Strongly- N P -complete und Weakly- N $m$$n = O(\log m)$$O(m)$$O(2^{n})$$m$$\mathcal{P}$$\mathcal{NP}$$\mathcal{NP}$-komplett, denk dran). Auf der anderen Seite, wenn alles, woran wir interessiert waren, Entscheidbarkeit war, dann wäre es eine ausreichend gute Proxy-Maßnahme.

Es gibt zwar keine festgelegte Regel für die Auswahl eines Proxy-Maßes für die Eingabegröße, die Anforderung besteht jedoch darin, dass die Erweiterung oder Verkleinerung der Proxy-Größe im Vergleich zur Eingabegröße mit dem kompatibel ist, was Sie beweisen möchten. Als Faustregel gilt, dass konstante Faktoränderungen so gut wie keine Rolle spielen. Kleine Polynomfaktoren sind normalerweise in Ordnung und funktionieren für den größten Teil der Grundtheorie, die Sie sehen. Große Polynomfaktoren funktionieren möglicherweise noch in der Theorie, können aber in der Praxis eine böse Überraschung sein. und exponentielle Änderungsbeträge sind normalerweise viel zu extrem.

Es hängt von Ihrem Rechenmodell und leider auch manchmal vom Algorithmus selbst ab.

• $ababcd$
• Wenn Ihr Modell der RAM ist, entspricht die Größe der Eingabe der Anzahl der Register / Speicherzellen, in denen die Eingabe anfänglich verbleibt. Dies könnte missbraucht werden, da Sie technisch die gesamte Eingabe in ein Register schreiben könnten. Berechnungen sind jedoch dann teurer, wenn Sie das logarithmische Kostenmodell verwenden.
• $w$$w$

Viele Algorithmen werden jedoch nicht in Bezug auf die "tatsächliche" Eingabegröße gemessen. Dann muss man genau hinschauen, worauf sich die Aussage der Analyse bezieht.

• $O(n\log n)$$n$$O(1)$$n$
• $n\times n$

$n$