Hinweis: Dies ist nicht die Frage, wie die GCF in O (n)Größter gemeinsamer Faktor in o (1)?
Sie haben zwei ganze Zahlen, n und i zu lösen. Wie können wir (in Pseudocode) GCM(n, i) in konstanter Zeit berechnen, wobei n und i die Domäne 0 -> infinity haben?
Die einzigen Lösungen, die ich gesehen habe, verwenden Rekursion oder Schleifen. Ich würde es gerne in ständiger Zeit machen, wenn das möglich ist.
Danke.
Nun, technisch ist das möglich, ja - zum Beispiel durch Erstellen einer Matrix vorberechneter Ergebnisse. Aber das ist wegen des wahnsinnigen Speicherverbrauchs kaum praktikabel.
N. B .: Diese Methode hat eine wichtige Voraussetzung:
n, i ∉ [0; ∞), sondern n, i ∈ [0; M], M ∈ [0; ∞) - das heißt der Wertebereich beliebig groß ist, aber immer noch fixiert.
Sonst wäre die Operation des Lesens von n und i in den Speicher asymptotisch linear, was O(1) sogar theoretisch unmöglich macht.
Danke. Ich hatte das Gefühl, dass das mit traditionellen Mitteln nicht möglich war. Interessante Ideen aber! – Hatefiend
Es muss keine Matrix sein, Sie können eine Bitmaske aller Faktoren der benötigten Zahlen erstellen und ein "und" der zwei Bitmasken machen. Es wäre jedoch ein sehr großer Tisch. –
Wie könnte es möglich sein, wenn die Frage explizit besagt, dass der Bereich von "i", "n" 0 bis unendlich sind? Sie können unendlich viele Antworten nicht vorberechnen. –
Warum denken Sie, dass dies möglich ist? Scheint mir eindeutig unmöglich. Übrigens hast du nach GCD gefragt, aber GCM geschrieben - ich vermute, dass das ein Tippfehler ist. –
Mögliches Duplikat von [Was ist der schnellste Weg, den GCD von zwei Zahlen zu finden?] (Http://stackoverflow.com/questions/22281661/what-is-the-fastest-way-to-find-the-gcd- von-zwei-Nummern) –