Seite 1 von 1

Theorietestat #3: Best und Worst Case

Verfasst: 22. Jun 2017 11:46
von SophiaLi1
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?

Re: Theorietestat #3: Best und Worst Case

Verfasst: 22. Jun 2017 20:52
von invariant
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ß

Re: Theorietestat #3: Best und Worst Case

Verfasst: 23. Jun 2017 16:48
von SophiaLi1
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?

Re: Theorietestat #3: Best und Worst Case

Verfasst: 24. Jun 2017 13:25
von invariant
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ß