Im Theorietestat #3 gibt es eine Aufgabe, in der die Komplexität von CounterNotZeroMatrix überprüft werden soll. Ich habe in diesem Fall die Höhe der Matrix (also M.length) n genannt und die Breite (M[ i ].length, was für eine echte Matrix unabhängig von i sein sollte). Mit allen Konstanten noch drin, kommt in etwa so etwas heraus:
Was die cs im einzelnen sind, ist ja nicht weiter relevant. Wenn man die Konstanten rausschmeißt, könnte man sagen, die Komplexitätsklasse ist Theta(n*m+n). Was ich mich gerade frage ist, ob ich das +n nicht einfach rausschmeißen kann. Wenn wir m = 0 wählen würden und nur n gegen unendlich streben lassen würden, dann wäre das n relevant, da n*m dann immer 0 ist. Für ein festen m > 1 wird m*n aber schon Ordnung n sein und dann ist das +n redundant. Wenn wir z.B. sagen n=c*m mit konstantem c und lassen so n gegen unendlich streben dann ist das schon Ordnung n^2, wodurch das +n wieder vernachlässigbar wird.
Also etwas allgemeiner formuliert wäre meine Frage: Wenn die Komplexität von mehreren Variablen abhängt, sollen wir nur den Grenzwert von allen Variablen gleichzeitig gegen unendlich betrachten oder auch Fälle, in denen eine Variable fest ist und die andere alleine gegen unendlich strebt, so dass sich die asymtotische Komplexität nicht ganz so sehr vereinfacht? Wie ist es z.B. bei n/m?
