Komplexitä ÜbungsN UE3 (Beispiel:ChecerNotZero)

Samdarwisch
Neuling
Neuling
Beiträge: 2
Registriert: 13. Mai 2017 19:42

Komplexitä ÜbungsN UE3 (Beispiel:ChecerNotZero)

Beitrag von Samdarwisch » 13. Jun 2017 11:32

Im Beispiel ChecerNotZero wird hier der Best Case so erklären :

dass dieser vorzeitige Abbruch, so schnell wie möglich ausgeführt wird, also direkt das erste
Listenelement ungleich 0 ist.

wie ich verstanden habe ,wenn das erste Element ungleich null ,das wird True zurückgegebenund soll das nächste Element überprüft werden .
wenn das Erste Element GLEICH null ist dann ist ein Abbruch und das ist der Best Case

die frage ist habe ich falsch verstanden oder soll das Elemnt ungleich null sein !


3.1.2 Algorithmus: CheckerNotZero
Der zweite betrachtete Algorithmus uberpruft, ob eine Liste Elemente enthalt, die ungleich 0 sind.
Zuerst werden wieder den relevanten Eingabegroen Variablennamen gegeben. In diesem Fall ist wieder
die einzige Eingabe eine LinkedList. Die Lange dieser Liste wird mit n bezeichnet.
Danach wird untersucht, ob sich Best- und Worst Case unterscheiden. Im Code sind zwei return-
Statements vorhanden z 5 und 8 was dafür spricht. Der vorzeitige Abbruch (Z.5) wird ausgelost,
falls das aktuelle Element ungleich 0 ist, wie aus der if-Anweisung (Z.4) ersichtlich ist. Der Best Case
ist also, dass dieser vorzeitige Abbruch, so schnell wie moglich ausgefuhrt wird, also direkt das erste
Listenelement ungleich 0 ist.





1 public class CheckerNotZero {
2 public boolean checkerNotZero ( ListItem < Integer > head ){
3 for( ListItem < Integer > current = head ; current != null ; current = current . next ){
4 if( current .key != 0){
5 return true ;
6 }
7 }
8 return false ;
9 }
10 }






Danke im Voraus
Sam

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

Re: Komplexitä ÜbungsN UE3 (Beispiel:ChecerNotZero)

Beitrag von invariant » 13. Jun 2017 12:08

Hallo,

Wie auch aus dem Code ersichtlich gibt der Algorithmus genau dann true zurück, wenn mindestens ein Element ungleich 0 ist.

Hier bitte auch aufpassen zwischen 0 - der Zahl - und null - dem Nullpointer - zu unterscheiden.

Wenn das erste Element ungleich 0 ist wird true zurückgegeben und kein weiteres Element überprüft.

Wenn Sie für den Best Case davon ausgehen, dass das erste Element gleich null ist, also die Liste nur ein Element hat ist das eine Einschränkung der Länge der Liste und die ist hier nicht zulässig.

Ich hoffe das hat Ihre Frage beantwortet.

Gruß

Samdarwisch
Neuling
Neuling
Beiträge: 2
Registriert: 13. Mai 2017 19:42

Re: Komplexitä ÜbungsN UE3 (Beispiel:ChecerNotZero)

Beitrag von Samdarwisch » 13. Jun 2017 12:15

Vieln Dank für die Antwort

420MLGuWOTm9
Neuling
Neuling
Beiträge: 9
Registriert: 29. Mai 2015 14:33

Re: Komplexitä ÜbungsN UE3 (Beispiel:ChecerNotZero)

Beitrag von 420MLGuWOTm9 » 13. Jun 2017 22:36

In der VL wurde kommuniziert, dass Best Case und Worst Case nicht an Beispielen konstruiert werden sollen. Heißt, sollte man hier im BC nicht eher annehmen, dass mind. ein Element != 0 ist? BC ist, wenn die for-schleife frühzeitig abgebrochen wird, was auch geschehen kann, wenn nach 100 Elementen erst die if-Abfrage greift.

Antworten

Zurück zu „Archiv“