Assoziatives, mehrdimensionales Array sortieren

[1unitedpower]

In einem Array aus Zeilenarrays habe ich beim Zugriff auf t Werte einer Zeile einen Arrayzugriff um das Zeilenarray aus dem Haupt-Array zu holen, und dann t Array-Zugriffe für die Felder.

Du gehst von einer anderen Operation aus als ich. Bzw. du hast mehrere primitive Operationen miteinander verknüpft und eine zusammengesetze Operation analysiert. Ich sprach nur vom Zugriff über einen Index auf einen Datensatz einer Datensatzsammlung. Wenn die Datensatzsammlung ein Zeilenarray ist, braucht dieser Zugriff konstante Laufzeit. Wenn die Sammlung ein Spaltenarray ist, dann braucht dieser Zugriff O(m), ein Array-Zugriff je Spalte (~Feld), das ist die asymptotische Laufzeit von get_record.

Du hast jetzt aber noch mehr gemacht, du hast dieser Operation noch t Lesezugriffe auf Felder eines Datensatzes nachgelagert. Im Falle des Zeilenarrays haben wir dann O(1) + O(t). Im Falle des Spaltenarrays haben wir dagegen: O(m) + O(t). Das ist die Lazfzeit, der zusammengesetzten Operation, die du gemeint hast, aber unter Einbeziehung der Anzahl der Felder m des Datensatzes.