Hier ist ein interessantes Programmierpuzzle, auf das ich gestoßen bin. Gegeben ein Array von positiven ganzen Zahlen und eine Zahl K. Wir müssen Paare (a, b) aus dem Array finden, so dass a % b = K .
Ich habe eine naive O (n ^ 2) Lösung, wo wir nach allen Paaren suchen können, so dass a% b = k ist. Funktioniert aber ineffizient. Wir können sicherlich besser als das können wir nicht? Irgendwelche effizienten Algorithmen für das gleiche? Oh, und es ist KEINE Hausaufgaben.
Sortieren Sie Ihre Array- und Binärsuche oder behalten Sie eine Hashtabelle mit der Anzahl der einzelnen Werte in Ihrem Array.
Für eine Zahl x können wir den größten y finden, so dass x mod y = K als y = x - K . Binäre Suche nach y oder suchen Sie in Ihrem Hash nach und erhöhen Sie Ihre Anzahl entsprechend.
Nun, das ist nicht unbedingt der einzige Wert, der funktioniert. Zum Beispiel 8 mod 6 = 8 mod 3 = 2 . Wir haben:
Dies bedeutet, dass Sie auch alle Teiler von y testen müssen. Sie können die Teiler in O(sqrt y) finden, was Ihnen eine Gesamtkomplexität von O(n log n sqrt(max_value)) bei Verwendung der binären Suche und O(n sqrt(max_value)) bei einer Hash-Tabelle gibt (empfohlen, besonders wenn Ihre Zahlen nicht sehr groß sind).
Behandeln Sie das Problem so, dass es zwei separate Arrays als Eingabe hat: eins für die a-Zahlen und ein% b = K und eins für die b-Zahlen. Ich gehe davon aus, dass alles & gt; = 0 ist.
Zuallererst können Sie jedes b & lt; = K. verwerfen.
Denken Sie nun an jede Zahl in b, die eine Folge K, K + b, K + 2b, K + 3b ... erzeugt. Sie können dies mit einem Zahlenpaar (pos, b) aufzeichnen, wobei pos um 1 erhöht wird b in jeder Phase. Beginnen Sie mit pos = 0.
Halten Sie diese Sequenzen in einer Prioritätswarteschlange, so dass Sie zu jedem Zeitpunkt den kleinsten pos-Wert finden können. Sortieren Sie das Array einer Zahl - Sie könnten dies im Voraus tun und alle Duplikate verwerfen.
%Vor%Im schlimmsten Fall vergleicht man am Ende jede Zahl mit jeder anderen Zahl, was der einfachen Lösung entspricht, aber mit Prioritätswarteschlangen und Sortieraufwand. Große Werte von b können jedoch in der Prioritätswarteschlange nicht untersucht werden, während mehrere Zahlen durchlaufen werden. In diesem Fall ist dies besser - und wenn viele Zahlen verarbeitet werden müssen und alle unterschiedlich sind, müssen einige von ihnen groß sein.
Diese Antwort erwähnt die Hauptpunkte eines Algorithmus (genannt DL , weil er "Teilerlisten" verwendet) und gibt Details über ein Programm namens amodb.py.
Sei B das Eingabe-Array mit N positiven ganzen Zahlen. Ohne großen Verlust der Allgemeinheit nehme man B[i] > K für alle i an und dass B in aufsteigender Reihenfolge ist. (Beachten Sie, dass x%B[i] < K wenn B[i] < K ist und wo B[i] = K , man kann Paare (B [i], B [j]) für alle j>i melden. Wenn B nicht anfänglich sortiert ist, berechnen Sie Kosten von O(N log N) , um es zu sortieren.)
In Algorithmus DL und Programm amodb.py ist A ein Array mit K, das von den Array-Elementen subtrahiert wird. Dh, A[i] = B[i] - K . Beachten Sie, dass wenn a%b == K , dann für einige j wir a = b*j + K oder a-K = b*j haben. Das heißt, a%b == K iff a-K ist ein Vielfaches von b . Wenn a-K = b*j und p ein beliebiger Faktor von b ist, dann ist p ein Faktor von a-K .
Die Primzahlen von 2 bis 97 heißen "kleine Faktoren". Wenn N Zahlen gleichmäßig zufällig aus einem Intervall [X, Y] ausgewählt werden, haben die Zahlen in der Größenordnung von N / ln (Y) keine kleinen Faktoren; eine ähnliche Zahl wird einen größten kleinen Faktor von 2 haben; und abnehmende Proportionen werden sukzessive größere kleinste Faktoren haben. Zum Beispiel wird im Durchschnitt etwa N/97 durch 97 teilbar sein, etwa N/89-N/(89*97) nach 89, aber nicht 97 usw. Im Allgemeinen, wenn Mitglieder von B zufällig sind, Listen von Mitgliedern mit bestimmten größten kleinen Faktoren oder ohne kleine Faktoren sind sub-O (N / ln (Y)) in der Länge.
Wenn eine Liste Bd Elemente von B enthält, die durch den größten kleinen Faktor p teilbar sind, testet DL jedes Element von Bd gegen Elemente der Liste Ad, wobei diese Elemente von A durch teilbar sind p . Bei einer Liste Bp für Elemente von B ohne kleine Faktoren testet DL jedes Element von Bp auf alle Elemente von A. Beispiel: Wenn N=25 , p=13 , Bd=[18967, 23231] und Ad=[12779, 162383] , dann testet DL , ob% of co_de% Null ist. Beachten Sie, dass die Anzahl der Tests in diesem Beispiel (und vielen anderen) halbiert werden kann, indem Sie 12779%18967, 162383%18967, 12779%23231, 162383%23231 beachten, aber amodb.py enthält diese Optimierung nicht.
DL macht 12779<18967 verschiedene Listen für J verschiedene Faktoren; In einer Version von amodb.py, J und der Faktorsatz ist weniger als 100. Ein größerer Wert von J=25 würde die J -Zeit erhöhen, um Divisorlisten zu initialisieren, würde aber die O(N*J) -Zeit auf etwas verringern Prozessliste Bp gegen Elemente von A. Siehe Ergebnisse unten. Zeit, andere Listen zu verarbeiten, ist O(N*len(Bp)) , was in scharfem Kontrast zur Komplexität von O((N/logY)*(N/logY)*J) für die Methode einer vorherigen Antwort steht.
Als nächstes wird von zwei Programmläufen ausgegeben. In jedem Satz stammt die erste O(n*sqrt(Y)) -Zeile aus einem naiven O (N * N) -Test und die zweite aus DL . (Beachten Sie, dass sowohl DL als auch die naive Methode schneller laufen würden, wenn zu kleine A-Werte schrittweise entfernt würden.) Das Zeitverhältnis in der letzten Zeile des ersten Tests zeigt ein enttäuschend niedriges Beschleunigungsverhältnis von 3,9 für DL gegen naive Methode. Für diesen Lauf enthielt Found nur die 25 Primzahlen weniger als 100. Für den zweiten Lauf, mit einer besseren Beschleunigung von ~ 4.4, enthielt factors die Zahlen 2 bis 13 und Primzahlen bis zu 100.
Programm amodb.py:
%Vor%Tags und Links algorithm language-agnostic number-theory