Stuck auf Komplexitätsanalyse eines kniffligen Programms

Question

Wirklich stecken die Komplexitätsanalyse dieses Problems. Bei den Ziffern 0-9 müssen wir alle Nummern der maximalen Länge k finden, deren Ziffern in aufsteigender Reihenfolge sind.

for example if k = 3 , numbers can be 0,00,000,01,02,03,04,.... 1,11,111,12,... 

So ist die Frage im Grunde, dass, wenn Wiederholungen für die Ziffern erlaubt, Wie viele solche Kombinationen sind möglich, alle Zahlen finden weniger als size k (less than digit length k), dass Ziffern von rechts nach links wird nicht abnehmende Ordnung sein.

Answer 1

Nummern mit höchstens k Ziffern, die schwach ansteigen, sind in 1-1-Korrespondenz mit binären Strings der Länge k+10, mit genau zehn 1. Die Anzahl der aufeinander folgenden 0 s kurz vor der i ten eins und eins in der binären Zeichenfolge ist die Anzahl der i Ziffern in der ursprünglichen Zahl. Zum Beispiel, wenn k=7, dann 001119 Karten zu 00100011111111010 (2 Nullen, 3 Einsen, 0 Zweien, 0 Dreien, ..., 0 Achten, 1 Neun, 1 Ziffer übrig, um die Anzahl der Ziffern bis zu 7).

Diese binären Zeichenfolgen sind einfach zu zählen: Es gibt choose(k+10, 10)-1 von ihnen (fehlt eine, weil die leere Zahl nicht erlaubt ist). Dies kann in O (1) arithmetischen Operationen (tatsächlich 10 Additionen, 18 Multiplikationen und eine Division) berechnet werden.

Answer 2

Ich habe nicht genug Ruf, um Pauls Antwort zu kommentieren, also füge ich eine andere Antwort hinzu. Die Formel ist nicht choose(k+10, 10) wie von Paul angegeben, es ist choose(k+9, 9). Wenn wir k=2 haben, choose(2+10, 10) gibt uns 66, wenn es nur 55 Zahlen gibt, die die Eigenschaft erfüllen.

Wir wählen Sterne und Trennzeichen aus, wobei die Trennzeichen unsere Ziffern in Buckets von 0 bis 9 aufteilen, und Sterne geben an, wie viele Ziffern aus einem Bucket ausgewählt werden sollen. (Eg **|**||*||||||* entsprechend 001139)

Die Begründung dahinter k+9 sind und nicht k+10 ist wie folgt: wir 9 Separatoren zwischen 10 Ziffern wählen, also während wir k Entscheidungen für die Sterne haben wir nur 9 Möglichkeiten haben für die Separatoren.

Answer 3

Ich habe auch nicht genug Ruf, also kann ich Pauls oder Globes Antwort nicht beantworten.

Globe Antwort wählen (k + 9,9) ist nicht perfekt, denn es zählt nur die Lösungen, wo die Zahlen genau k Ziffern haben. Aber die ursprünglichen Probleme erlauben auch Zahlen mit weniger Ziffern.

Pauls Antwort wählen (k + 10,10) zählt auch diese kürzeren Zahlen, aber es erlaubt auch Zahlen mit Nullstellen. Sagen wir k = 7, dann beschreibt die folgende binäre Zeichenfolge eine Zahl ohne Ziffern: 11111111110000000. Wir müssen diese ausschließen.

So ist die Lösung: wählen (k + 10,10) -1