Der K-te Faktor von N – ein O(sqrt n)-Algorithmus

Einführung

Kürzlich habe ich den Beitrag „Lerne die Big-O-Notation ein für alle Mal“ geschrieben. In diesem Beitrag gehe ich auf alle Arten der Big-O-Zeitnotation ein, die im Big-O-Spickzettel verfügbar sind. Und ich hätte nicht gedacht, dass es außer diesen sieben noch weitere Zeitnotationen geben würde.

Als ob das Universum selbst mich demütigen und sich über meine Unwissenheit lustig machen würde, stieß ich auf ein LeetCode-Problem mit einer Lösung von O(√n) Zeit. Was übersetzt werden könnte in O(N^1/2), wenn Sie verrückt sind.

Das Problem

Sie erhalten zwei positive ganze Zahlen n und k. Ein Faktor einer ganzen Zahl n ist als eine ganze Zahl i definiert, wobei n % i == 0.

Betrachten Sie eine Liste aller Faktoren von n, sortiert in aufsteigender Reihenfolge, geben Sie den k-ten Faktor in dieser Liste zurück oder geben Sie -1 zurück, wenn n weniger als k Faktoren hat.

Die offensichtliche Lösung

Nun, wenn Sie wie ich sind, war Ihr erster Gedanke, jede Zahl von 1 bis n durchzugehen, zu prüfen, ob es sich um einen Faktor handelt, und ihn zurückzugeben, wenn er im gewünschten k-Index liegt.

Der Code sieht so aus:

def getkthFactorOfN(n, k):
    result = 0
    for i in range(1, n + 1):
        if n % i == 0:
            result = result + 1
            if result == k:
                return i
    return -1

Das ist alles schön und gut, aber es ist „nur“ O(n). Schließlich gibt es nur eine Schleife und diese geht bis n 1.
Bei der Berücksichtigung der Zeitnotation wird jede andere Operation verworfen.

Aber, mein Freund, es gibt einen Haken.

Faktoren verstehen

Wenn man darüber nachdenkt, werden Faktoren ab einem bestimmten Punkt „gespiegelt“.

Nehmen Sie zum Beispiel die Zahl 81. Ihre Faktoren sind [1, 3, 9, 27], wobei:

• 1 * 81 = 81
• 3 * 27 = 81
• 9 * 9 = 81
• 27 * 3 = 81
• 81 * 1 = 81

Wenn Sie die Zahl 9 nicht mitzählen, werden die Vorgänge einfach wiederholt und umgedreht. Wenn Sie n durch einen seiner Faktoren dividieren, erhalten Sie einen weiteren Faktor.
Erwarten Sie die Quadratwurzel von n, wo sie selbst quadriert ist (duh).

Mit diesem Wissen wissen wir jetzt, dass wir die Schleife nicht bis zu n-mal (mit range(1, n 1)) durchlaufen müssen, sondern einfach bis zu math.sqrt(n). Danach haben wir alle Faktoren, die wir brauchen!

Die nicht so offensichtliche Lösung

Da wir nun alles haben, was wir brauchen, müssen wir diese Schleife von 1 -> umwandeln. n bis 1 -> sqrt n.

Ich gebe einfach den Code hier ein und wir gehen die Zeilen eine nach der anderen durch.

def getkthFactorOfN(n, k):
    i = 1
    factors_asc = []
    factors_desc = []
    while i * i <= n:
        if n % i == 0:
            factors_asc.append(i)
            if i != n // i:
                factors_desc.append(n // i)
        i += 1
    if k <= len(factors_asc):
        return factors_asc[k-1]
    k -= len(factors_asc)
    if k <= len(factors_desc):
        return factors_desc[-k]
    return -1

Uff, es ist viel komplexer. Lassen Sie es uns aufschlüsseln:

Zuerst initialisieren wir i = 1. Diese Variable wird bei der Suche nach Faktoren als „Zahl, bei der wir uns gerade befinden“ verwendet.

Zweitens erstellen wir zwei Arrays: Faktoren_asc und Faktoren_desc. Der Zauber dabei ist, dass wir Faktoren zu „factors_asc“ hinzufügen – sie werden so benannt, weil sie automatisch in aufsteigender Reihenfolge angezeigt werden.
Immer wenn wir etwas zu „factors_asc“ hinzufügen, teilen wir n durch es und fügen es zu „factors_desc“ hinzu. Ähnliche Logik hier; Sie werden bequem in absteigender Reihenfolge hinzugefügt.

Dann beginnen wir unsere Schleife. Hier habe ich es in „while i * i <= n“ geändert, da wir aufhören, wenn wir die Wurzel von n erreichen.

Wir beginnen mit der Prüfung, ob die aktuelle Zahl ein Faktor ist (n % i == 0). Wenn ja, können wir es an unser Factors_asc-Array anhängen.

Als nächstes erhalten wir den „Umkehrfaktor“ von i. Wir können dies tun, indem wir prüfen, ob i != n // i, oder mit anderen Worten, ob es nicht die Wurzel ist. Dies liegt daran, dass die Wurzel nicht in beiden Arrays dupliziert werden darf. Ist dies nicht der Fall, erhalten wir den umgekehrten Faktor, indem wir n // i ausführen und das Ergebnis in Factors_desc.

anhängen

Danach addieren wir 1 zu i und setzen unsere Schleife fort.

Nachdem die Schleife abgeschlossen ist, müssen wir über alle Fakultäten verfügen, die wir benötigen.

Wir beginnen mit der Prüfung, ob k in der ersten Hälfte einschließlich der Wurzel (die als Mitte interpretiert werden kann) liegt, mit if k <= len(factors_asc). Wenn ja, rufen Sie den Index aus diesem Array ab (denken Sie daran: Arrays beginnen bei Null!).

Wenn nicht, müssen wir die Anzahl der gefundenen Faktoren von k subtrahieren und erneut prüfen – mit k -= len(factors_asc) und wenn k <= len(factors_desc).

Wenn k innerhalb von „factors_desc“ liegt, erhalten Sie seinen Wert mit „factors_desk[-k]“ (vom letzten zum ersten).

Wenn alles fehlschlägt, geben Sie -1 zurück.

Die Kurve

Wenn Sie sich fragen, wo im Kurvendiagramm es landet, liegt es zwischen O(n) und O(log n), was besser als ersteres und schlechter ist als Letzteres. Hier ist eine Grafik:

Verfügbar bei Mathspace

Abschluss

Dies war eine Fahrt zum Entdecken und Forschen. Vielen Dank, dass Sie bis hierher gelesen haben.

Wenn Sie eine bessere Optimierung wünschen, können Sie die Variablen „factors_asc_len“ und „factors_desc_len“ erstellen und jedes Mal, wenn Sie einen Wert an diese Arrays anhängen, 1 hinzufügen, sodass die Methode len() nicht aufgerufen werden muss, da dies bei dieser Methode der Fall ist O(n), sodass es Auswirkungen auf die Zeitnotation haben kann.

Viel Glück im Studium und bis zum nächsten Mal!

Das obige ist der detaillierte Inhalt vonDer K-te Faktor von N – ein O(sqrt n)-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!