Dieses Problem stammt von interviewstreet.com
Wir werden eine Reihe von ganzen Zahlen gegeben , der darstellt Liniensegmente so , dass Endpunkte des Segments sind und . Stellen Sie sich vor, dass von oben auf jedem Segment ein horizontaler Strahl nach links geschossen wird und dieser Strahl stoppt, wenn er ein anderes Segment berührt oder auf die y-Achse trifft. Wir konstruieren ein Array von n ganzen Zahlen, , wobei gleich der Länge des Strahls ist, der von der Spitze des Segments geschossen wird . Wir definieren .n i ( i , 0 ) , ( i , y i ) , v 1 , . . . , V n v i i V ( y 1 , . . . , Y n ) = v 1 + . . . + v n
Wenn wir zum Beispiel , dann ist , wie im Bild unten gezeigt:[ v 1 , . . . , v 8 ] = [ 1 , 1 , 3 , 1 , 1 , 3 , 1 , 2 ]
Für jede Permutation von können wir berechnen . Wenn wir eine gleichmäßig zufällige Permutation von wählen , was ist der erwartete Wert von ?[ 1 , . . . , N ] V ( y P 1 , . . . , Y p n ) p [ 1 , . . . , N ] V ( y P 1 , . . . , Y p n )
Wenn wir dieses Problem mit dem naiven Ansatz lösen, ist es nicht effizient und läuft praktisch für immer für . Ich glaube, wir können dieses Problem lösen, indem wir den erwarteten Wert von für jeden Stick unabhängig berechnen , aber ich muss noch wissen, ob es einen anderen effizienten Ansatz für dieses Problem gibt. Auf welcher Basis können wir den erwarteten Wert für jeden Stab unabhängig berechnen?v i
quelle
Antworten:
Stellen Sie sich ein anderes Problem vor: Wenn Sie Stöcke gleicher Höhe in n Schlitze platzieren müssten, dann den erwarteten Abstand zwischen den Stöcken (und den erwarteten Abstand zwischen dem ersten Stock und einem fiktiven Schlitz 0 ) und den erwarteten Abstand zwischen dem letzten Stock und einem fiktiven Slot n + 1 ) ist n + 1k n 0 n+1 da esk+1Lücken gibt, die in eine Längen+1passen.n+1k+1 k+1 n+1
Um auf dieses Problem zurückzukommen, ist ein bestimmter Stick daran interessiert, wie viele Sticks (einschließlich sich selbst) so hoch oder höher sind. Wenn diese Zahl , ist die erwartete Lücke links davon ebenfalls n + 1k .n+1k+1
Der Algorithmus besteht also einfach darin, diesen Wert für jeden Stick zu finden und die Erwartung zu addieren. Zum Beispiel, beginnend mit Höhen von , beträgt die Anzahl der Stöcke mit einer größeren oder gleichen Höhe [ 5 , 7 , 1 , 5 , 5 , 2 , 8 , 7 ] so ist die Erwartung 9[3,2,5,3,3,4,1,2] [5,7,1,5,5,2,8,7] .96+98+92+96+96+93+99+98=15.25
Dies ist einfach zu programmieren: zum Beispiel eine einzelne Zeile in R
gibt die Werte in der Beispielausgabe im ursprünglichen Problem an
quelle
Henrys Lösung ist einfacher und allgemeiner als diese!
ist ungefähr die Hälfte der erwarteten Anzahl von Vergleichen, die von randomisierter Quicksortierung durchgeführt werden.E[V]
Unter der Annahme, dass die Stöcke unterschiedliche Höhen haben , können wir eine geschlossene Lösung für wie folgt ableiten .E[Y]
Dann haben wir für jeden Index ( du warum?) Und daher V j = Σ j i = 1 X i j V = n Σ j = 1 v j = n Σ j = 1 j Σ i = 1 X i j .j vj=∑ji=1Xij
Die Linearität der Erwartung impliziert sofort, dass
Da entweder oder , haben wir . 0 1 E [ X i j ] = Pr [ X i j = 1 ]Xij 0 1 E[Xij]=Pr[Xij=1]
Schließlich, und das ist wichtig , die Bit-Werte , da die in sind verschieden und permutierten gleichmäßig, jedes Element der Untergruppe mit gleicher Wahrscheinlichkeit die seine größte in dieser Teilmenge Element. Somit ist . (Wenn die Elemente von nicht verschieden sind, haben wir immer noch .){ Y i , . . . , Y j } Pr [ X i j = 1 ] = 1Y {Yi,...,Yj} YPr[Xij=1]≤1Pr[Xij=1]=1j−i+1 Y Pr[Xij=1]≤1j−i+1
Und jetzt haben wir nur ein bisschen Mathe. wobei die te harmonische Zahl bezeichnet .
Nun sollte es trivial sein, (bis zur Gleitkomma-Genauigkeit) in -Zeit zu berechnen .E[V] O(n)
quelle
Wie in den Kommentaren erwähnt, können Sie die Linearität der Erwartung verwenden.
Sortieren Sie das : .y y1≤y2≤⋯≤yn
Berücksichtigen Sie für jedes den erwarteten Wert von .yi vi=E[vi]
Dann istE[∑ni=1vi]=∑ni=1E[vi]
Eine einfache und naive Möglichkeit, zu berechnen, wäre zunächst, eine Position für . Sag .E[vi] yi j
Berechnen Sie nun die Wahrscheinlichkeit, dass Sie an Position einen Wert .j−1 ≥yi
Dann ist die Wahrscheinlichkeit, dass Sie bei einen Wert und bei einen Wertj−1 <yi j−2 ≥yi
und so weiter, wodurch Sie berechnen können .E[vi]
Sie können es wahrscheinlich schneller machen, indem Sie tatsächlich rechnen und eine Formel erhalten (ich habe es aber selbst nicht ausprobiert).
Hoffentlich hilft das.
quelle
Erweiterung der Antwort von @Aryabhata:
Fixiere ein und nehme an, dass sich das Item an Position . Der genaue Wert der Höhe spielt keine Rolle, es kommt darauf an, ob die Elemente größer oder gleich oder nicht. betrachte daher die Menge von Elementen , wobei 1 ist, wenn , und andernfalls 0 ist.i yi j yi Z(i) z(i)k yk≥yi z(i)k
Eine Permutation auf der Menge induziert eine entsprechende Permutation auf die Menge . Man betrachte zum Beispiel die folgende Permission der Menge : "01000 (1) ". Der Punkt ist der Punkt in Klammern an Position , und die mit " " bezeichneten spielen keine Rolle.Z(i) Y Z(i) … z(i)i j …
Der Wert von ist dann 1 plus die Länge der Folge von konsektiven Nullen direkt links von . Daraus folgt, dass tatsächlich 1 plus die erwartete Länge aufeinanderfolgender Zeoren ist, bis die erste "1" erfüllt ist, wenn wir höchstens Bits aus der Menge auswählen. (ohne Ersatz). Dies erinnert an die geometrische Verteilung, mit der Ausnahme, dass sie ersatzlos ist (und die Anzahl der Ziehungen begrenzt ist). Die Erwartung ist , auf genommen wird als auch , als einheitliche Wahl auf dem Satz von Positionen .vi z(i)i E(vi) j−1 Z(i)∖z(i)i { 1 , … , n }j {1,…,n}
Sobald dies berechnet ist (in dieser Richtung ), können wir den Zeilen von @ Aryabhatas Antwort folgen.
quelle
Ich verstehe nicht wirklich, was du meinst, von Tags scheint es, dass du nach einem Algorithmus suchst.
Wenn ja, wie hoch ist die erwartete zeitliche Komplexität? mit den Worten: "Wenn wir dieses Problem mit dem naiven Ansatz lösen, ist es nicht effizient und läuft für n = 50 praktisch für immer." es scheint mir, dass Ihr naiver Ansatz es in exponentieller Zeit löst.
Ich habe einen O (n ^ 2) -Algorithmus im Auge.
quelle