Wost/Average/Best Case |
| 25.04.2010, 21:11 | Auf diesen Beitrag antworten » | ||||
| Parwana | Wost/Average/Best Case 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 |
||||
|
|
|||||
| 25.04.2010, 21:29 | Auf diesen Beitrag antworten » | ||||
| ed209 | RE: Wost/Average/Best Case
Warum?
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:37 | Auf diesen Beitrag antworten » | ||||
| Parwana | 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. |
||||
| 25.04.2010, 21:45 | Auf diesen Beitrag antworten » | ||||
| ed209 | Lies die Aufgabe genau:
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 
|
||||
| Anzeige | |||||
|
|
|||||
| 25.04.2010, 21:55 | Auf diesen Beitrag antworten » | ||||
| Parwana | 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. |
||||
| 25.04.2010, 22:38 | Auf diesen Beitrag antworten » | ||||
| Parwana | 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? |
||||
|
|
