Λοιπόν, ξεκινώ τη σύγκριση των 2 αλγορίθμων από το θέμα της αποδοτικότητας που φαίνεται να συζητήθηκε περισσότερο.
Ο αλγόριθμος 2 διπλασιάζει τους ελέγχους και σε πρώτη φάση είναι πιο αργός. Αλλά ο τρόπος που τους αυξάνει (ο διπλασιασμός) δεν είναι τόσο κακός. Δηλαδή δεν αλλάζει την τάξη του αλγορίθμου. Ν ήταν και Ν παραμένει. Αν θυμάστε είχα ασκήσει βέτο στο θέμα της εύρεσης των 2 πρώτων από μια λίστα αριθμών επικαλούμενος την αύξηση των συγκρίσεων και άρα την έλλειψη αποδοτικότητας. Αλλά τότε άλλαζε η τάξη του αλγορίθμου από Ν σε Ν^2. Αυτό είναι κάτι πολύ διαφορετικό. Ο διπλασιασμός γίνεται πιο ανώδυνος αν λάβουμε υπόψην ότι σε ένα σχολικό πρόβλημα δε θα υπάρχουν και πολλές συνθήκες. Και 20 να είναι δε βλέπω μεγάλη διαφορά. Ενώ ένας αλγόριθμος εύρεσης 2 μεγαλύτερων έχει ακριβώς την ίδια μορφή ακόμα κι αν πρέπει να ψάξει 1000000 αριθμούς.
Υπάρχουν όμως και περιπτώσεις που ο αλγόριθμος 2 μπορεί να γίνει πιο γρήγορος από τον αλγ1. Ο αλγόριθμος 2 έχει ένα πλεονέκτημα: μπορεί να αλλάξει τη σειρά των ελέγχων. Αν έχουμε την πληροφορία ότι σε κάποιο διάστημα κάπου στη μέση είναι η μεγάλη πλειοψηφία των δειγμάτων μας τότε βολευει να βάλουμε τα συχνά διαστήματα στην αρχή έτσι ώστε η πολλαπλή επιλογή να αποφασίζει με λίγους ελέγχους. Για παράδειγμα ας υποθέσουμε ότι πρέπει να ελέγξουμε το iq μιας ολόκληρης χώρας που παίρνει τιμές από 0 ως 160 και να το κατατάξουμε σε κατηγορίας (διαστήματα πλάτους 5). Έχουμε 32 διαστήματα. Έχουμε επίσης την πληροφορία ότι οι τιμές συσσωρεύονται γύρω από το 80 (κατανομή Gauss με μέση τιμή 80). Έτσι μας βολεύει να βάλουμε τα διαστήματα γύρω από το 80 ψηλά στην πολαπλή επιλογή και όσο κατεβαίνουμε να απομακρυνόμαστε από το 80. Οι τελευταίοι έλεγχοι θα είναι για τα σπάνια διαστήματα [0,5] και [155, 160].
Εδώ ο αλγ 2 αποκτάει σημαντικό πλεονέκτημα στην ταχύτητα.
Υπάρχουν όμως και μερικές περιπτώσεις που ο αλγ 1 μπορεί κυριολεκτικά να εκτοξεύσει την ταχύτητα. Αν τα άκρα των διαστημάτων είναι κατάλληλα μπορεί η πολλαπλή επιλογή να υλοποιήσει μια διαδική αναζήτηση στέλνοντας την τάξη του αλγόριθμου στο λογ(Ν). Δεν το σχολιάζω αυτό παραπάνω γιατί θεωρώ ότι είναι έξω από τη μορφή που έχει το μάθημα σήμερα.
Στην παραγωγή ευανάγνωστου αλγορίθμου ο αλγ 2 είναι καλύτερος. Ο λόγος είναι ότι επειδή τα άκρα των διαστημάτων είναι σαφή, μπορούμε βλέποντας τη συνθήκη να καταλάβουμε σε ποιο διάστημα αναφέρεται. Αντίθετα στον αλγ 1 χρειάζεται να δεις και τις προηγούμενες συνθήκες για να καταλάβεις ποιο διάστημα καλύπτει ο συγκεκριμένος έλεγχος. Έτσι μπορεί να χρειάζεται να ανατρέξεις σε προηγούμενη σελίδα κάτι που κάνει τον αλγόριθμο πιο δυσανάγνωστο.
Στην ευκολία εκμάθησης πάλι νομίζω ότι ο αλγ 2 είναι καλύτερος λόγω του ότι είναι πιο ευανάγνωστος και έχει σαφή άκρα. Ο μαθητής βλέπει έναν έλεγχο και αμέσως καταλαβαίνει το διάστημα στο οποίο αναφέρεται.
Στη δυνατότητα χρήσης σε πολύπλοκα προγράμματα τα πράγματα είναι μπερδεμένα. Σε καταστάσεις που τα διαστήματα είναι διατεταγμένα μπορεί ο αλγ 1 να δώσει πιο συμπαγη κώδικα. Κλασσικό περίπτωση είναι στο κεφάλαιο 8 του τετραδίου το παράδειγμα 1 (με τους ρύπους). Για να το λύσεις αυτό με σαφή άκρα πρέπει να κατατάξεις μια κατάσταση ανάλογα με το ρύπο που οδηγεί στο χειρότερο στάδιο.
Πχ για στάδιο λήψης μέτρων Α βαθμίδας η συνθήκη είναι
Αν (ΝΟ2 >500 και ΝΟ2<700 και Ο3 <500) ή (Ο3>300 και Ο3<500 και ΝΟ2<700)
Μπέρδεμα! Αλλά από την άλλη μεριά αν ξέρεις να δίνεις σαφή άκρα παίζοντας με τις συνθήκες μπορείς να λύσεις τα πάντα.
Νομίζω ότι κάθε τεχνική έχει δικό της πεδίο εφαρμογής. Σαν κανόνα όμως θα έλεγα ότι στο χαμηλό επίπεδο του μαθήματος ψηφίζω τον αλγόριθμο 2 γιατί δίνει πιο ευανάγνωστο κώδικα και μικραίνει την πιθανότητα λάθους θυσιάζοντας σε ανεκτό σημείο την ταχύτητα (δεν αλλάζει την τάξη). Νομίζω ότι απαντώ και στο ιδιαίτερα εύστοχο ερώτημα του συνωνόματου George που ρώτησε «πόσο λάθος είναι ο έλεγχος περιττών συνθηκών σε ένα αλγόριθμο». Η απάντηση μου είναι: κυρίως αν δεν αλλάζει η τάξη του αλγορίθμου και δευτερευόντως αν τα δεδομένα δεν είναι πολλά (πχ 20 το πολύ έλεγχοι στο σχολικο μάθημα) επιλέγουμε ευκολία στην εκμάθηση.
Σε πιο προχωρημένο επίπεδο νομιζω ότι διαλέγουμε το πιο γρήγορο, που σημαίνει διαδική αναζήτηση (αν γίνεται), συνυπολογισμό της πιθανότητας να είσαι σε κάποιο διάστημα κλπ
Νομίζω μίλησα αντικειμενικά. Μπορούμε να κουβεντιάσουμε οτιδήποτε.
Φιλικά
