Wenn wir ein Array haben Anint s, und wir möchten die int bei A[n-1] löschen, wie würden wir das genau tun?Warum ist die Worst-Case-Komplexität des Löschens des letzten Elements in einem Array O (1) und nicht O (n)? /?
Mein Professor behauptet, dass die Worst-Case-Komplexität für diese Operation O(1) ist, aber ich bin verwirrt, wie man das Element "richtig" löscht. Ich persönlich würde nicht einfach 0 in A[n-1] schreiben, weil das technisch mit 0 überschrieben wird.
Meine Idee war, ein neues Array B mit n-1 Elementen zu erstellen und die ersten n-1 Elemente über von A kopieren, die eine Komplexität von O(n) schaffen würde, das Löschen zu vervollständigen, aber das ist offensichtlich nicht die richtige Antwort.
Kann jemand einen Einblick darauf geben?
Hängt davon ab, welche Begriffe von "array" und "delete" Sie verwenden. Bei klassischen Arrays gibt es keine Elemente zu löschen. – user2357112
Es wurde wahrscheinlich angenommen, dass das Array eine feste Größe hatte. In diesem Fall entspricht das "Löschen" des letzten Elements des Arrays dem Setzen des letzten Elements auf 0 usw. Wenn Ihr Array dynamisch skaliert ist (dh die Größe ändern kann) Kapazität braucht,) das ist ein anderes Problem. Da get/put-Operationen für Arrays fester Größe "O (1)" sind, ist die Anweisung "Löschen" des letzten Elements, das "O (1)" ist, in diesem Kontext korrekt. –
Wenn Ihre Elemente keine Primitive sind, können Sie A [n-1] = null; das würde nur etwas Speicher freigeben, aber das Array wird immer 'N' Elemente haben, was du initialisierst. – SomeDude