3. Komplexität von Funktionen in Vectoren/Listen

Komplexität von Funktionen in Vectoren/Listen

  • A

    Hallo,

    ich verstehe nicht, warum der Zugriff auf ein Element in einem Vector O(1) wohingegen dieser in der Liste O(n) ist. Ich meine in der Liste kann ich das schon nachvollziehen, weil man immer auf das nächste Element zugreifen muss bis man das gewünschte hat. Aber wie wird das denn anders bei einem sequenziellen Vector realisiert?? Wenn ich da auf das fünfte Element zugreifen will, muss doch intern auch ein Zeiger vom 0. Element des Vectors zum 5. Element des incrementiert werden bzw. vom 0. bis zum n-ten, wenn man das n-te Element des Vectors möchte, wäre nicht dann die Komplexität O(n)?

    Außerdem versteh ich die Darstellung einer mathematischen Menge als Bitvektor nicht: Sei M={2,5,7,1,9}, wie erzeuge ich daraus einen Bitvektor der nur bool Werte speichert? Dazu habe ich noch weitere Fragen, aber vielleicht klären diese sich, wenn ich verstanden habe, wie diese Darstellung funktioniert.

    Ich bedanke mich schon Mal im voraus :),

    MfG
    Ambitious

    0
  • S

    Wenn ich da auf das fünfte Element zugreifen will, muss doch intern auch ein Zeiger vom 0. Element des Vectors zum 5. Element des incrementiert werden bzw. vom 0. bis zum n-ten, wenn man das n-te Element des Vectors möchte, wäre nicht dann die Komplexität O(n)?

    std::vector speichert alle Elemente fortlaufend direkt hintereinander im Speicher. Daher reicht einfache Zeigerarithmetik, um einen Zeiger auf das n-te Element zu berechnen, genau wie bei echten Arrays.
    Sei arr der Zeiger auf das erste Element im Array, dann addierst du einfach n dazu und dereferenzierst. In Kurzform arr[n] . Und schon hast du ein lvalue das auf das n -te Element verweist. Und das ist natürlich von der Komplexität her unabhängig von n , daher: O(1)O(1).

    Außerdem versteh ich die Darstellung einer mathematischen Menge als Bitvektor nicht: Sei M={2,5,7,1,9}, wie erzeuge ich daraus einen Bitvektor der nur bool Werte speichert?

    Verstehe ich dich richtig, du möchtest alle diese Werte in dualer Darstellung (die einzelnen Bits also separat) speichern? Oder was genau...?

    0
  • A

    Danke dir für deine Antwort, hat mir geholfen(hätte ich eigentlich auch selbst draufkommen können mit der einfachen Zeigerdarstellung 🙄 )

    Zur zweit Sache: Nein, die Elemente sollen nicht bitweise dargestellt werden, sondern es gilt: b[i] == true <=> e(index i) isElement of M. Aber ich versteh nicht so ganz wie ich das verstehen soll? Und dann steht darauffolgend die Komplexität für einfügen, löschen, für die Funktion isMember, etc...
    Aber ich versteh nicht, wie mit Hilfe des Bitvektors mit der ebengenannten Definition eine mathematische Menge implementiert werden kann, die die Funktionen:
    new, insert, delete, isMember, union, intersect, enumerate(Umwandlung Menge->Liste) bietet.
    Und mein Beispiel bezog sich auf die Menge M={2,5,7,1,9}. Wie würde hier dann die konkrete Implementierung mittels Bitvektor aussehen?

    Hoffe, dass das etwas verständlicher war.

    0
  • K

    Sieht nach HA aus. Bitte poste doch den kompletten Text!

    0
  • A

    Nein, sind keine HA sonst würde ich ehrlich hier nicht fragen :). Bereite mich auf Klausur vor und bin dabei auf diese Zeilen gestoßen, die wortwörtlich so im Skript stehen. Außer das Beispiel mit der Menge M={2,5,7,1,9}, das hab ich mir selbst überlegt um das, was da erklärt wird, nachvollziehen zu können.
    Es ist jetzt nicht wichtig für die Klausur nur bin ich neugierig, was damit gemeint sein soll.

    0
  • ?
     

    vector<bool> bitvektor; //tadaaa
/*TODO: tu irgendwas, damit bitvector genug Speicher reserviert hat,
dass ich nicht auf nicht-existente Elemente zugreife
oder erweitere den vector dynamisch bei Bedarf (bitvektor.resize) */
//speichere Elemente 2 und 5
bitvector[2] = true;
bitvector[5] = true;
//lösche element 5
bitvector[5] = false; //prüfe, ob ich den vector jetzt verkleinern kann?
vector<bool> intersect(const vector<bool> &v1, const vector<bool> &v2){
    return v1 and v2; //TODO: irgendwie bitweises/elementweises 'und' auf die vectoren anwenden
}
//TODO: analog zu intersect für Vereinigen nur mit 'oder' statt 'und'
//wieso heißt das enumerate?
list<int> getListFromBoolVector(const vector<bool> &v){ //mein Name ist auch nicht viel besser
    list<int> l;
    for (size_t index = 0; index < v.size(); index++)
        if (v[index])
            l.fügeEin(index); //TODO: wie hieß das nochmal bei list?
    return l;
} //kann man schon fast so abgeben

/* TODO: Sag dem Prof/Lehrer, dass nächstes Mal zusätzlich die Aufgabe "Schätzen Sie die
Speicher- und Laufzeiteffizienz des bitvektors im Vergleich zur Liste ab. Ist eines immer besser
als das Andere oder ist es situationsabhängig. Erläutern Sie die Situationen,
in denen das Eine besser ist als das Andere, wenn zutreffend." stellen soll
*/ //Das ist wahrscheinlich eine blöde Idee, aber das solltest du für die Klausur beantworten können
    0
  • A

    Ahh danke für dein Beispiel.

    Das Problem war, dass ich nicht ganz genau im Skript gelesen habe, denn da steht dass die Komplexität bei Vereinigung O(N) (großes N und nicht kleines), was bedeutet, dass es von der maximalen Mächtigkeit(=N) abhängt und nicht von der Anzahl der Elemente(=n).

    Und wie gesagt eine Aufgabe gab es nicht dazu und die Komplexitäten sind alle aufgezählt, auch weiss ich wann man welches benutzen sollte, nur konnte ich mir das nicht ganz vorstellen, wie ich mit 4 elementen im bool bitvektor die 9 als Element der Menge darstellen sollte.

    Habs jetzt aber super verstanden, danke!

    0
Anmelden zum Antworten