Μάθημα 5 (Μέρος A) / Μέθοδος «Διαίρει και Βασίλευε» και Εφαρμογές της
Μέθοδος «Διαίρει και Βασίλευε» και Εφαρμογές της: Παιδιά καλημέρα σας σήμερα αφού να ξεκινήσουμε να δούμε την επαναλαμβάνω σήμερα θα ξεκινήσουμε να δούμε τι προτιμάς αλγόριθμοι και τεχνική η οποία είναι ονομαστή διαίρει και βασίλευε λοιπόν επαναλαμβάνω σήμερα θα δούμε τι προτιμάς αλγόριθμοι και τεχν...
| Κύριος δημιουργός: | |
|---|---|
| Γλώσσα: | el |
| Φορέας: | Πανεπιστήμιο Πατρών |
| Μορφή: | Video |
| Είδος: | Ανοικτά μαθήματα |
| Συλλογή: | Τμήμα Mηχανικών Η/Υ & Πληροφορικής / Εισαγωγή στους Αλγόριθμους |
| Ημερομηνία έκδοσης: |
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ
2014
|
| Θέματα: | |
| Άδεια Χρήσης: | Αναφορά-Μη-Εμπορική Χρήση-Όχι Παράγωγο Έργο |
| Διαθέσιμο Online: | http://delos.upatras.gr/opendelos/videolecture/show?rid=7cdc5b2a |
| Μέθοδος «Διαίρει και Βασίλευε» και Εφαρμογές της: Παιδιά καλημέρα σας σήμερα αφού να ξεκινήσουμε να δούμε την επαναλαμβάνω σήμερα θα ξεκινήσουμε να δούμε τι προτιμάς αλγόριθμοι και τεχνική η οποία είναι ονομαστή διαίρει και βασίλευε λοιπόν επαναλαμβάνω σήμερα θα δούμε τι προτιμάς αλγόριθμοι και τεχνική η οποία ονομάζεται για σας το λέω κι φορέα που ονομάζεται διαίρει και βασίλευε είναι ένα τεχνική ώρα που είναι αρκετά παλιά ξέρει κανείς πότε πρωτοεμφανίστηκε από την ρωμαϊκή εποχή ωραία το το ξέρετε αυτό αυτός ήταν κυρίως την πρώτη εφάρμοσε έτσι ο ιούλιος καίσαρας ήταν ένα από τις 9 από τις προσφιλές του πρακτικές πολεμικές τακτικές η διαίρεση του αντιπάλου στρατεύματος δύο μισά περίπου και μετά οι επιθέσεις το ένα μισό με ολόκληρο το στράτευμα έτσι ώστε να μεγιστοποιήσει τις πιθανότητες επιτυχίας βέβαια όλα αυτά ισχύουν εκτός από το γνωστό μικρό χωριό που αντιστέκεται ακόμα λαιμό οι αλγόριθμοι και τεχνική λοιπόν βασική τεχνική διαίρει και βασίλευε κάνει το εξής διασπά την είσοδο σε διάφορα τμήματα μικρότερου μεγέθους το πλήθος των τμημάτων εξαρτάται από τη συγκεκριμένη εφαρμογή δεν απαντά καθορισμένο το δεύτερο βήμα είναι να επιλύσουμε το αρχικό πρόβλημα σε κάθε ένα από τα τμήματα αυτά καλώντας τον αλγόριθμο όμως με έναν ειρωνικό τρόπο κάνοντας δηλαδή τον ίδιο αλγόριθμο αλλά σε μικρότερη είσοδο και το τρίτο βήμα είναι να συνδυάσουμε τις επιμέρους λύσεις των προβλημάτων των προ του αρχικού δηλαδή προβλήματος το οποίο εφαρμόζεται σε μικρότερο μέγεθος εισόδου έτσι ώστε να έχουμε μια συνολική λύση για το αρχικό μας πρόβλημα αυτή τη βασική ιδέα θα δούμε παραδείγματα της τεχνικής αυτής προκειμένου να την καταλάβετε κύρια εφαρμογή ένα από τις κύριες εφαρμογές είναι το πρόβλημα της ταξινόμησής στοιχείων συνήθως ο τρόπος εδώ εφαρμογής της μεθόδου αυτής είναι η διαίρεση του αρχικού προβλήματος σε δύο τμήματα περίπου ίσου μεγέθους μ δευτέρα ωραία αντώνη φυσικά ένα άρτιο σαν την περίπτωσή του ενώ έχει μια δευτέρα σινεμά κ.α. την δευτέρα και ρωμαίος ωραία αλλά δεν έχει σημασία αυτό το συν ένα στοιχείο που μπορεί να είναι η διαφορά στο μέγεθος των προβλημάτων μετά επιλύουμε αναδρομικά κάθε πρόβλημα στα δύο μισά στο οποίο διάσπασης με το αρχικό πρόβλημα και μετά συνδυάζουμε τις δύο λύσεις μια συνολική λύση σε γραμμικό χρόνο αυτό δεν προφανές όπως γίνεται θα το συζητήσουμε γιατί είναι σημαντική η εφαρμογή της τις ταξινομήσεις γιατί γιατί άρα μπορούμε να ταξινομήσουν με σε βέλτιστο χρόνο με την εφαρμογή αυτής της τεχνικής και όχι μόνο υπάρχουν και άλλες τεχνικές και όχι να κάνουμε την εφαρμογή και να απομονώσουμε εφαρμογή της πλοκής μεθόδου που ονομάζεται σας ενόσω δηλαδή ταξινομεί σημαίνει ύφεση η οποία προβαίνει χρόνου είναι τραγανό αυτό θα το δούμε σήμερα γιατί η λειτουργία αυτή διαίρει και βασίλευε με απλό τρόπο το ονομάζετε Emerson 1000 ταξινόμηση με συγχώνευση έχει έναν άσημο τοπικό αριθμό στοιχείων των πράξεων Μηλιώνη όπου ν O αριθμός των στοιχείων της εισόδου μπορεί κάποιος να μου πει γιατί η απλοϊκή μέθοδος ταξινομήσεις παίρνει χοντρά το έχουμε αναφέρει σε προηγούμενο μάθημα να πολύ ωραία σας είπα και πριν λίγο πιο εύκολος τρόπος να ταξινομήσει δεν ξέρεις κάνετε μια σάρωση γραμμική σάρωσε είδαμε και έναν αλγόριθμο εύρεσης μέγιστη ο οποίος με ένα τετριμμένη τροποποίηση γίνεται αλγόριθμος εύρεσης ελάχιστοι εκτελείται τον αλγόριθμο δεν παίρνει γραμμικό χρόνο σαρώνει δηλαδή την είσοδο έκαναν συγκρίσεις αποφασίζει ποιο είναι το πρώτο στοιχείο αυτό είναι το πρώτο σας στοιχείο στην ταξινομημένες έξω ωραία με ταχύτατες και αφαιρείται από την την είσοδο μετά κοιτάτε τα υπόλοιπα στοιχεία το μικρότερο από τα υπόλοιπα λυπημένα το βάζετε Δευτέρα ωραία μεταδίδονται τα υπόλοιπα είναι πλέον δύο στοιχεία το μικρότερο από αυτά των βάζετε τρίτο και ούτω καθεξής αυτό χοντρικά η ανάλυση του βορρά να Night να δοθεί κατά δύο τρόπους οικονομική ανάλυση λέει ότι εγώ σαρώνουν στοιχεία και μπισκότο μικρότερο κάθε φορά για να κάνω μια παραλείψεις δυστυχία στη χειρότερη περίπτωση την επόμενη φάνηκαν νάνοι πλην δύο κλπ άρα έχω χρόνο μιας σάρωσης για να βρω το ελάχιστο μηνιαίο ο κεφάλαιο του ν επί ένα επανάληψη της μας κάνει ο τετράγωνος ωραία που άλλος τρόπος να το Δείτε αυτό είναι επειδή κάποιος μπορεί να πει μα την πρώτη φορά κάνω νησίδες στην επόμενη κανονιών να συμπληρώσεις την επομένη θα κανονίζουν ποιος βρισκόταν σε έναν έτσι αυτός αριθμός των πράξεων των συγκρίσεων μέχρι να αποφασίσω κάθε φορά κάποιον το μικρότερο στοιχείο αυτό πάλι είναι αριθμητική πρόοδος που ξέρετε ότι είναι κλείνει συγνώμη επιμένει σε ένα διαδήλωση του οποίου είναι και πάλι σαν σε συλλογικό συμβολισμό τάξη μεγέθους είναι πράγμα ωραία όπως λοιπόν για να μετρήσετε αυτές απλοϊκός τρόπος ταξινομήσεις θα μας πάρει χρόνο ανάλογο του Δραγούμη το πλήθος των στοιχείων όπως εξήγησαν στο πρώτο μάθημα έτσι διάφορα δεν μπορώ με τεράστια όταν τον είπαν οι φήμες μεγάλο μας εκατομμύρια στοιχεία 10000000 στοιχεία κλπ αλλά εφαρμογή υπάρχουν πάρα πολλές εφαρμογές ταξινόμησης οι οποίοι είναι προφανής ετσι θέλουμε να δούμε τους να ταξινομήσουν με καταν αριθμό λογαριασμού τους τραπεζικούς λογαριασμούς είναι ταξινομήσουν το τηλεφωνικό κατάλογο κατά αλφαβητική σειρά υπάρχουνε πολλές μη προφανείς εφαρμογές που αφορούν σε αποσυμπίεση δεδομένων και γραφικά υπολογιστών μέχρι προτάσεις βιβλίων στο Amazon φορέα και υπάρχουν πάρα πολλά προβλήματα που γίνονται πιο εύκολα μετά από ταξινόμηση είδαμε ένα τέτοιο πρόβλημα έτσι οι αναζητήσεις ένα απαξιωμένο πείνα με την λεγόμενη διάδικοι αναζήτηση μπορούμε πάρα πολύ εύκολα εφόσον είσοδος είναι ταξινομημένα να δούμε το στοιχείο του ελάχιστου τους ίδιους αγνό μάλλον ψαρά ο χρόνος σαρώνοντας τα άλλα αλλά σε λογαριασμό ΥΚΩ χρόνο πουλιά εξωτικά μικρότερος από τον γραμμικό χρόνο ακριβώς γι αυτό το λόγο επειδή ταξινόμηση είναι μια πάρα πολύ ένα πολύ βασικό πρόβλημα σε μια πληθώρα εφαρμογών θα τη δούμε διεξοδικά στο σημερινό μάθημα με εφαρμογή της μεθόδου διαίρει και βασίλευε και συγκεκριμένα θα δούμε τον αλγόριθμο μελισσοκόμος είχε επικρατήσει στα αγγλικά ο οποίος προτού ανακαλύφθηκε από τον κο τόπου βλέπετε τον έχουμε ξαναδεί που ουσιαστικά άφθονο αίμα θυμίζω ότι διαμόρφωσε την πρώτη αρχιτεκτονική του υπολογιστή μέχρι τη την εμφάνιση των πολύ πύρινων επεξεργαστών έχουμε έναν ένα CPU ένα κεντρική μονάδα επεξεργασίας ένα μνήμη και καταχωρείται στο λήγουν οποιοσδήποτε εξίσου τυπικά ότι θέλουμε να κάνουμε α αριθμητική ταξινόμηση και έχουμε μια ακολουθία από χαρακτήρες αυτό που κάνουμε είναι διαιρούμενη στη μέση βιώνουν μάλλον παίρνουμε το αρχικό πίνακα δεν κύλησαν και την κόβουμε στη μέση και έχουμε λοιπόν δύο μισά εφαρμόζουμε αναδρομικά στα δύο μισά τον αλγόριθμο και μετά κάνουμε συγχώνευση τα βάζουν μαζί αυτή είναι η βασική ιδέα του αλγόριθμου πως κάνουμε συγχωνεύσεων του έχετε δει αυτό αλλά θα το ξαναδούμε αν χρησιμοποιούμε αυτό που κάνουμε να χρησιμοποιούμε έναν προσωρινό πίνακα και κάθε φορά κοιτάμε από τις από τα δύο τμήματα στα οποία διαίρεσε το αρχικό πρόβλημα το πρώτο τα πρώτα στοιχεία τα οποία δεν έχουμε ακόμα δει και τα συγκρίνουμε ωραία πως γίνεται αυτό γίνεται ως εξής αρχικά είπαμε έχουμε δύο δείκτες το μπλε διεκδικεί το πράσινο δίκτυο μπλε είναι στο αριστερό τμήμα πιο πράσινος τεχνικά στοιχεία του δεξιού τμήματος από τα δύο στα οποία έχουμε διαιρέσει το δικό μας πρόβλημα ωραία και κοιτάμε του ελάχιστα ποιο είναι το ελάχιστο από τα δύο το ελάχιστο α αριθμητικά είναι το έχει το λέει λοιπόν μπαίνει ως πρώτος το πολιτικό πυρήνα μετά απαντά εφ' όσον το ελάχιστο προήλθε από το αριστερό πίνακα που πυροδοτείται από τον μπλε δίχτυ τότε ο δείκτης αυτός μετακινείται ένα θέση δεξιότερα το στοιχείο αυτό το έχουμε δει ώρα και γίνεται πάλι σύγκριση του στοιχείου μου τέχνη μπλε χρήματα στο αρχείο μου τέχνη ο πράσινος δείκτης τονίζει με το ICS των μικρότερων που είναι το και το μέτρο του GPS μεταξύ τους γιατί έτσι κατεβαίνει το τζελ λοιπόν είναι μικρότερο από το τέξας αριθμητικά κατεβαίνει λοιπόν κατασκοπευτικό πίνακα και τώρα θα μετατοπιστεί ο δείκτης αυτός μια θέση δεξιότερα και θα συγκριθεί τώρα το νέο στοιχείο είναι με το HTC το μικρότερο από τα δύο έχουνε στην περίπτωση αυτή πιο συγνώμη το Ladies παραμένει κάτω και θα μετακινηθεί ο πράσινος δείκτης ένα θέση δεξιότερα φορέα έχουμε λοιπόν τώρα το ΕΛΜΕ το ΑΕΙ πιόνι των μικρότερων αριθμητικά από το δύο κατεβαίνει κάτω μετακινείται ένα θέση ψηλότερα ο κόσμος δυστυχώς μετά έχουμε το έλεγε με το με το μη πρόεδρε είναι α αριθμητικά μικρότερο κατεβαίνει και αυτό κάποτε θα μετακινηθεί μπλε δείκτης ένα θέση δεξιότερα και έχουμε τώρα τη σύγκληση του στοιχείου κόβουμε το στοιχείο κάνουμε το στοιχείο ενώ θα κατέβει για να πάρει θετικά μικρότερο από το οποίο θα μετακινηθεί ο ίδιος δείκτης μια θέση δεξιότερα και μετά έχουμε μου τη σύγκρισή του με το ένα το όπου είναι ο είναι μικρότερο θα κατέβει κάτω θα μετακινηθεί μπλε δείκτης ένα θέση δεξιότερα έχουμε σύγκριση τώρα του Νέου στοιχείου άρα με το εις το και τον άρη είναι μικρότερο και θα κατέβει εξαντλήσαμε το πρώτο μισό του μένος αυτό που κάνουν είναι απλά αντιγράφουμε τα υπόλοιπα στοιχεία που εξαντλήθηκε το πρώτο ίσως το δεύτερο μισό στο βοηθητικό παρά πίνακα νέα αυτός είναι ο αλγόριθμος της συγχωνεύσεις οι μέρες στα αγγλικά και υπάρχει και ένα τρόπος από ταυτοχρόνως άσκηση χωρίς βοηθητικό στην αγορά με χρησιμοποιώντας μόνο ένα πολύ μικρό πολύ μικρή εξτρά μνήμη αυτό που θέλω να καταλάβετε και να θυμάστε είναι ότι στη γενική περίπτωση αυτός συνολικός αριθμός χωριά που έχουμε λοιπόν δύο ταξινομημένες λίστες καταξιωμένων πεινασμένοι στοιχείο καθένας και αυτό που κάνουμε είναι έχουμε τους δύο δείκτες ΑΕΙ είναι μπλε δείκτης ο Jay πράσινους δείκτες στο παράδειγμά μας και ενώ το α είναι μικρότερο ίσως από το vintage η κάνουμε προσάρτηση του μικρότερου γιου του α στην περίπτωση αυτή στη λίστα εξόδους στο βοηθητικό του πίνακα και μεταθέτουν το μπλε δείκτη κατά ένα δεξιό που σημαίνει αυξάνουμε το I κατά ένα μονάδα παλαιός το αφού αν το vintage είναι το μικρότερο τότε προσθέτουμε το β τζέι στον πίνακα εξόδου και έχουμε το πράσινο δείχνει να αυξάνει κατά ένα σήμερα εισόδου εξαντληθούν τα στοιχεία και προστάτου με τα υπόλοιπα στοιχεία της ένα διεθνής τόσο στην έξω που αλγορίθμους αυτούς για συγχώνευση των δύο ληστών με γιατρούς ν η κάθε ένα γίνεται σε χρόνο ο κεφάλαιο του ν δηλαδή εκτελεί ένα γραμμικό αριθμό από στοιχειώδεις μπορεί κάποιος να μου πει γιατί να με δεν έχουμε δεσμευτεί να αναμένουνε δες πείραζε ετών ο κεφάλαιο έτσι υποκρύπτει μια σταθερά κλπ παιδιά δεν είναι δύσκολο να να βρείτε την πολυπλοκότητα του αλγόριθμου και θα πρέπει να εξασκείται σε αυτό βέβαια αλλιώς θα συναντήσετε δυσκολίες όχι μόνο σε αυτό το μάθημα και αργότερα σε πολλά μαθήματα καταρχήν υπάρχει μια αρχή κοπής των δύο δεικτών έτσι του δείκτη IQ του DJ είναι μια πράξη καταχώρισης δύο πράξεις δηλαδή αρχικά έχουμε αυτή αρχικό ποίηση πριν ταχύτερο χρόνο μετά έχουμε ένα βρόγχο Wine φορέων ο δρόμος αυτός αποτελεί έχει μια εντολή η ντον ελις έχουμε να δούμε πως θα παραλείψει να κάνει βρόχος βάιλ και πόσο χρόνο μας παίρνει κάθε επανάληψη συμφωνούμε να ξέρουμε πόσο χρόνο περνούν κάθε επανάληψη και πόσο πόσοι επαναλήψεις κάνουμε έναν πολλαπλασιασμό που έμαθε το δημοτικό και βρίσκουμε τις το χρόνο εκτέλεσης του αλγόριθμου ρε πάμε να δούμε η εντολή η δανή Hellas εδώ πόσο χρόνο περνούν έχω ένα σύγκριση ωραία και από τη στιγμή που έχω τη σύγκριση και αποφάσεις αν το α και το β τζέι και το μικρότερο από τα δύο και εκτελείται το κομμάτι δεν γίνονται κομμάτι ένα αυτό που κάνει είναι όπως λέει και το παράδειγμα είτε πρόσθετο στοιχείο σε μια λίστα η αντιγράφων στοιχείο να πεινάνε το προσάρτηση λοιπόν του α I κάπου σημαίνει είτε αν η λίστα να προσθέσω στο τέλος της λίστας ενημερώνοντας ένα σταθερό αριθμό από χτες έχουμε και δεν το έχουμε δει αυτό προσθήκη στοιχείων στη λίστα η αντιγραφή ένα στοιχείου σε ένα θέση ένα πίνακα πάλι είναι ένα πράξη καταχώρισης επομένως έχουμε εδώ ένα σύγκριση και έναν σταθερό ρυθμό από πράξη πάλι είτε στη ένα είτε στην άλλη περίπτωση φορέα δηλαδή η εντολή ήταν ένα ευρώ παίρνει έτσι έχουμε λοιπόν το βρόχο wine και που χρόνος κτήσης ήρθε ελιές είναι σταθερός αυτό που μας ενδιαφέρει είναι πως ο αριθμός των επαναλήψεων του βρόχου wine φορέα είναι κανείς που δεν καταλαβαίνει γιατί αυτή η εντολή δεν σπέρνει σταθερό χρόνο σταθερός σημαίνει ο του ένα σημαίνει μια σταθερά έτσι πέντε 10 δεν έχει σημασία αλλά μια σταθερά έχουν ανεξάρτητη τόσο συμβολισμός σημαίνει ανεξάρτητο το κόστος αλγόριθμοι κόστος σε χρόνο συγκεκριμένη περίπτωση από το μέγεθος της εισόδου ωραία οποιαδήποτε έκαναν είσοδος εδώ θα κάνουμε πέντε πράξεις ωραία υπερείσπραξη σήμερα πράξεις λέω επαναλάμβανε κανείς δεν καταλαβαίνει γιατί αυτή η εντολή δεν άλις παίρνει σταθερό χρόνο τώρα μπορεί κανείς να μου πει ποιος είναι ο αριθμός των παραλείψεων πόσες επαναλήψεις κάνε αυτό ΣΒΒΕ έτσι λέει θα τελεστεί μέχρις ότου και οι δύο ληστές δεν καίνε Mark εκτελείτε όσο και οι δύο ληστές δεν εκανες που σημαίνει ότι μόλις μιχάλης θα γίνει κενή σταματάει χώρο η εκτέλεση του βρόχου αλ παρακαλώ θα κάνει επαναλήψεις συμφωνείτε να λοιπόν κοιτάξτε τι ο βρόχος του α κάνει θα κάνει έτσι όπως συνετό γραμμένο δηλαδή όταν μια λύση θα γίνει κενή μόνες επειδή όμως μπορεί να γίνει και θα κάνει το πολύ δύο μη επανάληψης στοιχείων γιατί γιατί κάθε φορά γίνεται μια σύγκριση φορέα και κάθε φορά στο μέτωπο μετά από τη σύγκριση με βέβαια που όπως μετράμε πόσα παράλειψη κάνει μετά μετά από κάθε επανάληψη το αποτέλεσμα μάλλον καφές κάθε επανάληψης πρόσφατα κάποιο στοιχείο είναι το α και το β δεν στυλίστα έξω ωραία μετά από κάθε επανάληψη επομένως άνευ μετρήσω πόσα στοιχεία γράφουν έτσι εκτυπώνονται στυλίστα έξοδο καταλαβαίνουμε πόσα στοιχεία έγγραφο στυλίστα εξόδου στον πίνακα εξόδου τότε έχουμε κρίση και τον αριθμό των επαναλήψεων επειδή στο τέλος κάθε φορά γράφεται ένα στοιχείο τα στοιχεία είναι μια κενή βιώνει για έχω βιολί δύο ληστές οι δύο πίνακες μέγεθος ν επομένως τα στοιχεία αυτά και ϕτάνει τα πρώτα και πάνε τα λεφτά πρέπει να γραφτούν στη λίστα εξόδου οι ο αριθμός των επαναλήψεων εδώ είναι το πολύ διώνη καταλαβαίνουμε επομένως αυτό σημαίνει ότι ο χρόνος εκτέλεσης του αλγορίθμου της συγχώνευσης είναι διώνη επί μια σταθερά ο κεφάλαιο του ν δηλαδή ν επι κάποια σταθερά επαναλαμβάνονται συλλογισμό θέλουμε να μετρήσουμε πόσα παραλείψεις θα κάνει πρόβα ένα τρόπος να δούμε πόσες συγκρίσεις θεό εδώ γίνονται ώρα μπορεί αυτό λίγο να μας δυσκολέψει ωραία με το να δούμε γιατί γίνεται ουσιαστικά ένα κάπως παράλληλη αύξηση δύο δεικτών και κάθε φορά δεν συγκρίνονται όλα με όλα συνδέονται κάποια στοιχεία της πρώτης λίστας με κάποια στοιχεία της δεύτερης λίστας πουρέ ένα απλός τρόπος να το Δείτε αυτό είναι επίσης τι συμβαίνει στο τέλος κάθε επανάληψης έχουμε προσαρτήσει ένα στοιχείου είτε από την πρώτη λίστα α είτε από τη δεύτερη λίστα μπήκαν σε αυτό τον πίνακα έξω ωραία επομένως αφού μετά από κάθε επανάληψη ένα στοιχείο αναγράφεται η μια την άλλη στον πίνακα εξόδου αν μετρήσω άρα όσα στοιχεία έχουν εγγραφεί στο βοηθητικό πίνακα στην έξοδο δηλαδή του αλγόριθμου τότε έχουν βρει και τις επαναλήψεις που θα κάνει πρόβα επειδή όλα τα στοιχεία φαίνεται να έχουν έτσι μια κενή βιώνει και μετά από κάθε επανάληψης σίγουρα γράφεται ένα στοιχείο παρά το πολύ θα έχουμε δύο 9 παραλείψεις μπορεί να κάνω λιγότερες επαναλήψεις αν σταματήσει μια λίστα νωρίτερα και πάλι όμως θα πουν αντιγράψω τα στοιχεία της στην έξοδο πάλι θα κάνω ουσιαστικά διώνη επαναλήψεις είναι κατανοητό βεβαίως ναι αλλά και πάλι θα τα υπόλοιπα στοιχεία να αντιγράψετε κλπ δηλαδή περισσότεροι τελειώνει πρώτη λίστα έχουν μείνει κ στοιχεία από τη δευτέρα φακής δυο μνημείων κ στοιχεία ας τον πίνακα όσο τα υπόλοιπα κ στοιχεία πρέπει να αντιγράψεις θα κάνεις μέναμε ακριβώς με αναμμένα βροχή φόρο τα υπόλοιπα στοιχεία πρέπει να εγγραφούν στη λίστα έξοδα κ στοιχεία δύο μνημείων κ σιγκαπούρη πάλι μειώνει ωραία κατανοητό ώρα πάμε στον αλγόριθμο με σόργο γιατί έχουμε βρει όλα τα σημαντικά και την πιο σημαντική απ ότι είναι ο αλγόριθμος νέο κάνει το εξής έτσι εάν μας δίνεται μια λίστα ένα πίνακας ένα αρχικό η αρχική θέση το πρώτο στοίχημα ένα τελευταίο στοιχείου να μη εάν τώρα η λίστα χειμώνα στοιχείο επιστρέφονται στοιχείων ταξινομημένα ωραία άλλος βρίσκουμε το μεσαίο στοιχείο ουσιαστικά το νησί είναι ένα γιγάντιο ουσιαστικά αυτή είναι η εντολή που διευρύνει τον πίνακα σε δύο κομμάτια και τι κάνουμε εκτελούμε αναδρομικά τον ίδιο αλγόριθμο στον πίνακα άβολη θέση ένα έως του είναι το αριστερό μισό από τη θέση του συν ένα έως μ είναι το δεξί σου και μετά να κάνουμε τη συγχώνευση με τη ρουτίνα που σας περιέγραψα τον ΑΠΟΕΛ δύο τμημάτων α και β που θα προκύψουν από την δομική κρίση του αλγόριθμου στα δύο μισά του πείνα ωραία και επιστρέφουμε φυσικά το αποτέλεσμα της συγχώνευσης νέα το καταλαβαίνουμε είμαι όμως αυτοί διαίρει και βασίλευε εκτός των άλλων μας επιτρέπει να γράφουμε κείμενα πολύ κομψό τρόπο αλγόριθμους εδώ βλέπετε οτι είναι 1.3 4.6 γκολ της έτσι ψευτό εντολές εγώ αλλά είναι μου δεν νομίζω να είναι εκτός από από κορυφαία εδώ είναι ουσιαστικά αυτός είναι ένα κόντρα σε cc πλάσμα παρακαλώ είχε τις ναι ναι του απάντησα το απάντησα πριν Δένδιας πρόσθεσε και ένα ψεύδος στοιχείο στο τέλος πάντα ανεξαρτήτως αριθμού βάλτου μια πολύ μεγάλη τιμή συνάπτεται και Σπάτα ζυγό δεν δεν ενδιαφέρει πίσω στο περίπου πανί σαν κεραυνός έτσι με το single είναι ένα δεν κάνει καμία διαφορά δηλαδή από τη στιγμή που πάνε στο νησί για να διατηρούν ακέραιο μέρος το πρώτο θα είναι από ένα εώς και τον θάνο Πάλλη απαιτούσε να νέος κύκλος θα είναι το ένα θα έχει λόγο πέντε στοιχεία παροχή έξι στοιχεία είχε ξεπεραστεί τελείως τώρα πιάνει η χρονική πολυπλοκότητα την το καταλαβαίνω το να έχει κανείς χωριά ένοχος τον ψευδό κώδικα νέα νομίζω είναι αρκετά απλός τώρα η ΕΔΟΚ το πρώτο βήμα παραλαμβάνουν είναι η διαίρεση δηλαδή ότι βρίσκουμε το μεσαίο στοιχείο και το πάμε σε δύο τμήματα όχι 10 στοιχεία σε πέντε και πέντε οι διαιρέσεις ο σταθερό για το μόνο που μας ενδιαφέρει να βρούμε τον δικτύου που στη συγκεκριμένη περίπτωση είναι το μεσαίο στοιχείο φορέα το ταξιδεύουμε αναδρομικά τώρα τα δύο μισά αυτά όποια προκύψει άλλο ο χρόνος εκτέλεσης του αλγόριθμου τ ν τότε έχουμε δύο υπό προβλήματα μέγεθος μ δευτέρα όπου τὸν Δευτέρα ενώ χρόνος για να επιλύσουμε το καθένα και το κάνω το θέλουμε αυτό το κάνουμε δύο φορές και έχουμε δύο παιδιά προβλήματα φορέα επαναλαμβάνω τώρα μου με ταυτόχρονη θα είναι χρόνος εκτέλεσης του αλγόριθμου μέλη της short σε είσοδο που αποτελείται από τρεις στοιχεία φορέα και επομένως όταν έχω άφθονη χρόνο που χρειάζομαι για να ταξινομήσουν όλο τον αλγόριθμο για να ταξινομεί ίσο ένα τμήμα που είχε μέγεθος 0 φτερά θα χρειαστώ τ ν δευτέρα έτσι όπου δικάζονται αυτά και επειδή έχω δύο τέτοια τμήματα εδώ υπάρχουν δύο ταχύτητες αυτοί και η συγχώνευση το απέδειξα θα μου πάρει χρόνο νίκη νέα επομένως ο χρόνος εκτέλεσης του αλγόριθμου μεν στο στη χειρότερη περίπτωση σε είσοδο μεγέθους δραχμή δίνεται από ένα αναδρομική σχέση που περιγράφεται έτσι πιο λεπτομερειακά από αυτή την σχέση και η απλούστερη από αυτήν δηλαδή το τ μείο το πολύ δύο τ δευτέρας σημεία στα περάσει ποινή που χρειάζομαι για να κάνω την συγχώνευση και φυσικά ουδεμία και ένα νίκη σε ειδική του ήταν από ένα στοιχείο όπως είπαμε πριν δεν χρειαζόταν καν να θες να μου κάνει την τάξεων μένει ίδια ακολουθία που έχω κάνει έχω έννομο στοιχεία το καταλαβαίνουμε πώς πάμε απορρέει από εδώ επαναλαμβάνω έχουμε διαιρέσει τον σταθερό χρόνο μας ενδιαφέρει σίγουρος πρέπει ο κεφάλαιο του ν που σημαίνει μια σταθερή βάση για ποινή και θέλουν δύο χώρας το Τ50 φτερά δύο αναδρομικές κλήσεις από προβλήματα Γι' αυτούς η δευτέρα για να προτείνει παρά λύση αυτή λέγεται αναδρομική σχέση γιατί γιατί περιγράφεται ο χρόνος εκτέλεσης συνάρτηση του εαυτού του μια αναδρομή και το ζήτημα το σημαντικό που φτάσαμε φτάσαμε ως απασχόληση στο υπόλοιπο του μαθήματος είναι πως επιλύουμε τέτοιες αναδρομικές σχέσεις δεν είναι πάντοτε προφανής λύση προς το παρόν υπάρχει κάποια απορία το πώς καταλήξαμε σε αυτήν εδώ τη σχέση όλα υπάρχουν τρεις μέθοδοι για την επίλυση των οικονομικών σχέσεων μέθοδος εκδηλώσεις αναδρομές η επαναληπτική μέθοδος η ανάπτυξη της διαδρομής και η λεγόμενη μέθοδος αντικατάστασης ίσως τις προβλέψεις και υπάρχουν και άλλες θα δούμε αυτές τις βασικές προς το παρόν τι σημαίνει μεθοδοσ εκδηλώσεις αναδρομής η μέθοδος έχει μπροστά της αναδρομής κάνει το εξής θα χρησιμοποιήσουμε τη βοήθεια ένα δέντρου δωρεά αρχικά σχετίζουν έχουν το δέντρο μας έχει μόνο ένα κόσμο του οποίου αν το κόστος είναι πίσω με ταυτόχρονη αυτό εδώ μπορούμε να γράψουμε ως εξής με βάση την αναδρομή τ ν ίσον δύο τ.μ. δευτέρας τυνησία ποινή μπορώ να το αντικαταστήσω σαν τον όρο που δεν εξαρτάται από τα συν δύο αναδρομικές κλήσεις σε προβλήματα μεγέθους τὸν Δευτέρα γιατί αυτό είναι η είναι ίδιο και μετά κοιτάω ανά επίπεδο αυτό έχει κόστος ΣΙΑ ποινή αυτό έχει κόστος διότι τ του ν Δευτέρα τα αν προσθέσουμε αυτό μου δίνει αυτού ν το αρχικό κόστος και εφαρμόζω αυτή την ιδέα σε κάθε επίπεδο μέχρις ότου καταλήξουν σε κάποιο πολύ μικρό χρόνο που ξερω ανάλυση επαναλαμβάνω αυτό που κάνανε παίρνω δύναμη νομική σχέση αυτών νήσων δύο τ.μ. δευτέρας τυνησία ποινή συσχετιζόμενα με έναν τρόπο μοναδικό μου φορέα του οποίου η αξία του κόστους είναι χρονική πολυπλοκότητα αλγορίθμων αυτό τώρα του το δέντρο επειδή το αναλύω σε έχουν ένα δέντρο που έχει τρεις κόμβους που κόσμος ρίζα αντικαθιστά το το τ ν με το σταθερό χώρο εδώ με τον όρο συγγνώμη που δεν εξαρτάται από τα και έχουμε εδώ τόσα παιδιά αυτού του κόσμου όσα μου λέει η αναδρομική αφήσει ο συντελεστής εδώ στον Ωρωπό εξαρτώνται από το ταπεινό δίοδος βουλευτής αλλά έχω δύο παιδιά και το κάθε νομικός τ η δευτέρα τώρα για να δω το κόστος αυτό χρονικό κόστος που περιγράφεται από αυτό τον ναι με αυτό τον τρόπο είναι το πρώτο μου κοστίσει αφήνει το δεύτερο αθροίζουν τα κόστη των πλευρών στον επίπεδο αυτό είναι δύο τ.μ. Δευτέρα επομένως τ ν είναι ίσο με δύο τ.μ. 2ος ουσία ποινή ακριβώς αυτό που έχουν το κάνω αυτό τώρα κοιτάξτε ΣΙΑ ποινή δύο έχω φτάσει σε αυτή την περίπτωση εδώ το καλό με τα αναδρομικά για το νομό μου δηλαδή εδώ θα γίνει συζητούν Δευτέρα και συγκινείται αυτό και θα έχουν δυο παιδιά το καθένα που θα τα η κάρτα δεν έχουν κάνει τίποτα απλά έχουν έχουν εφαρμόσει αυτήν την αναδρομή και έχουν βάλει όπου ν τον Δευτέρα Αυγή δύο τ.μ. 4ος τυνησία ποινή Δευτέρα πολλά και συνεχίζουν μέταλλο θα εκκινήσει διεθνή ύδατα και θα πάει αυτού λόγου κτλ και βλέπετε ότι σιγά σιγά πηγαίνει όντας από τη ρίζα προς τα φύλλα του δέντρου φτάνω σε προβλήματα που έχουν μέγεθος δύο το οποίο όταν έχουν δύο στοιχεία ξέρω πώς να το πω να επιλύσουν πως έδωσε μπορεί να πάρει το νήσων δύο είναι δύο έπειτα αυτό ένα τούνελ δεν σε κάτι και τώρα για να βρούμε διότι με τον τρόπο αυτό ποιά είναι γιατί βλέπετε αυτά εδώ θα αντικατασταθούν από κάτι σταθερό όλα τα άλλα έχουν αντικαταστήσει με όρους που δεν εξαρτώνται από την αναδρομική σχέση από τα ωραία και αρχίζω το κόστος όλων των επιπέδων το πρώτο Ένεση επιμένει το δεύτερο είναι δύο φορές επισείει ποινή δευτέρα δίνει πάλι συμβαίνει το τρίτο επίπεδο έχω τέσσερις τέσσερις κόμβους που καθένας έχει κόστος χρονικό σημείο επί ΝΔ αναπαλαίωση ποινή μπορείτε να δίδονται στο επίπεδο να κ θα έχω διοριστεί για πάντα τους κόμβους ο καθένας θα εκτίσει ποινή διατηρεί στην απάλυνση ποινή και τα τελευταία δύο χρόνια Δευτέρα τέτοια το καθένα είναι C P δύο αυτό επαναλαμβάνω ένα άγαλμα κουνήσουν δύο εδώ και εδώ αυτό γίνεται δεν γίνεται βάσει επί δύο και αυτός με τον TAP του δύο και πάλι από τη δευτέρα παιδεία και έχω πάλι το κόστος για ποινή το θέμα είναι πόσα τέτοια επίπεδα έχουν πόσα επίπεδα τέτοια έχω είναι πολύ είναι εύκολο να βρείτε γιατί διερωτάται χώρα διά δύο χώρια την πρώτη φορά για κ εσένα θα ως την Δευτέρα 10 πόσο βιότοπος των τρίτων κλπ πιο είναι το μέγιστο κ έτσι ώστε να φτάσουν σε ένα στοιχείο αυτό συμβαίνει αν και μόνο αν άννα τόνοι είναι δύο στην κ αν και μόνο αν το κ είναι λογαριασμός του ν με βάση το δύο φορέων για το λόγο αυτό έχω λογαριασμό ΥΚΩ αριθμό επίπεδο αυτά ταχύτατες του φροντιστηρίου που κρατά για τόσο έτσι δεν είναι τοπίο των δέντρων και τα οφείλει να επομένως εδώ έχουμε να κάνουμε τώρα έχω ΣΙΑ ποινικό τους σε κάθε επίπεδο έχουν λιώνει επίπεδα άρα θα προσθέτουν και η λύση είναι ο κεφάλαιο του δηλώνει μια σταθερά δηλαδή επιλογών ένα σταθερά είναι αυτή η σταθερά που προκύπτει από την συγχώνευση ο κεφάλαιο του Μιωνή είναι ένα σταθερά συμβολίζει ένα σταθερό παράγοντας συ ποινή αυτό συμβολίζουν οδικός τουρισμός ξέρουμε σταθερά αυτή αλλά δεν μας ενδιαφέρει κατηγορούμαι πάντα έτσι αυτό που μας ενδιαφέρει ότι είναι μια εδώ είναι ότι είναι μια σταθερά έτσι και εμάς μας ενδιαφέρει να βρούμε επομένως με τον τρόπο αυτό ξεκινά από ένα αναδρομική σχέση είναι διαστημικός περισσότερα θα τοποθετήσει και φτάνουμε σε έναν κλειστό τύπο δηλαδή σε κάτι που μας δίνει τη λύση της της χρονικής πολυπλοκότητας χειρότερες περιπτώσεις ένα προβλήματος συγκεκριμένη περίπτωση του νέλσον όποιος είναι ανεξάρτητος από τ δεν υπάρχει ταυτότητα μέλος κοινόχρηστος κήπος τις σχέσεις να νέα σεζόν και με μεγαλύτερο δεν δώσαμε αυτό βάζαμε σε κάθε αυτό που κάναμε είναι ότι το είναι άφθονη με την που σπάει σε δύο πεδία τὸν δεύτερο και τὸν Δευτέρα και με τον τ ν αντικαθιστούμε με τον σταθερό με τον όρο που τους ενώνει το λαό που δεν εξαρτάται από τον ν και το κάνουμε αυτό αναδρομικά από αυτό όπως εξήγησε ενώ σε προηγούμενα μαθήματα δεν μίλησε καθόλου αυτά ναι στο προηγούμενο μάθημα κάνατε μια ειδική μορφή δέντρων που σας βοηθάει να υλοποιήσετε αυτό την μια δομή δεδομένων που λέγεται σόρος δε σημαίνει ότι οποιοδήποτε δέντρο συναντάμε είναι σόρος φορέα |