Πολυπλοκότητα της merge

Ξεκίνησε από llort_x, 27 Ιουλ 2019, 12:21:19 ΠΜ

« προηγούμενο - επόμενο »

llort_x

Παράθεση από: evry στις 26 Ιουλ 2019, 07:34:45 ΜΜ
...
Αν μπει Python και μαζί κάποια στοιχεία πολυπλοκότητας και λίγο αναδρομή τότε θα έχουμε φτιάξει ένα μάθημα το οποίο θα είναι αντίστοιχο με όλα τα εισαγωγικά μαθήματα προγραμματισμού πολλών θετικών σχολών (Το μαθηματικό κάνει Python!)
...
Συμφωνώ με τον evry.
Η πολυπλοκότητα πρέπει να μπει και στο ΓΕΛ και στο ΕΠΑΛ. Ίσως έτσι αποφευχθούν φαινόμενα όπως αυτό στη σελίδα 136 του βιβλίου Προγραμματισμού της Γ των ΕΠΑΛ, όπου αναφέρεται για τη λειτουργία της συγχώνευσης δυο ταξινομημένων λιστών ότι

"Ο αλγόριθμος αξιοποιεί το γεγονός ότι οι αρχικές λίστες είναι ήδη ταξινομημένες, ώστε να μη χρειαστεί να ταξινομήσει από την αρχή την τελική λίστα, κάτι το οποίο έχει σημαντικό υπολογιστικό κόστος για πολύ μεγάλες λίστες."

και στη συνέχεια δίνεται μια υλοποίηση της συγχώνευσης δυο ταξινομημένων λιστών με πολυπλοκότητα Ο(nm).

evry

#1
Δεν κατάλαβα τι εννοείς. Που ακριβώς είναι το πρόβλημα?
Μπορείς να εξηγήσεις γιατί η πολυπλοκότητα του αλγορίθμου είναι O(mn) όπως λες και όχι Ο(m+n)?

Οι λειτουργίες pop και append έχουν Ο(1)
https://wiki.python.org/moin/TimeComplexity

Παράθεση από: llort_x στις 27 Ιουλ 2019, 12:21:19 ΠΜ
Συμφωνώ με τον evry.
Η πολυπλοκότητα πρέπει να μπει και στο ΓΕΛ και στο ΕΠΑΛ. Ίσως έτσι αποφευχθούν φαινόμενα όπως αυτό στη σελίδα 136 του βιβλίου Προγραμματισμού της Γ των ΕΠΑΛ, όπου αναφέρεται για τη λειτουργία της συγχώνευσης δυο ταξινομημένων λιστών ότι

"Ο αλγόριθμος αξιοποιεί το γεγονός ότι οι αρχικές λίστες είναι ήδη ταξινομημένες, ώστε να μη χρειαστεί να ταξινομήσει από την αρχή την τελική λίστα, κάτι το οποίο έχει σημαντικό υπολογιστικό κόστος για πολύ μεγάλες λίστες."

και στη συνέχεια δίνεται μια υλοποίηση της συγχώνευσης δυο ταξινομημένων λιστών με πολυπλοκότητα Ο(nm).


What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

evry

οκ, εδώ συνεχίζουμε τη συζήτηση για την πολυπλοκότητα της merge
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

evry

Ναι έχεις δίκιο είναι O(mn) γιατί η πολυπλοκότητα της pop(0) είναι Ο(n) αφού η εσωτερική υλοποίηση της Python για την πράξη αυτή είναι να δημιουργήσει μια νέα λίστα και να αντιγράψει εκεί τα υπόλοιπα στοιχεία.
Μάλιστα η λειτουργία pop(0) σε μια λίστα Ν στοιχείων δεν είναι απλά Ο(Ν) αλλά Θ(Ν) !
Εγώ είχα στο μυαλό μου πολυπλοκότητα Ο(m+n) που είναι η κανονική πολυπλοκότητα της merge γιατί σκεφτόμουν ως κόστος μόνο τις συγκρίσεις.

Τώρα το ερώτημα είναι ότι τελικά ο τρόπος αυτός δεν είναι τόσο αποδοτικός όσο η κανονική συγχώνευση είναι όμως καλύτερος από την ταξινόμηση(bubble sort)? Τα assignments που έχουν πάνω κάτω πρέπει να είναι τα ίδια. Η διαφορά είναι ότι έχουμε πολύ λιγότερες συγκρίσεις από την bubble sort αλλά αντισταθμίζεται αυτό στην αντιγραφή της λίστας που γίνεται κάθε φορά? Νομίζω πως αντισταθμίζεται.
Ίσως αν το δοκιμάσετε αυτό πειραματικά να πάρετε μια απάντηση. Νομίζω έχει ενδιαφέρον.

Όσον αφορά τον λόγο που μπήκε αυτός ο κώδικας στο βιβλίο έχει το πλεονέκτημα ότι είναι ταυτόσημος με τον πραγματικό αλγόριθμο της συγχώνευσης που θα κάνει κάποιος στον πραγματικό κόσμο με αντικείμενα που θα έχει στη σειρά. Απλά θα αφαιρεί το πρώτο αντικείμενο και θα το μεταφέρει στη νέα λίστα. Διδακτικά δηλαδή νομίζω ότι είναι το καλύτερο που μπορεί να δείξει κάποιος γιατί μπορεί να το περιγράψει αρχικά με μια πολύ χαλαρή ψευδογλώσσα και να δώσει και μια καλή οπτικοποίηση. Επίσης γλιτώνεις από τους δείκτες i,j,k. Είσαι δηλαδή σε ένα πολύ υψηλότερο επίπεδο αλγοριθμικά. Νομίζω ότι το κόστος για την pop(0) αξίζει τον κόπο.
Επίσης από ότι είδα αν αλλάξουμε τη λίστα στη δομή deque που είναι στα collections τότε το pop(1) έχει πράγματι Ο(1) πολυπλοκότητα και όλα είναι οκ, αν μας ενδιαφέρει η απόδοση
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr