Komplexität des Algorithmus, das ein Element in einer kreisförmigen verknüpften Liste am vorderen Ende einfügt
-
16-10-2019 - |
Frage
Wenn in einer kreisförmigen verknüpften Liste ein Element vorne eingefügt werden muss [kurz bevor der von Kopf gezeigte Knoten], kann er in O (1) durchgeführt werden (siehe Antwort hier)
Aber in einem Buch, das derzeit ich derzeit habe, wird erwähnt, dass es in O (n) (der üblichen Methode) erfolgt. Ich habe auch nur wenige Vorlesungs -PPTs gesehen, sie alle erwähnen die übliche Methode, um die Liste zu durchqueren und ein Element hinzuzufügen.
Meine Frage ist :
Welche Methode wird in praktischen Szenarien verwendet?
Ich bin kurz davor, an einer Prüfung teilzunehmen, die aus MCQs besteht, wenn oben gestellt wird, soll ich o (n) markieren, da dies die Standardantwort ist?
Lösung
Die in praktischen Szenarien verwendete Methode hängt vom Szenario (und vom Programmierer) ab. Es gibt mehrere mögliche Probleme, die die Auswahl der Implementierung beeinflussen:
- Ob der Algorithmus dem Programmierer bekannt ist.
- Einfache Codierung (es ist am einfachsten, wenn es bereits in einer Bibliothek implementiert ist, die Sie verwenden können).
- Geschwindigkeit - Das hängt davon ab, wie die Datenstruktur verwendet wird.
- Space Overhead von der Datenstruktur.
Ein intelligenter Programmierer sollte all dies berücksichtigen und versuchen, sich über verschiedene Algorithmen und Datenstrukturen zu informieren.