Du guckst von innen nach außen welche Laufzeit was hat.
Mein Beispiel:
1. In der List-Comprehension haben wir zuerst die Tupelerstellung O(1) = fixe Zeit, weil tupelerstellung fixe Zeit und len(x) auch fixe Zeit, da jedes String-Objekt die Länge als Feld hat. (nicht wie bei C-Strings, strlen(s) braucht O(slen), da es den Terminator suchen muß!*) Das ganze wird dann n-mal ausgeführt durch die Listcomprehension: n*O(1) = O(n) = Zeit direkt abhängig von n.
2. max läuft die Liste schrittweise ab und behält einfach einen Zeiger auf das Maximum. Der Vergleich kostet auch maximal fixe Zeit, also O(1), und wieder n*O(1) = O(n)
3. Der Zugriff auf das erste Element eines Tupels ist wieder O(1)
Wir brauchen als für das innere O(n) Zeit, für das äußere O(n) Zeit, für das undekorieren O(1), O(n) + O(n) + O(1) = O(n) , also O(n) Zeit für das ganze. Die Zeit die es braucht wächst also linear mit der Anzahl von Elementen in der Liste.
Dein Beispiel:
1. Das Dekorieren mit dem Key spar ich mir jetzt mal, das ist genauso wie oben O(n) wo ich explizit dekoriert hab, weil sorted intern genau das macht: dekorieren.
2. Dann das sortieren, das braucht O(n*log^1.<irgendwas> n), abgekürzt von _mir_ (nicht ganz korrekt) immer geschrieben als O(n*log n), wächst also schneller als linear.
3. Das holen des letzten Elements braucht wieder O(1).
Wir haben also: O(n) + O(n*log n) + O(1) = O(n*log n), weil asymptotisch die Laufzeit sich an C*n*log n annähert weil es der Term ist der am schnellsten wächst (wobei C eine beliebige nach oben beschränkte Konstante ist).
Damit skaliert Deine Methode nicht so gut wie direkt max zu benutzen mit dekorierten Werten, weil es eben schneller als linear wächst.
Das sagt natürlich nichts darüber aus welche Methode auf der Länge die der OP will schneller ist, es ist nur ein Verhalten was die jeweilige Methode hat wenn n immer größer wird. Sprich: wenn man die Laufzeit in Relation zu n graphisch aufträgt und Deine Methode am Anfang schneller ist gibt es auf jeden Fall irgendwo einen Punkt wo der Graph den Graphen meiner Funktion schneidet, da dieser langsamer wächst. Wo dieser Punkt ist, darüber sagt das ganze was ich da gemacht hab gar nichts aus.
Der Punkt kann zum Beispiel auch bei n=1**10 sein, das würde bedeuten dass Deine Methode für alle praktischen Belange vorzuziehen ist, obwohl sie schlechteres Laufzeitverhalten hat. Das ist aber hier sicherlich nicht der Fall, und meine "gut-intuition" (wie übersetzt man das auf Deutsch?) sagt mir dass meine Methode immer die schnellere ist.
Hoffe das hilft.
--- Heiko.
* wobei man hier anmerken muß dass das wieder eine Frage ist ob es eine feste obere Grenze für die Stringlänge gibt (die es ja im Endeffekt immer gibt, da der Speicher des Computers nach oben limitiert ist). Wenn wir zum Beispiel annehmen dass die Strings alle der Länge nach kleiner als 1000 sind, ist auch die Laufzeit hierfür immer <= 1000, also wieder Laufzeit = O(1) <=> Laufzeit <= C*1 für C=1000. Wenn wir das nicht annehmen (also dass die Strings auch unendlich lang sein können), müßten wir das ganze etwas komplizierter werden lassen, wo ich jetzt keinen Bock drauf hab.