Zeitkomplexität eines Auswahlproblems

Question

Ich frage mich, wie die Zeit Komplexität des folgenden Auswahlproblems ist, das ich beim Nachdenken an ein String-Matching-Problem gefunden habe.

Angenommen, die Operationen von Ganzzahlen benötigen $ O (1) $ Zeit

Wir erhalten $ M $ Sets mit jeweils $ N $ Integer -Nummern. Wir möchten genau eine Ganzzahl aus jedem Satz auswählen, um ein Satz S zu erstellen, so dass $ ~ l = max (s) - min (s) ~ $ minimiert wird.

Zum Beispiel n = 4, m = 3:

$ S_1 = {1, 43, 71, 101 } $

$ S_2 = {18, 53, 80, 107 } $

$ S_3 = {3, 16, 51, 208 } $

Jetzt

$ ~ S = {43, 53, 51 } $

hat eine Nummer von jedem Satz und

$ ~ l = max (s) - min (s) = 53 - 43 = 10 ~ $

Wich ist der minimal mögliche Wert von $ l $ (glaube ich).

Das erste, was ich ausprobierte, war eine Reduzierung des Set -Cover -Problems, aber ich konnte keine finden.

Answer 1

Wenn Sie versuchen, $ NP $ $ -Härtigkeit dieses Problems zu beweisen, benötigen Sie eine Reduzierung aus (nicht zu).

Wie auch immer, ich glaube nicht, dass dies $ np $ -Hard ist (es sei denn $ P = NP $)

Angenommen, die $ s_i $ werden sortiert.

Angenommen, Sie entscheiden, dass Element $ x in S_J $ minimal sein wird. Jetzt ineinander sind das kleinste Element mehr (oder gleich) $ x $ mit Binärsuche und das Maximum unter diesen.

Tun Sie dies für jede der $ mn $ number, vorausgesetzt, es ist das Minimum. Wählen Sie das beste Set, das Sie bekommen. Dies gibt Ihnen einen Polynomzeitalgorithmus: $ m log n $ Zeit für jedes der $ Mn $ Elements, die einen $ o (m^2n log n) $ Time -Algorithmus gibt.