 Charakteristische Operation? |
Björn
unregistriert
 |
|
| Charakteristische Operation? |
     |
Meine Frage:
Hey Leute,
was ist dem in dem Teilgebiet von Algorithmen unter einer charakteristischen Operation zu verstehen? Google liefert als Ergebnis lediglich, dass es sich dabei um das Suchen handelt? Das hilft mir aber auch nicht wirklich weiter.
Meine Ideen:
Gerne die Erklärung auch an einem Beispiel (wenn nicht zu aufwändig)
Vielen Dank :-)
|
|
27.04.2015 15:43 |
|
|
as_string 
Haudegen
Dabei seit: 06.11.2013
Beiträge: 638
Herkunft: Heidelberg
|
|
Hallo!
Ich glaube nicht, dass das ein wirklich feststehender Begriff in der Informatik ist (wäre mir zumindest noch nicht über den Weg gelaufen, was allerdings auch nicht immer etwas zu bedeuten hat...).
Du hast beim Googlen wahrscheinlich den Wikipedia-Artikel über Suchbäume gefunden gehabt. Bei einem solchen Suchbaum als Datenstruktur ist natürlich eine charakteristische Operation (also in diesem Fall das, wofür man den Baum überhaupt macht), natürlich das Suchen. Warum sonst auch einen "Suchbaum" aufbauen.
Umgekehrt bedeutet das allerdings nicht, dass mit "charakteristischer Operation" immer unbedingt "Suchen" gemeint ist.
Magst Du uns einfach mal sagen, in welchem Zusammenhang Du denn jetzt über diesen Begriff gestolpert bist? Ist es eine Aufgabe?
Gruß
Marco
|
|
|
27.04.2015 17:41 |
|
|
Björn
unregistriert
|
|
Ja, es war in der Tat der Wikipedia-Artikel über Suchbäume :-)
Und es handelt sich auch um eine Aufgabe, die lautet:
1. Gegeben sei ein Feld A der Länge n, das wie folgt initialisiert ist A[1] = 1, A[2] = 2, . . . ,
A[n] = n. In Pseudocode sind zwei Algorithmen abgebildet die eine Permutation des Feldes
A erzeugen.
a) Geben Sie die Laufzeit beider Algorithmen mit Hilfe der O-Notation an.
b) Implementieren Sie beide Algorithmen in der Programmiersprache Java.
c) Vergleichen Sie empirisch die Laufzeit beider Algorithmen, indem Sie für wachsende
Eingaben n= 103,5·103,104,5·104,105,5·105,106 die Laufzeit bestimmen und graphisch
bzw. tabellarisch darstellen. Vergleichen Sie die empirischen Laufzeiten mit den
Laufzeiten der O-Notation.
Hinweis: Die Funktion RANDOM(a,b) erzeugt eine ganze Zufallszahl zwischen a und b
(d.h. RANDOM(a,b) ∈ R = {a, a+ 1, a+ 2, . . . , b}).
PERMUTE1(A)
1 n=länge[A]
2 for i = 1 to n
3 for j = 1 to n
4 if RANDOM(0,1) == 1
5 tausche A[i] ↔ A[j]
6 return A
PERMUTE2(A)
1 n = länge [A]
2 for i = 1to n
3 tausche A[i] ↔ A[RANDOM(i, n)]
4 return A
|
|
|
27.04.2015 18:03 |
|
|
|
|
Und wo taucht in der Aufgabe die "charakteristische Operation" (habe ich auch noch nie gehört) auf?
Und wie kommst du bei der Aufgabe voran?
Und kontrolliere bitte, dass der kopierte Text auch so aussieht, wie er sollte:
(d.h. RANDOM(a,b) ∈ R = {a, a+ 1, a+ 2, . . . , b}).
tausche A[i] ↔ A[j]
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
27.04.2015 19:45 |
|
|
Björn
unregistriert
|
|
Ne, die charakteristische Operation war auf das Allgemeine bezogen.
Ich habe mit der Aufgabe das Problem, dass ich nicht recht weiß, wie man beginnen soll.
Muss jetzt der best case, average case oder der worst case berechnet werden?
Das wäre wichtig zu wissen, dann kann ich auch mit Formeln arbeiten und komme vielleicht voran :-)
|
|
|
27.04.2015 20:41 |
|
|
|
|
Da gibt es keinen best/worst case, der Ablauf ist immer der gleiche.
Und vergiss die Formeln, versuche es einfach mit Nachdenken.
Bei deinem ersten Algorithmus hast du 2 verschachtelte Schleifen mit je n Durchläufen, also insgesamt n*n.
Beim zweiten hast du nur eine Schleife mit n Durchläufen, also wird der zweite schneller ablaufen.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
27.04.2015 21:13 |
|
|
Björn
unregistriert
|
|
Sehe ich es richtig, dass es die best/worst case- Fälle dann eigentlich nur für Such-Algorithmen gibt?
|
|
|
27.04.2015 21:16 |
|
|
as_string
Haudegen
Dabei seit: 06.11.2013
Beiträge: 638
Herkunft: Heidelberg
|
|
Nein, das hat mit Suche oder nicht nichts zu tun.
Wenn Du einen Algorithmus hast mit unbekannten (z. B. zufällig generierten, oder auch allgemein aus Eingaben des Benutzers erzeugten oder so) Eingangsdaten, dann kann die Laufzeit von den Eingangsdaten abhängen, muss aber nicht.
Wenn Du die beiden Algorithmen anschaust, dann wirst Du feststellen, dass Du immer for-Schleifen hast, die von 1 bis n laufen. Bei einem bestimmen n müssen die also immer gleich häufig durchlaufen werden, egal was in dem Array drin steht und auch egal, welches Ergebnis die RANDOM()-Funktion jeweils liefert. Deshalb ist die Laufzeit immer von der selben Ordnung.
Bei manchen anderen Algorithmen (Du kennst bis jetzt eben nur Suchalgorithmen) hängt es aber nicht nur von der Größe des Arrays (also von n) ab, sondern auch von der grundlegenden Beschaffenheit der Eingabe-Daten. Und dann kann man eben u. U. eine spezielle Beschaffenheit der Daten feststellen, bei der der Algorithmus besonders schlecht funktioniert und dann besonders lange braucht, und andere, die besonders gut sind. Oft gibt es auch etwa nur wenige Fälle, bei denen es besonders schlecht ist, aber meistens geht es nahe dem "best-case", so dass average-case gleich dem best-case ist, aber trotzdem noch ein worst-case existiert, usw.
Gruß
Marco
|
|
|
28.04.2015 13:26 |
|
|
|
