Αποστολέας Θέμα: Πολυπλοκότητα της merge  (Αναγνώστηκε 488 φορές)

llort_x

  • Νέος
  • *
  • Μηνύματα: 3
Πολυπλοκότητα της merge
« στις: 27 Ιούλ 2019, 12:21:19 πμ »
...
Αν μπει Python και μαζί κάποια στοιχεία πολυπλοκότητας και λίγο αναδρομή τότε θα έχουμε φτιάξει ένα μάθημα το οποίο θα είναι αντίστοιχο με όλα τα εισαγωγικά μαθήματα προγραμματισμού πολλών θετικών σχολών (Το μαθηματικό κάνει Python!)
...
Συμφωνώ με τον evry.
Η πολυπλοκότητα πρέπει να μπει και στο ΓΕΛ και στο ΕΠΑΛ. Ίσως έτσι αποφευχθούν φαινόμενα όπως αυτό στη σελίδα 136 του βιβλίου Προγραμματισμού της Γ των ΕΠΑΛ, όπου αναφέρεται για τη λειτουργία της συγχώνευσης δυο ταξινομημένων λιστών ότι

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

και στη συνέχεια δίνεται μια υλοποίηση της συγχώνευσης δυο ταξινομημένων λιστών με πολυπλοκότητα Ο(nm).
« Τελευταία τροποποίηση: 27 Ιούλ 2019, 01:17:42 μμ από evry »

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Πολυπλοκότητα της merge
« Απάντηση #1 στις: 27 Ιούλ 2019, 09:50:27 πμ »
Δεν κατάλαβα τι εννοείς. Που ακριβώς είναι το πρόβλημα?
Μπορείς να εξηγήσεις γιατί η πολυπλοκότητα του αλγορίθμου είναι O(mn) όπως λες και όχι Ο(m+n)?

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

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

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

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


« Τελευταία τροποποίηση: 27 Ιούλ 2019, 01:18:07 μμ από evry »
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

llort_x

  • Νέος
  • *
  • Μηνύματα: 3
Πολυπλοκότητα της merge
« Απάντηση #2 στις: 27 Ιούλ 2019, 12:34:01 μμ »
Δεν κατάλαβα τι εννοείς. Που ακριβώς είναι το πρόβλημα?
Μπορείς να εξηγήσεις γιατί η πολυπλοκότητα του αλγορίθμου είναι O(mn) όπως λες και όχι Ο(m+n)?

Οι λειτουργίες pop και append έχουν Ο(1)
https://wiki.python.org/moin/TimeComplexity
Αν θέλεις κι έχεις χρόνο evry, μετάφερε το μήνυμά μου και την απάντησή σου σε ένα νήμα που θα αφορά στην πολυπλοκότητα της συγκεκριμένης υλοποίησης της merge, για να μπορεί να γίνει σχετική συζήτηση, και θα σου απαντήσω με την πρώτη ευκαιρία.
« Τελευταία τροποποίηση: 27 Ιούλ 2019, 01:18:34 μμ από evry »

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: Πολυπλοκότητα της merge
« Απάντηση #3 στις: 27 Ιούλ 2019, 01:19:16 μμ »
οκ, εδώ συνεχίζουμε τη συζήτηση για την πολυπλοκότητα της merge
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

llort_x

  • Νέος
  • *
  • Μηνύματα: 3
Απ: Πολυπλοκότητα της merge
« Απάντηση #4 στις: 28 Ιούλ 2019, 12:45:52 μμ »
οκ, εδώ συνεχίζουμε τη συζήτηση για την πολυπλοκότητα της merge
Ωραία!
Όποτε σου επιτρέψει ο χρόνος σου evry, αν θέλεις, τρέξε τα τρία προγράμματα στο συνημμένο και ανάρτησε εδώ την έξοδό τους, με τη σειρά που υποδηλώνει η αρίθμηση στο όνομά τους, δηλαδή πρώτα την έξοδο του 1_append, μετά του 2_pop_last και τελευταία την έξοδο του 3_pop_first.

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3145
  • to Iterate is human to Recurse divine
Απ: Πολυπλοκότητα της merge
« Απάντηση #5 στις: 28 Ιούλ 2019, 10:13:48 μμ »
Ναι έχεις δίκιο είναι 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