Code-Schnipsel

Zitat:

Wenn man die Liste nur mit den Funktionen (welche Operationen darstellen) bearbeiten soll, sind natürlich hier keine Teillisten möglich.

Achso, Du meintest das anders. Ja nee, dann waren wir beide richtig

Ich ging einfach mal davon aus, dass es keine sinnvollen Operationen auf Listen mehr gibt, die nicht bereits in der Bibliothek enthalten sind... falls doch, so werden sie natürlich hinzugefügt.

Zitat:

Zitat:
Liste reversieren geht in O(n*log(n)), also verflucht schnell

Ist n die Anzahl der besuchten Elemente?
Wie kommst Du auf log(n)?

n ist immer die Größe der Eingabe, hier also die Länge der Liste.

Die Laufzeit ist O(n*log(n)), ich beweise das hier mal in "Prosa":

Der Algortihmus Mergesort (der bei mir zum Sortieren verwendet wird) ist ein Divide-and-Conquer-Verfahren. Beim Sortieren wird die Liste zunächst in zwei etwa gleichlange Teillisten zerlegt, diese werden sortiert und dann "gemergt", also sortiert zusammengefügt.

Offensichtlich ist dieses Verfahren der ideale Kandidat für Rekursion.

Das Zerlegen in Teillisten dauert maximal O(log(n)) Zeit (Eine Liste der Länge 1024 teile ich einmal, dann hab ich 2x512. Ich teile die beiden nochmal, dann hab ich 4x256, 8x128, 16x64, 32x32, 64x16, 128x8, 256x4, 512x2, 1024x1, das sind genau 10 Iterationen, und 10 = log(1024) zur Basis 2). Dann besitze ich also n Teillisten der Länge 1. Je zwei dieser Teillisten lassen sich in maximal O(n) Zeit zu einer Liste zusammenfügen (merge() dauert maximal O(n)). Das muss ich aber solange machen bis ich keine Teillisten mehr habe, also log(n) Mal.

Also ist die gesamte Laufzeit in der Klasse O(n*log(n)).

n ist die Länge der Liste, und so lange dauert ein merge()-Vorgang maximal.
Und mergen muss ich log(n) Mal.

Hoffe das reicht als Erklärung. Bei Google findet man unter dem Stichwort "Laufzeit Mergesort" aber noch jede Menge anderen Kram, insbesondere auch korrekte Beweise. Am besten hilft es, sich einfach ein Bild zu malen.

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Danke für die Erklärung .

 

broesel:

Du schreibst in deinen Funktionen

...
node *n = NULL;

...

if	((n = (node *)malloc(sizeof(node))) == NULL) {
...

und lässt node *n bei der Deklaration auf NULL zeigen - laut dem Buch "C von A-Z" Kapitel 8.2 also eine Definition.
Laut dem Buch "C von A-Z" Kapitel 17.2 gibt malloc() bei Erfolg die Anfangsadresse eines reservierten Speicherbereichs oder einen Zeiger auf NULL zurück.
Ist die Initialisierung mit NULL deshalb nicht überflüssig, ja sogar langsammer als wenn man den Zeiger nur deklariert würde?
Nur eine grundsätzliche Frage

Gruß,
Patrick-Oliver

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.

 

Zitat:

broesel:

Du schreibst in deinen Funktionen

...
node *n = NULL;

...

if	((n = (node *)malloc(sizeof(node))) == NULL) {
...

und lässt node *n bei der Deklaration auf NULL zeigen - laut dem Buch "C von A-Z" Kapitel 8.2 also eine Definition.

Auch

node *n;

ist eine Definition.

node *n = NULL;

Ist eine Initialisierung, die immer eine Definition implizieren.


Das solltest Du dir nochmal etwas genauer angucken .

@Jürgen
Ich will dir ja nichts unterstellen aber für mich sieht es so aus, als ob im folgenden Link jemand etwas abgeschrieben hätte:

Variablen deklarieren

Dies findet sich nämlich sehr ähnlich hier:

Unterschied: Deklaration, Definition, Initialisierung

Kann mich diesbezüglich jemand aufklären?

Zitat:

Laut dem Buch "C von A-Z" Kapitel 17.2 gibt malloc() bei Erfolg die Anfangsadresse eines reservierten Speicherbereichs oder einen Zeiger auf NULL zurück.
Ist die Initialisierung mit NULL deshalb nicht überflüssig, ja sogar langsammer als wenn man den Zeiger nur deklariert würde?
Nur eine grundsätzliche Frage

Du hast recht, die Initialisierung dieser Variablen ist langsamer als eine Definition aber es üblich und ich würde auch sagen guter Stil, einem Zeiger der bis jetzt keine gültige Adresse hat, den NULL-Zeiger zuzuordnen, damit dies auch überpüft werden kann, siehe dazu auch folgendes:

Die Mysterie von NULL

 

Ich möchte vorschlagen, den Namen der Funktion list_size in list_count zu ändern.
Eine zusätzliche list_size kann dann den gesammten Speicherbedarf der Liste ermitteln.

Gruß,
Patrick-Oliver

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.