Introduction to Algorithms and Programming

Εισαγωγή:Πολυπλοκότητα Αλγορίθμων

Υποθέστε ότι είστε ο Line Manager σε μία εταιρία πληροφορικής. Οι διάφοροι team leaders σας παρουσιάζουν τους ιδέες τους για το πώς να υλοποιηθεί το πρόγραμμα. Εσείς πρεπει να επιλέξετε την αποδοτικότερη πρόταση!  (Αποδοτικότερος είναι ο πιο γρήγορος αλγόριθμος. Αυτος που θα κάνει τις λιγότερες επαναλήψεις)

Η άσκηση ΔΕΝ  βαθμολογείται. 

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

Ερώτηση 1 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0 βαθμοί) 

Ερώτηση 1.

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

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

Ερώτηση 2 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0 βαθμοί) 

Ερώτηση 2.

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

Πρόταση 2: Ο αλγόριθμος προσπελάσει επανειλημμένα τη λίστα, συγκρίνει παρακείμενα στοιχεία και τα ανταλλάσσει αν είναι σε λάθος σειρά. Το πέρασμα μέσω της λίστας επαναλαμβάνεται έως ότου ταξινομηθεί η λίστα.

 

Ερώτηση 3 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0 βαθμοί) 

Ερώτηση 3.

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

Πρόταση 2:Ο αλγόριθμος προσπελάσει επανειλημμένα τη λίστα, συγκρίνει παρακείμενα στοιχεία και τα ανταλλάσσει αν είναι σε λάθος σειρά. Το πέρασμα μέσω της λίστας επαναλαμβάνεται έως ότου ταξινομηθεί η λίστα.

Ερώτηση 4 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0 βαθμοί) 

Ερώτηση 4.

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

 

Πρόταση 2:Ο αλγόριθμος προσπελάσει επανειλημμένα τη λίστα, συγκρίνει παρακείμενα στοιχεία και τα ανταλλάσσει αν είναι σε λάθος σειρά. Το πέρασμα μέσω της λίστας επαναλαμβάνεται έως ότου ταξινομηθεί η λίστα.

 

Ερώτηση 5 (Πολλαπλής Επιλογής (Μοναδική Απάντηση) — 0 βαθμοί) 

Ερώτηση 5.

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


Πρόταση 2: Λειτουργεί επιλέγοντας ένα στοιχείο άξονα από τη συστοιχία και χωρίζοντας τα άλλα στοιχεία σε δύο δευτερεύουσες συστοιχίες, ανάλογα με το αν είναι μικρότερα ή μεγαλύτερα από τον άξονα.Στη συνέχεια, οι υπο-σειρές ταξινομούνται με τον ίδιο τρόπο.