CG/2014-Hauptklausur, Aufgabe 6 d) 2.

[StephanGocht]

Der Aufwand für den Aufbau ist linear bei Gittern: Du weißt ja sofort wo das dreieck hin muss wenn du dir es anschaust, musst es also nicht zweimal anschauen. Man muss das Ergebnis dann zwar noch eintragen und ein dreieck könnte ja über alle Felder des gitters gehen aber das ist nicht die Frage. Die Laufzeit dürfte O(n*m) sein wobei n die anzahl der dreiecke und m die anzahl der Felder im Gitter ist (im schlimmsten Fall muss man jedes dreieck in alle gitter zellen eintragen).