Zeitkomplexität < Algorithmen < Schule < Informatik < Vorhilfe
|
| Aufgabe | Eine verkettete Liste enthält einen Zyklus, wenn man beginnend von einem Knoten p, den next-Zeigern folgt und wieder beim Knoten p ankommt. Die Liste habe n Knoten, wobei n nicht bekannt ist.
a. Beschreiben Sie einen Algorithmus mit der Zeitkomplexität O(n), welcher bestimmt ob eine verkettete Liste einen Zyklus enthält. Sie können O(n) extra Speicherplatz verwenden. |
Hallo, ich habe leider kein Ansatz bei dieser Aufgabe und würde mich über Tipps freuen.
Überlegungen:
es soll ein Algorithmus mit der Zeitkomplexität O(n) sein also Linear. Dieser Algorithmus hängt von der Anzahl der Rechenschritte ab. Zyklus einer verkettete Liste hängt von den Knoten(also Werten die in Speicherzellen gespeichert sind) aber ich komme trotzdem nicht auf die Lösung?
gruß capablanca
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:10 Mi 19.05.2010 | | Autor: | capablanca |
Hier habe ich eine Idee, ich weiss aber nicht ob ich die Frage so beantworte?
mit der Sprache Java
| 1: |
| | 2: | while(cursor.next!=null) {
| | 3: | //ein Zeiger wird kopiert um den Cursor nach rechts zu verschieben
| | 4: | cursor = cursor.next;
| | 5: | }//ende
|
so geht man die ganze Liste(Element nach Element) durch bis man das Ende der Liste erreicht hat.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:12 Fr 21.05.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
