Complexal Komplexität der sortierten Array

Question

Derzeit mache ich ein Projekt für meine Universität, wo ich bekannte Datenstrukturen (Array, Linked List, BST, etc.) implementieren und ich muss die Zeiten, die einige Operationen auf ihnen erfordern. Zum Beispiel war die erste für mich Array. Ich habe die Zeit für das Hinzufügen eines Elements in der Mitte eines Arrays gemessen (mit weiteren Werten von c, also n = n + 1. Es gab natürlich O(n), wobei n eine Anzahl von Elementen ist. Jetzt muss ich prüfen, ob ein Element hinzugefügt wird . zu Beginn des Array und ein Element, um es anhängt (Hinzufügen zu Ende) ich habe zwei einfache Algorithmen bekommt (ich nicht STL oder boost:: verwenden):

Hinzufügen zum Anfang:

void array::beginning_append(int value) 
{ 
    int *temp = new int[n + 1]; 
    memcpy(temp + 1, table, sizeof(int) * n); 
    n = n + 1; 
    temp[0] = value; 
    delete[] table; 
    table = new int[n]; 
    memcpy(table, temp, sizeof(int) * n); 
    delete[] temp; 
} 

Angehängt an das Ende:

void array::append(int value) 
{ 
    int *temp = new int[n + 1]; 
    memcpy(temp, table, sizeof(int) * n); 
    temp[n] = value; 
    n = n + 1; 
    delete[] table; 
    table = new int[n]; 
    memcpy(table, temp, sizeof(int) * n); 
    delete[] temp; 
} 

Das sind Methoden oder array Klasse, wobei table und n Mitglieder dieser Klasse sind. Jetzt unterscheiden sich diese nicht so sehr, ich dachte, dass ihre Zeiten gleich sein werden, und sie sind (ich überprüfte mit QueryPerformanceCounter für große Anzahl von Elementen, wie 500000, und es gab mir O(n) Komplexität), aber mein Dozent sagte, dass das Hinzufügen zu Beginn wird O(n) Rechenkomplexität haben, aber das Hinzufügen oder Entfernen eines Elements vom Ende wird eine Komplexität von O(1) haben, so dass es const sein wird, unabhängig von der Anzahl der Elemente. So würde Ich mag euch fragen, ob meine Algorithmen schlecht sind, ich meine, sie unnötigen Dinge zu tun, und das ist, warum sie auf der Anzahl der Elemente verlassen, oder mein Dozent war einfach falsch

Answer 1

Beiden Komplexitäten sind:

O (n)

weil Sie das gesamte Array kopieren.

Weitere Informationen zur Komplexität von memcpy()here.

---

Tipp: Sie können die zweite Kopie leicht überspringen, indem Sie die Speicherfreigabe table an zeigt, und dann macht es temp zu zeigen. Auf diese Weise kopieren Sie nur einmal, nicht zweimal. Die gesamte zeitliche Komplexität ändert sich jedoch nicht.

Beispiel:

void array::prepend(int value) 
{ 
    int *temp = new int[n + 1]; 
    memcpy(temp + 1, table, sizeof(int) * n); 
    n = n + 1; 
    temp[0] = value; 
    delete[] table; 
    table = temp; 
} 

---

Pro Tipp: How do you detect/avoid Memory leaks in your (Unmanaged) code?

_{Hunch: Eine geschickte Implementierung von realloc() ausführen soll schneller als ein Brute memcpy() in ein neues Array. Der Grund dafür ist, dass realloc() Ihr Array vergrößern/verkleinern kann, ohne das Ganze an einen neuen Ort kopieren zu müssen (was passieren kann, wenn es einfach nicht genug zusammenhängenden Platz gibt), dann wird es schneller. realloc() bedeutet nicht immer O (1).}

Answer 2

Das Hinzufügen zum Ende kann in O(1) erreicht werden, wenn der Puffer groß genug ist, um das neue Element zu halten. In der Regel wird bei einer Neuzuweisung die Speichergröße um mehr als das, was gerade benötigt wird, erhöht, um nicht zu oft Neuzuweisungen vornehmen zu müssen.

In diesem Fall hätten Sie eine durchschnittliche Komplexität von O(1) und eine ungünstigste Komplexität von O(n), wenn eine Neuzuweisung auftritt.