Αποστολέας Θέμα: Ερώτηση για την πολυπλοκότητα της ταξινόμησης φυσσαλίδας  (Αναγνώστηκε 2136 φορές)

georgia_kitsou

  • Οπαδός
  • **
  • Μηνύματα: 19

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

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

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

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

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

 
 

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Καλησπέρα σε όλους!  :)

 Θα ήθελα να ρωτήσω για το παράδειγμα 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

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2313
Πιο απλά, οι επαναλήψεις που απαιτούνται για την δυαδική αναζήτηση είναι ίσες με τον εκθέτη που πρέπει να υψωθεί το δυο για να ξεπεράσει τον αριθμό των στοιχείων του πίνακα

Δηλαδή
2 ^ χ > Ν
όπου χ είναι οι επαναλήψεις και Ν τα στοιχεία
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

Diotima

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

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

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

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

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

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

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

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

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

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

dpa2006

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 722
Θα συμφωνήσω με τους προλαλήσαντες,επίσης σελίδα 5 στο:
https://euclid.ee.duth.gr/courses/old/2011-12/DS/slides/DSAlg02%20sorting.pdf
Computer science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell.source:http://en.wikipedia.org/wiki/Computer_science

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Η πολυπλοκότητα της συγχώνευσης 2 ταξινομημένων πινάκων σε ταξινομημένο πίνακα ποια είναι;; :-[
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής

petrosp13

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 2313
O(n+m);
Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής

dski

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 202
O(n+m);

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

nikolasmer

  • Ομάδα Νέου Λυκείου
  • *
  • Μηνύματα: 564
  • There can be only one...may it be AEPP.
Έγινε...
Ευχαριστώ πολύ και τους δυο σας... :)
Απ' τα τσακάλια δεν γλυτώνεις μ'ευχές ή παρακάλια
(Κ. Βάρναλης)

Μερεντίτης Νικόλαος
Καθηγητής Πληροφορικής - Φροντιστής