Algorithmus zu aggregieren Punkte

Question

I eine Tabelle Rating

• row1 = (V1, K1, 5);
• row2 = (V2, K2, 7);
• row2 = (V1, K1, 3);

ich brauche die Punkte in einer aggregate Tabelle , so dass die Tabelle enthält

• row1 = (V1, K1, 8) zu aggregieren;
• row2 = (V2, K2, 7);

I Schleife einmal durch die Rating-Tabelle und eine Karte erstellen mit [key = (Col1, Col2), value = Points] Wenn der Schlüssel vorhanden fügt ich die Punkte sonst einen neuen Map-Eintrag erstellen. Die Rating-Tabelle kann fast 100 Einträge enthalten, deshalb wollte ich mehrere Durchgänge vermeiden.

Ist dies der effizienteste Weg?

Answer 1

Es hängt davon ab, welche Datenstruktur Sie zum Speichern der Karte verwenden. Wenn Sie eine Hash-Map verwenden, wird das Speichern und Lesen von dieser in der Komplexität konstant sein (O(1)). Dann machen Sie einen einzigen Durchgang mit einer Abfrage und höchstens einer Einfügung für jeden Eintrag im Array. Dies bedeutet, dass die gesamte Komplexität Ihres Algorithmus O(n) ist.

Allerdings ist die Eingabe allein O(n), was bedeutet, dass Sie nicht besser machen können.

Denken Sie daran, dass wenn Sie eine andere Implementierung der Karte wählen, z. Baumkarte wird sich die Komplexität ändern und Sie werden nicht die effizienteste Lösung erhalten.