Gegeben ein Dataset D_ {26xn} mit Spalten aus [a-z] (keine Spalte ist nur ein Beispiel) und n Beobachtungen. Jede Spalte (x) hat (r_x) eindeutige Zustände. Zeilen in D werden mit absteigender Priorität in den Spalten [a-z] sortiert.Wählen Sie den Operator in der Datenbank
Aufgabe: Für Spalten (b, j, p) geben Sie Indizes von Zeilen zurück, so dass Indizes identischer Zeilen aufeinanderfolgen. Die Reihenfolge zwischen Zeilen mit unterschiedlichen Werten für (b, j, p) ist unerheblich.
Kann es eine Lösung mit einer Komplexität von O (n) geben?
Sol1: Spalten (b, j, p) können sortiert werden und entsprechende Indizes zurückgegeben werden. Aber die Komplexität für diese Lösung ist O (no_columns * nlog (n)).
Sol2: Iterate über jede Zeile und hash sie. Aber Hashing wäre praktisch teurer.