Ερώτηση για την πολυπλοκότητα της ταξινόμησης φυσσαλίδας

[georgia_kitsou]

Καλησπέρα σε όλους! 

Θα ήθελα να ρωτήσω για το παράδειγμα 3 σελ 47 του τετραδίου μαθητή, σε σχέση με την παράγραφο 5.3.1 σελ 97 του βιβλίου.
Καταρχάς, γιατί δίνει άλλη μορφή του αλγορίθμου από αυτή που μάθαμε στο κεφάλαιο 3 (όπου λέει Για j από n μέχρι 2 με βήμα -1);
Να υποθέσω ότι αυτό δεν έχει σημασία, επειδή σε κάθε περίπτωση ο εσωτερικός βρόχος του j θα κάνει n-1 επαναλήψεις, οπότε το δηλώνει ως Για j από 1 μέχρι n-1;

  Επίσης, κατανοώ ότι σε κάθε περίπτωση η πολυπλοκότητα του συγκεκριμένου αλγορίθμου είναι τετραγωνική, αλλά στο παράδειγμα του τετραδίου μαθητή δίνει σημασία τόσο στις συγκρίσεις όσο και στις ανταλλαγές των στοιχείων του πίνακα, ενώ στο βιβλίο μιλάει μόνο για συγκρίσεις. Τι θα πρέπει να πούμε εμείς;

Τέλος, η πολυπλοκότητα για τη δυαδική αναζήτηση O(logn) πώς προκύπτει;

  Συγγνώμη αν σας κούρασα και ευχαριστώ εκ των προτέρων!
 

[gpapargi]

Καλησπέρα σε όλους! 

Θα ήθελα να ρωτήσω για το παράδειγμα 3 σελ 47 του τετραδίου μαθητή, σε σχέση με την παράγραφο 5.3.1 σελ 97 του βιβλίου.
Καταρχάς, γιατί δίνει άλλη μορφή του αλγορίθμου από αυτή που μάθαμε στο κεφάλαιο 3 (όπου λέει Για j από n μέχρι 2 με βήμα -1);
Να υποθέσω ότι αυτό δεν έχει σημασία, επειδή σε κάθε περίπτωση ο εσωτερικός βρόχος του j θα κάνει n-1 επαναλήψεις, οπότε το δηλώνει ως Για j από 1 μέχρι n-1;

Γράφει αυτή την παραλλαγή της φυσαλίδας γιατί έχει εύκολο υπολογισμό πλήθους επαναλήψεων. Φυσικά κάνει πολλά περιττά βήματα αφού η σάρωση ανεβαίνει μέχρι πάνω δηλαδή μπαίνει και στο ήδη ταξινομημένο κομμάτι του πίνακα ενώ είναι γνωστό ότι δε θα συμβεί καμία αντιμετάθεση εκεί μέσα. Η «συνηθισμένη» στο μάθημα φυσαλίδα έχει μεταβλητό άκρο στο μέσα βρόχο οπότε για να κάνεις αλγεβρικό υπολογισμό της πολυπλοκότητας πρέπει να χρησιμοποιήσεις τον τύπο για το άθροισμα όρων αριθμητικής προόδου.

Επίσης, κατανοώ ότι σε κάθε περίπτωση η πολυπλοκότητα του συγκεκριμένου αλγορίθμου είναι τετραγωνική, αλλά στο παράδειγμα του τετραδίου μαθητή δίνει σημασία τόσο στις συγκρίσεις όσο και στις ανταλλαγές των στοιχείων του πίνακα, ενώ στο βιβλίο μιλάει μόνο για συγκρίσεις. Τι θα πρέπει να πούμε εμείς;

Είναι θέμα του τι θέλεις να μετρήσεις κάθε φορά.

Τέλος, η πολυπλοκότητα για τη δυαδική αναζήτηση O(logn) πώς προκύπτει;

Φαντάσου ένα πίνακα με 2^κ στοιχεία. Επειδή κάθε φορά περιορίζεις στο μισό το πλήθος των στοιχείων στο οποίο ψάχνεις, το πλήθος των στοιχείων στο οποίο ψάχνεις περιορίζεται διαδοχικά σε 2^(κ-1), 2^(κ-2) κλπ. Όταν γίνει 2^0=1 τελειώνουμε.  Άρα θέλει κ βήματα για 2^κ στοιχεία. Άρα η συνάρτηση πολυπλοκότητας που δίνει το πλήθος των επαναλήψεων σε συνάρτηση του πλήθους των στοιχείων του πίνακα είναι f(2^κ)=κ.
Επειδή θέλεις το f(ν) και όχι το f(2^ν) θέσε όπου κ το log(ν). Θα καταλήξεις σε f(ν)=log(ν) 

[petrosp13]

Πιο απλά, οι επαναλήψεις που απαιτούνται για την δυαδική αναζήτηση είναι ίσες με τον εκθέτη που πρέπει να υψωθεί το δυο για να ξεπεράσει τον αριθμό των στοιχείων του πίνακα

Δηλαδή
2 ^ χ > Ν
όπου χ είναι οι επαναλήψεις και Ν τα στοιχεία

[Diotima]

Επίσης, κατανοώ ότι σε κάθε περίπτωση η πολυπλοκότητα του συγκεκριμένου αλγορίθμου είναι τετραγωνική, αλλά στο παράδειγμα του τετραδίου μαθητή δίνει σημασία τόσο στις συγκρίσεις όσο και στις ανταλλαγές των στοιχείων του πίνακα, ενώ στο βιβλίο μιλάει μόνο για συγκρίσεις. Τι θα πρέπει να πούμε εμείς;

Συμφωνώ με τους συναδέλφους και θεωρώ σαφείς και πλήρεις τις απαντήσεις τους.
Θέλω να σχολιάσω λίγο παραπάνω την απάντηση στο συγκεκριμένο ερώτημα σου γιατί θεωρώ ότι το τετράδιο του μαθητή περιέχει κάπου ένα εκφραστικό λάθος που μπορεί να μπερδέψει κάποιον.

Κατ' αρχήν όταν πρόκειται να υπολογίσουμε την πολυπλοκότητα ενός αλγορίθμου που επιλύει ένα πρόβλημα, πρέπει να ορίσουμε εκτός από το μέγεθος του προβλήματος (που μπορεί να είναι μία ή περισσότερες μεταβλητές) και τη βασική ή τις βασικές πράξεις με τις οποίες θα γίνει η μέτρηση.

Εδώ το πρόβλημα είναι η ταξινόμηση n στοιχείων που επιλύει ένας δεδομένος αλγόριθμος φυσαλίδας και το μέγεθος του προβλήματος είναι το πλήθος n των στοιχείων που θα ταξινομηθούν. Μένει λοιπόν να ορίσουμε ποια (ή ποιες) θα είναι η βασική πράξη (ή οι βασικές πράξεις) με την οποία (τις οποίες) θα γίνει η μέτρηση.

Στην παράγραφο 5.3.1 το βιβλίο γράφει:
"Το πιο βασικό κριτήριο της επίδοσης μίας μεθόδου ταξινόμησης είναι ο αριθμός C, που μετρά τις απαιτούμενες συγκρίσεις κλειδιών (key comparisons), που εκτελούνται μέχρι να τελειώσει η ταξινόμηση. Ένα άλλο κριτήριο είναι ο αριθμός Μ που μετρά τις μετακινήσεις (moves) των στοιχείων. Οι αριθμοί C και Μ είναι συναρτήσεις του αριθμού n των στοιχείων, που πρέπει να ταξινομηθούν."

Μπορούμε λοιπόν να ορίσουμε ως βασική πράξη για τη μέτρηση τη σύγκριση δύο στοιχείων (να μετρήσουμε τον αριθμό όλων των συγκρίσεων που γίνονται), ή μπορούμε να ορίσουμε ως βασική πράξη την ανταλλαγή δύο στοιχείων (να μετρήσουμε το μέγιστο αριθμό αντιμεταθέσεων που μπορούν να γίνουν, γιατί ψάχνουμε για ελάχιστο άνω φράγμα, οπότε μετράμε τη χειρότερη περίπτωση) ή μπορούμε να επιλέξουμε και τα δύο.
Είναι καθαρά θέμα επιλογής.

Το τετράδιο του μαθητή στη σελ. 47 έχει εκφραστικό λάθος στην πρόταση:

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

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

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

Η μέτρηση και των δύο νομίζω δίνει μια καλύτερη εκτίμηση όταν συγκρίνονται ως προς την πολυπλοκότητα τους δύο αλγόριθμοι ταξινόμησης που ενώ έχουν την ίδια τάξη Ο(n²) έχουν διαφορετική συνάρτηση πολυπλοκότητας (ως προς αυτές τις πράξεις) και άρα διαφορετικό χρόνο εκτέλεσης. Π.χ. η ταξινόμηση με επιλογή κάνει τον ίδιο αριθμό συγκρίσεων με την κλασική φυσαλίδα, αλλά κάνει πολύ λιγότερες αντιμεταθέσεις, άρα είναι πιο γρήγορος αλγόριθμος.

[dpa2006]

Θα συμφωνήσω με τους προλαλήσαντες,επίσης σελίδα 5 στο:
https://euclid.ee.duth.gr/courses/old/2011-12/DS/slides/DSAlg02%20sorting.pdf

[nikolasmer]

Η πολυπλοκότητα της συγχώνευσης 2 ταξινομημένων πινάκων σε ταξινομημένο πίνακα ποια είναι;;

[petrosp13]

O(n+m);

[dski]

O(n+m);

Με πρόλαβες Πέτρο . Αν οι πίνακες έχουν n και m στοιχεία αντίστοιχα τότε είναι O(n+m). Νίκο, αν το σκεφτείς απλά, για τη συγχώνευση απαιτείται συνολικά ένα πέρασμα στα στοιχεία κάθε πίνακα.

[nikolasmer]

Έγινε...
Ευχαριστώ πολύ και τους δυο σας...