Theorietestat #3: Best und Worst Case

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Theorietestat #3: Best und Worst Case

Beitrag von SophiaLi1 » 22. Jun 2017 11:46

Hallo,

bei der Bestimmung der Komplexität soll man immer untersuchen, ob sich der Best und Worst Case unterscheiden. In 3.1.1 bei dem Beispiel mit CounterNotZero hätte ich jetzt gesagt, dass sich Best und Worst Case nicht unterscheiden. Im Text ist das nicht eindeutig formuliert. Es klingt zunächst so, als würden Best und Worst Case sich nicht unterscheiden, allerdings wird dann später einmal die Komplexität für den besten Fall (beschrieben mit f(n)) und die Komplexität für den schlechtesten Fall (beschrieben mit g(n)) bestimmt. Warum bestimmt man die Fälle separat, wenn man vorher festgestellt hat, dass sich Best und Worst Case nicht unterscheiden?

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Theorietestat #3: Best und Worst Case

Beitrag von invariant » 22. Jun 2017 20:52

Hallo,

Wenn man die Komplexitätsklassen untersuchen will oder die Komplexitätsfunktionen für große n sind Best- und Worstcase tatsächlich gleich.
Der Unterschied ergibt sich im Beispiel nur durch eine Konstante, eben ob der counter erhöht wird oder nicht. Wenn man die Funktionen sauber mit allen Konstanten aufstellen will muss man an dieser Stelle also unterscheiden.

Ist aber vielleicht wirklich ein bisschen missverständlich formuliert.

Hoffe trotzdem das hat die Frage jetzt geklärt.

Gruß

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: Theorietestat #3: Best und Worst Case

Beitrag von SophiaLi1 » 23. Jun 2017 16:48

Hallo,

danke für deine Antwort. Sollen wir dann auf die Frage: "Unterscheiden sich Worst und Best Case?" an dieser Stelle mit ja oder nein antworten?

invariant
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 6. Mai 2017 19:01

Re: Theorietestat #3: Best und Worst Case

Beitrag von invariant » 24. Jun 2017 13:25

Hallo,

kommt ganz auf die Aufgabe an ;)

Grundsätzlich erstmal ja würde ich sagen, wenn die Konstanten nicht beachtet werden sollen kann man das aber auch ignorieren.

Gruß

Antworten

Zurück zu „Archiv“