Informatiker Board | Praktische Informatik

Informatiker Board » Themengebiete » Praktische Informatik » Wost/Average/Best Case

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Wost/Average/Best Case

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Parwana
Grünschnabel

Dabei seit: 25.04.2010
Beiträge: 6

Wost/Average/Best Case

Zitatantwort auf diesen Beitrag erstellen

Hallo, ich hab Probleme dieses Aufgabenblatt zu lösen und zwar verstehe ich den Algorithmus nicht ganz, in der Aufgabe steht zwar, dass es ein Array sein soll mir sieht es jedoch nach einem Baum aus.

Und mir ist mir auch nicht ganz ersichtlich in welcher Form ich die Aufgabe 1 lösen soll bzw. habe ich Probleme diese zu lösen, sowie die anderen Aufgaben auf diesem Blatt.

Ich hoffe Ihr könnt mir Helfen.

Übungsblatt

Dateianhang:

Uebung1.zip (81 KB, 478 mal heruntergeladen)

25.04.2010 21:11

Nehmen Sie Parwana in Ihre Freundesliste auf

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

RE: Wost/Average/Best Case

Zitat:

Original von Parwana
Hallo, ich hab Probleme dieses Aufgabenblatt zu lösen und zwar verstehe ich den Algorithmus nicht ganz, in der Aufgabe steht zwar, dass es ein Array sein soll mir sieht es jedoch nach einem Baum aus.

Warum?

Zitat:

Und mir ist mir auch nicht ganz ersichtlich in welcher Form ich die Aufgabe 1 lösen soll bzw. habe ich Probleme diese zu lösen, sowie die anderen Aufgaben auf diesem Blatt.

Zu 1a)
An welchen Stellen passieren denn vergleiche und wie sieht der "worst-case"-Fall aus?

Gruß,
ED

PS: Das Programm ist fehlerhaft für ungrade n.

25.04.2010 21:29

Nehmen Sie ed209 in Ihre Freundesliste auf

Parwana
Grünschnabel

Dabei seit: 25.04.2010
Beiträge: 6

Also der Wost Case ist ja eigentlich immer gleich O(n), denn im schlimmsten Fall muss der Algorithmus das ganzen Array durchlaufen um an einen bestimmten Wert zu gelangen, und der Best Case danach auch O(1), denn im besten Fall ist es das Erste Element.

Ich bin weiß aber nicht so ganz in welcher Notation ich das schreiben soll und ich weiß auch nicht genau wie ich den Average Case.

Wie kommst du zum Schluss, dass das Programm für alle Ungeraden n fehlerhaft ist?, und ich Versteh nicht was "Gehen Sie davon aus, dass der gesuchte Schlüssel mit einer Wahrscheinlichkeit von
0:3 im Array enthalten ist..." bedeuten soll.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Parwana: 25.04.2010 21:37.

25.04.2010 21:37

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

Lies die Aufgabe genau:

Zitat:

Bestimmen Sie in Abhängigkeit von n ...
a) die exakte Anzahl der Vergleiche im Worst-Case.

Du musst die Vergleiche zählen, die der Computer machen muß.
Am einfachsten ist es wenn du das für ein konkretes Beispiel mal durchprobierst und dann verallgemeinerst.

Es steht auch nicht 0:3 sondern 0.3 was also 30% entspricht.

Zu dem Fehler später mehr, wenn die anderen Aufgaben gelöst sind smile

25.04.2010 21:45

Parwana
Grünschnabel

Dabei seit: 25.04.2010
Beiträge: 6

Hab ein paar Bespiele gemacht, kann aber kein Muster erkennen, bzw weiß ich nicht genau wie ich das Verallgemeinern soll.

Ich kann ja n und k selbst wählen oder?, wobei n<k sein muss damit sich der wert im Array befindet?

€dit: Also hab mir ein beispiel angesehen und muss feststellen, das der Best Case 2 ist, da der algo bei einem durchlauf 2 Werte vergleicht.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Parwana: 25.04.2010 21:58.

25.04.2010 21:55

Parwana
Grünschnabel

Dabei seit: 25.04.2010
Beiträge: 6

Hab das Ergebnis für Aufgabe 1 a und b

W(n)= 2* n/2 mit n=n+1 für n-ungerade
B (n)= 2, da 1 Durchlauf 2 Werte vergleicht

ich brauch aber noch Hilfe bei dem Average Case und

bei den beweisen.

€dit: Als Average Case habe ich 0.3*0,85n raus stimmt das?

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Parwana: 25.04.2010 23:58.

25.04.2010 22:38

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Wost/Average/Best Case