Angenommen, einige Zahlen gegeben
%Vor% Sie müssen alle Paare finden (a, b) wobei a in der Liste vor b und a%b = 0 erscheint.
Hier sind solche Paare:
%Vor%Gibt es einen besseren Algorithmus als O (n 2 ) ?
?Sie können eine Liste aller Teiler der möglichen Ganzzahlen in der Eingabe = O (n ^ 1.5)
vorberechnenDanach iterieren Sie über die Eingabe, während Sie verfolgen, wie viel eine Zahl wert ist (d. h. wie viele Paare es bilden würde).
Für jede Zahl in der Eingabe müssen Sie über alle Teiler iterieren, d. h. O (n ^ 1.5)
Also ist die Gesamtkomplexität O (n ^ 1.5), wobei n das Maximum von 100000 und die Größe Ihrer Eingabe ist.
%Vor%Mit dynamischer Programmierung kann dies mit der Komplexität O (nlogn) gelöst werden. Ähnlich wie Münzwertproblem.
Bitte lesen Sie den folgenden Link für die Münzwertproblemlösung Problem der Münzbezeichnung
Tags und Links algorithm data-structures