Theorietestat #3: CounterNotZeroMatrix: n*m + n oder einfach n*m

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Theorietestat #3: CounterNotZeroMatrix: n*m + n oder einfach n*m

Beitrag von LukasPhysiker » 29. Mai 2017 12:49

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:

Code: Alles auswählen

c1 + n*(m*(c2+c2)+c5+c6)+c4
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?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Theorietestat #3: CounterNotZeroMatrix: n*m + n oder einfach n*m

Beitrag von Prof. Karsten Weihe » 29. Mai 2017 14:44

Guten Tag "LukasPhysiker" (und Mitleser),

die Worst-Case- bzw. Best-Case-Komplexität sind Funktionen von einem oder mehreren Parametern, d.h. jeder Kombination von Parametern wird jeweils ein Worst-Case- bzw. Best-Case-Wert zugeordnet. Sie können nicht zur Vereinfachung davon ausgehen, dass die Parameter nach einem bestimmten Muster gemeinsam gegen unendlich gehen.

Dass Sie das Verhalten der beiden Funktionen betrachten unter der Annahme, dass die Parameter gegen unendlich gehen, kann nur dazu dienen, Summanden 'rauszuschmeißen, die von anderen Summanden in allen Parametern dominiert werden. Sie können beispielsweise einen Summand (m+n) 'rausschmeißen, wenn es einen Summanden m*n gibt.

Ist Ihre Frage beantwortet?

KW

LukasPhysiker
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 111
Registriert: 6. Mai 2017 13:05

Re: Theorietestat #3: CounterNotZeroMatrix: n*m + n oder einfach n*m

Beitrag von LukasPhysiker » 29. Mai 2017 21:47

Wenn ich das richtig verstehe, ist also der Summand n hier zu vernachlässigen? Dann habe ich es jetzt verstanden. Danke. :)

Antworten

Zurück zu „Archiv“