| Die letzten 6 Beiträge |
| 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? |
| 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. |
| ed209 |
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 
|
| 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. |
| ed209 |
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. |
| 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
| Dateianhang: |
 Uebung1.zip (81 KB, 475 mal heruntergeladen)
|
|
|
|
