Ποιο είναι το επίπεδο χρονικής πολυπλοκότητας της λειτουργίας προσθήκης ενός στοιχείου στο τέλος ενός πίνακα χρησιμοποιώντας ένα slice;

Στη Go, η λειτουργία προσθήκης ενός στοιχείου στο τέλος ενός slice (append) έχει μια αθροιστική χρονική πολυπλοκότητα O(1).

Εξήγηση:

• Αν το slice έχει αρκετή χωρητικότητα (capacity), η προσθήκη ενός στοιχείου γίνεται απλά γράφοντας στη επόμενη ελεύθερη θέση — αυτή είναι μια λειτουργία σε σταθερό χρόνο.

• Αν η χωρητικότητα δεν είναι αρκετή, δεσμεύεται ένας νέος μεγαλύτερος πίνακας, αντιγράφονται τα παλιά στοιχεία και προστίθεται το νέο — αυτή η λειτουργία διαρκεί O(n), όπου n είναι το τρέχον μέγεθος του slice.

Ωστόσο, επειδή τέτοιες αναδιατάξεις δεν συμβαίνουν σε κάθε προσθήκη, αλλά μόνο περιοδικά, η μέση (αθροιστική) πολυπλοκότητα της προσθήκης παραμένει O(1).