Μάθημα 1 (μέρος Β) / Εισαγωγικά - Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων (μέρος Β)
Εισαγωγικά - Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων (μέρος Β): Την προηγούμενη φορά είδαμε τι σημαίνει αποδοτικό αλγόριθμο και για ποιο λόγο θα επικεντρωθούμε στη λεγόμενη ανάλυση πολυπλοκότητας χειρότερες περιπτώσεις το μόνο που δεν έχουμε συζητήσει σημαντικό βεβαίως είναι το μοντέλο αξ...
| Κύριος δημιουργός: | |
|---|---|
| Γλώσσα: | el |
| Φορέας: | Πανεπιστήμιο Πατρών |
| Μορφή: | Video |
| Είδος: | Ανοικτά μαθήματα |
| Συλλογή: | Τμήμα Mηχανικών Η/Υ & Πληροφορικής / Εισαγωγή στους Αλγόριθμους |
| Ημερομηνία έκδοσης: |
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ
2014
|
| Θέματα: | |
| Άδεια Χρήσης: | Αναφορά-Μη-Εμπορική Χρήση-Όχι Παράγωγο Έργο |
| Διαθέσιμο Online: | http://delos.upatras.gr/opendelos/videolecture/show?rid=22fcc31 |
| id |
9b8d3668-a510-4ecb-9979-d2593338d376 |
|---|---|
| title |
Μάθημα 1 (μέρος Β) / Εισαγωγικά - Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων (μέρος Β) |
| spellingShingle |
Μάθημα 1 (μέρος Β) / Εισαγωγικά - Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων (μέρος Β) Επιστήμες Υπολογιστών, Πληροφορικής, Τηλεπικοινωνιών Επιστήμες Μηχανικού Η/Υ και Ηλεκτρονικού Μηχανικού Ζαρολιάγκης Χρήστος |
| publisher |
ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΩΝ |
| url |
http://delos.upatras.gr/opendelos/videolecture/show?rid=22fcc31 |
| publishDate |
2014 |
| language |
el |
| thumbnail |
http://oava-admin-api.datascouting.com/static/0553/614a/2f9b/9c40/84e8/26cd/32e2/1988/0553614a2f9b9c4084e826cd32e21988.jpg |
| topic |
Επιστήμες Υπολογιστών, Πληροφορικής, Τηλεπικοινωνιών Επιστήμες Μηχανικού Η/Υ και Ηλεκτρονικού Μηχανικού |
| topic_facet |
Επιστήμες Υπολογιστών, Πληροφορικής, Τηλεπικοινωνιών Επιστήμες Μηχανικού Η/Υ και Ηλεκτρονικού Μηχανικού |
| author |
Ζαρολιάγκης Χρήστος |
| author_facet |
Ζαρολιάγκης Χρήστος |
| hierarchy_parent_title |
Εισαγωγή στους Αλγόριθμους |
| hierarchy_top_title |
Τμήμα Mηχανικών Η/Υ & Πληροφορικής |
| format |
Video |
| rights_txt |
CC |
| rightsExpression_str |
Αναφορά-Μη-Εμπορική Χρήση-Όχι Παράγωγο Έργο |
| organizationType_txt |
Πανεπιστήμια |
| hasOrganisationLogo_txt |
http://delos.upatras.gr/opendelos/resources/logos/upatras.png |
| author_role |
Καθηγητής |
| author2_role |
Καθηγητής |
| relatedlink_txt |
https://www.aueb.gr/ |
| durationNormalPlayTime_txt |
00:37:39.58 |
| genre |
Ανοικτά μαθήματα |
| genre_facet |
Ανοικτά μαθήματα |
| institution |
Πανεπιστήμιο Πατρών |
| asr_txt |
Την προηγούμενη φορά είδαμε τι σημαίνει αποδοτικό αλγόριθμο και για ποιο λόγο θα επικεντρωθούμε στη λεγόμενη ανάλυση πολυπλοκότητας χειρότερες περιπτώσεις το μόνο που δεν έχουμε συζητήσει σημαντικό βεβαίως είναι το μοντέλο αξιολόγησης σε ποιο μοντέλο μετράμε την αποδοτικότητα και τι σημαίνουν στοιχειώδεις πράξεις στο μοντέλο αυτό με δύο Προσέξτε λίγο αυτό είναι πάρα πολύ βασικό για να καταλάβετε το υπόλοιπο του μαθήματος αν δεν είναι κάτι που δεν είναι τελείως σαφές παρακαλώ πολύ όπως είπα μη διστάσετε να τα το λεγόμενο μοντέλο μηχανής τυχαίας προσπέλασης είναι ουσιαστικά μου πολύ κοντά στο νου όπως πραγματικά χρίστηκε χτίστηκαν υπολογιστές δεν την εμφάνιση των πολλοί πίνουν φίλιππα υπολογιστών δηλαδή έχουμε μια κεντρική μονάδα επεξεργασίας όταν κανένας από τους η οποία έχει πρόσβαση σε μια μίνι που μπορεί να έχει έναν απεριόριστο αριθμό ωστόσο δε μας ενδιαφέρει και πρόσβαση σε κάποιους καταχωρείται μας και αυτή η κεντρική μονάδα επεξεργασίας μπορεί να εκτελεί λεγόμενος εντολές μηχανής ωραία τις οποίες δηλαδή ότι οι εντολές που μάθατε στη γλώσσα σε λοιπόν κανένας από τους το μοντέλο αυτό προτού εισιτήρια και κύριοι βλέπετε δεξιά σίγουρα στην καταγωγή αλλά ουσία μεγάλωσε σπούδασε και έδρασε στην αμερική δολοφόνο έναν έχει κάνει πολλά σημαντικά πράγματα στη ζωή του ένα από αυτά είναι το μοντέλο αρχιτεκτονικής των των υπολογιστών το δεύτερο είναι αντίθετα από τους πατέρες της θεωρίας παιγνίων μια ακόμα και χάνεται κ.ά. αν πάτε στην ιστοσελίδα του αυτό μας ενδιαφέρει λοιπόν εδώ είναι ότι έχουμε ένα ένα μοντέλο Υπολογιστικής μηχανής θεωρητικό βέβαια απαλλαγών μοιάζει πάρα πάρα πολύ με το μοντέλο το οποίο έχουν οι σύγχρονοι υπολογιστές ένα κεντρική μονάδα επεξεργασίας που έχει πρόσβαση σε έναν απεριόριστο αριθμό θέσεων μνήμης και σε ένα ευκαταφρόνητες μια ένοπλος Καλαβρύτων τώρα θα πρέπει να ξέρετε ότι εκτός από εντολές μηχανής αυτό που θέλω να συζητήσετε και να καταλάβετε είναι το εξής ότι το μέγεθος της λέξης μνήμης έχει πολύ μεγάλη σημασία έτσι ώστε να μετράμε σωστά την απόδοση ένα αλγόριθμου ξέρετε ότι όταν έχουν μεταβληθεί b της σάμι σε ένα θέση μήνυση μπορώ να παραθέσω δυο στην πλήρη στοιχεία αυτό θα πρέπει να λέγεται μαθαίνουμε είναι μια χαρά εάν το θυμάστε δεν τίποτα Λίβας βάση δύο γιατί γιατί έχουμε το δυαδικό σύστημα συμπολεμιστές στο δεκαδικό σύστημα για παράδειγμα όταν έχουμε τρεις ψηφία μπορούν να αναπαραστήσουν 10 στην τρίτη βάσει του συστήματος στο πλαι των ψηφίων διαφορετικούς αριθμούς πορεία από το χίλιους δηλαδή από 0 μέχρι 999 είναι 1000 τ.μ. αντίστοιχα μπορούμε λοιπόν με τα λόμπι για να αναπαραστήσουν δύο 61 στοιχεία γιατί το λέω αυτό διότι όταν έχουν ένα πρόβλημα το οποίο ταξινόμηση στοιχείων έχουνε στοιχεία ένα μικρό γλυκό θα πρέπει το πλήθος των στοιχείων αυτών αναπό να μπορεί να παρασταθεί στη μνήμη του υπολογιστή δηλαδή θέλω να ταξινομήσουν 100000 αριθμούς τελών ταξινόμησης το ένα εκατομμύριο αριθμούς εκατομμύρια ΑΦΜ όλων των φορολογουμένων Σαββίδη χώρας 27000000 θάνος ταξινόμηση πορεία δηλαδή θα αφού τόνοι θα πρέπει να μπορεί να παρασταθεί έτσι δηλαδή θα πρέπει να παραστεί η ποιος τα λέει αυτά στοιχεία το πλήθος των στοιχείων αυτό σημαίνει αν πάρουμε λογαριασμούς των δύο μερών λογαριασμό Novasports δύο σημαίνει ότι χρειάζομαι λογαριασμού με βάση το δύο μ BBC για να αναπαραστήσουν ένα πλήθος ν αριθμό καταλαβαίνουμε 1000 όμως σχέση μεταξύ τάβλι και δύο συναυλίες είναι εκθετική δηλαδή πάνω από έναν αριθμό κι αυτός αριθμός τάφων στον εξακριβώσατε αριθμού τση μιλεί η απόσταση μεταξύ στάβλου και βυσσοδομούν είναι εκθετική ετσι εθνική σύνταξη οι ίδιες να δουν έτσι συμβαίνει μεταξύ λογαριασμό του ν και του ν δηλαδή όλο το τόνοι είναι εκθετικά μεγαλύτερο λογαριασμό υπάρχει θετική αποστάσεις σας τα λέω όλα αυτά λείπουν για να σας πω ότι όταν έχουν μέγεθος εισόδου μ θα πρέπει οι λέξεις είναι εμείς να αποτελούνται από λογαριασμό του ν με τις δεν χρειάζομαι παραπάνω δεν βγάζουμε δηλαδή να μη μπει για να παραστήσουν λίγα πράγματα αλλά πολύ μικρότερο αριθμό ψηφίων πανό μπαλόνια να αναπαραστήσουν μας δηλαδή για να παραστεί σε αριθμούς ούτε καν οικοσύστημα από τον δεν μέχρι το 999 χρεώσουν τρεις ψηφία δε χρειάζομαι Νάρκωσαν μειοψηφία αυτοτελώς τώρα για να γράψω τον αριθμό εκατομμύρια έτσι γίναμε δηλαδή τους πόσα εκατομμύρια αριθμούς χρειάζομαι έξι ψηφία δε χρειάζομαι 1000100 του αξιόλογα ρυθμός του 10 του πλήθους τον αριθμό των εκατομμύρια αυτό λέμε εδώ καταλαβαίνουμε φορέα εκτός από το μεγάλο σου δεν υπάρχουν προβλήματα που έχουνε και τιμές στοιχείων εισόδου κεφαλαίων δηλαδή δεν είναι μόνο ότι έχω να ταξινομήσουν ένα εκατομμύριο αριθμούς αλλά θέλω να δω και τείνουμε να ταξινομήσει ωραία είναι πενταψήφιο 16100 ψηφιακά από διακόσιους γάμους στοιχεία αποτελούνται εδώ κάνουμε λοιπόν προφανώς λοιπόν με την ίδια συλλογιστική όταν έχω ένα στοιχείο το οποίο έχει τιμή ν κεφαλαιο χρειάζεται λογαριασμός του ν κεφαλαιο b για να παρασταθεί και εγώ κάνω την υπόθεση ωραία ότι αυτά τα δύο σχετίζονται με πολύ κυνικό τρόπο κρατών κεφάλαιο δεν μπορεί να είναι μεγαλύτερο από το πλήθος των στοιχείων υψωμένο στην C Σιμόπουλος είναι μια σταθερά δηλαδή έχουν ταξινομήσεις εκατομμύρια αριθμούς και έπειτα τους είναι οι δύο αυτοί οι αριθμοί δεν είναι παραπάνω από την από 1000010 στην ακτή οι αριθμοί αυτοί δεν είναι πάνω από 10 στη 12η για παράδειγμα έτσι από αν πως την τρίτη θα 10 στην 18η έτσι είναι μια λογική υπόθεση αυτή δεν μπορεί να είναι εξωτικά μεγαλύτερος δεν μπορεί να να ξανά εκατομμύρια βαθμούς και να ήδη οι τιμές που αναπαριστούν άνετο δύο στην ανά εκατομμύριο για παράδειγμα επομένως με βάση λοιπόν ότι τον κεφάλαιο είναι κάποιο κάποια δύναμη του ν όπου τους είναι μια σταθερά και αυτό πρέπει επίσης να μπορεί να παρασταθεί στη μνήμη του υπολογιστή δηλαδή πρέπει κι αυτό να ενώσουμε δύο στην παύλου ανταμοιβή λέξη γίνει μας τότε σημαίνει ότι το ήλεγξε μίνι Λαυρίου είναι ένα αν πάρετε λογαριασμούς των δύο αυτών μερών τόση γιατί δεν τονίζει στην δύση είναι ίσο με δύο στην Danone αυτό σημαίνει ότι αν πάρω λογαριασμούς και των δύο μερών με βάση το δύο εις τον οποίον δίκτυο θα σταθώ παραλείπω γιατί όλοι οι λογαριασμοί μας θεωρούμε την απόφαση των δύο όσα λέγονται ειδικά τώρα από βασικές διότι στον αριθμό που εκθέτεις εδώ πάει μπροστά και εκθέτει Ευρωπαϊκή πίστη μπροστά και ευρωομόλογα αγνώστου δύο με βάση τους δύο κάνει μονάδα επομένως το ταμπλό είναι ίσο με το συν και φίλων ν όλα αυτά σας τα λέω για να σας πω το εξής ότι εδώ λοιπόν για είσοδο ένα μέγεθος εισόδου πλήθους είναι μικρό και τιμών στοιχείο είναι κεφάλαιο χρειαζόμαστε λέξεις μνήμης πουλάνε ένα σταθερά επί λογαριασμός το πλήθος των στοιχείων b τόσα δείτε επιτρέπουν σε ένα λέξη ναι εμείς και ουσιαστικά αυτό θα το μετρήσουμε σαν ένα επίσης στοιχειώδη πράξη δηλαδή επαναλαμβάνω δεν μπορεί η δεκαδικά συστήματα υπάρχουν πάρα πολλά διάδικο ξέρετε τριαδικό δεκαδικό 16 άδικο μπορεί να υπάρχει το μοναδιαίο εσείς δηλαδή έχω ένα σύμβολο αυτό ας πούμε και μπορώ να παραστήσουν τους αριθμούς να τον αριθμό τρεις τραγούδια σύμφωνα τον αριθμό επτά γράφω καταπίεση έτσι αθύρματα στο ένα εκατομμύριο θα μπορούσα να γράψω ενα εκατομμύριο παιδιά σύμφωνα έτσι δεν είναι αυτό είναι το b αυτό δεν μας το μοναδικό σύστημα κυβερνά εκεί θέλω να σας εφιστούν την προσοχή και δε μπορούμε να πούμε ότι τον αριθμό εκατομμύρια σε οποιοδήποτε σύστημα αναπαραστάσεις έστω και στο μοναδιαίο μπορώ να τον εγγράψουν σε μια θέση μήνυση να τον διαβάσω διάθεση μνήμης με ένα στοιχειώδη πράξεις μπορώ να το κάνω αυτό σε λογαριασμό της αξίας έτσι του ν μικρό είναι κεφάλαιο MB στο δυαδικό σύστημα γιατί τόσα χρειάζονται επομένως επαναλαμβάνω στη ν π ως έχει το στοιχειώδες υπολογιστικό βήμα σημαίνει ότι όταν έχω ένα στιγμιότυπο εισόδου με πλήθος στοιχείων μικρό αγγλικό με μέγιστη τιμή στοιχειώνει κεφάλαιο χρεώνουν ένα μονάδα χρόνου για κάθε βασική λειτουργία δηλαδή αριθμητικές πράξεις λογικές πράξεις συγκρίσεις καταχωρήσεις και επίσης ένα μονάδα χρόνου για προσπέλαση στη μίνι είτε αυτοί είναι ανάγνωση είτε είναι έγγραφη αλλά ένα σταθερού αριθμού λέξεων μνήμης των λογαριασμών ν b όχι έναν απεριόριστο αριθμό πομπή καταλαβαίνουμε πόσο αυτή είναι μια λογική υπόθεση που κάνουμε και θα πρέπει πάντα να το θυμόμαστε τώρα βέβαια μπορεί κάποιος να πει ότι ισότητα γιατί Χρόνης σόργο ένα μονάδα χρόνου για όλες αυτές τις πράξεις ξέρουν πολύ καλά και πολλαπλασιασμός διαίρεση είναι κοστίζει περισσότερο χρόνο από ότι πρόσθεσε ωραία η σύγκριση δύο αριθμών προσθαφαιρέσεις συνάντησαν το υπόλοιπο είναι μεγαλύτερο του ένα μικρότερου ίσως να κάνει έτσι η σύγκριση επίσης είναι πολύ πιο χρονοβόρα αποτελεί πρόσθεσε δεν πειράζει επειδή δομεί μιλάμε για πράξεις στις τάξεις στα σύγχρονα συστήματα των δυναμικών την είναι ακόμα και το χαμηλότερο πάρτε εδώ σαν στοιχειώδη πράξη και μέγιστη σε χρόνο λειτουργίας δεν μας πειράζει έτσι αυτό το κάνουμε για να διευκολυνθούν με καλύτερα στους υπολογισμούς μας για να μην έχουμε και λέμε τόσο πρόσθεσε ωστόσο διαίρεση κλπ δεν μας ενδιαφέρει παίρνουμε λοιπόν τα στοιχειώδη υπολογιστική πράξη τη μέγιστη ας πούμε σε ένα νοσοκομείο πράξη από αυτές έχει και αυτό τη βαφτίζουμε στοιχειώδη πράξη εξάλλου αυτό συνάδει και με το μοντέλο που σας είπα τις χειρότερες περιπτώσεις και τώρα η επιθυμία και μάγος που λέγαμε πριν μεταφράζεται σαν χρονική πολυπλοκότητα η αντίστοιχη χωρικοί πολυπλοκότητα σαν μια συνάρτηση του πλήθους της εισόδου και του λογαριασμού του κεφαλαίου των τιμών δηλαδή που αναπαριστά ίσως δηλαδή μας να το πω καλύτερα εδώ θα έχουμε λοιπόν ότι ισχύει αυτό ότι χρονική θέλουμε χρονική συνάρτηση να είναι ένα συνάρτηση δύσοσμο αυτής κινητών πραγμάτων επιλογών αριθμού του μια χαρά σε κοινή θέσεων ν κρήτης θα κάνει ας πούμε αλγόριθμος αυτός στοιχειώδεις πράξεις ωραία για παράδειγμα δε δηλαδή δεν θέλουμε να πούμε ότι δεν θέλουμε να πούμε ότι αλγόριθμους μας θα κάνει τρεις ν τετραγώνου επί κεφαλαίου πράξεις αυτό δεν το θέλει θέλουμε δηλαδή αυτό δεν θα θέλουμε οι εξαρτήσεις διαθέτουν το πλήθος ήδη τις τιμές όπως των κεφαλαιαγορών είναι ως προς τον λογαριασμό των γιατί τότε μετραει σωστά μου τότε είναι σωστή αξιολόγηση και το θέμα λοιπόν είναι πλέον τη μορφή έτσι μια άλλη μορφή συναρτήσεις θα μπορούσα να κάνω που είναι επίσης σωστή το καυτό μήνα έξοδό μου δύο τη στιγμή επί λογαρισμούς του ν κεφαλαιο στην τριετία και αυτή είναι ένα συνάρτηση κλοπή πάλι πληροί αυτές προϋποθέσεις δηλαδή είναι ένα συνάντηση το σάββατο από τον από κάποια δύναμη του ν από κάποια δύναμη του λογαριασμού του ν κεφαλαιο τώρα το βασικό ερώτημα είναι τι μορφή πρέπει να έχει συναντήσεις της προσέξτε λίγο ο πιο απλός τρόπος για να επιλύσετε ένα πρόβλημα είναι η λεγόμενη μέθοδος της ωμής βίας δηλαδή θέλετε να κάνετε Ταξινόμηση ένα αριθμό μπορείτε να παράγετε όλες τις μεταθέσεις των αριθμών που είναι παραγωγικός το πλήθος ωραία να διαφυλάξετε και να Δείτε ποιες από αυτές είναι σε ταξινομεί σειρά και να πείτε έκαναν την ταξινόμηση των αριθμό συνήθως λοιπόν αυτό δηλαδή που κάνουμε είναι έλεγχο όλων των δυνατών λύσεων του προβλήματος και επιλέγουμε εκείνη που μας δίνει την επίλυση μου που θέλουν αυτό παίρνει εκθετικά μεγάλο χρόνο ακόμα χειρότερο τον παραγωγικό είναι είναι κάποια βιώσιμη λιωμένη ακόμα χειρότερα από το διαστημικό και όπως θα δούμε έχει πρακτική αξία μηδαμινή φορέα και πολύ συχνά μας δημιουργεί πολύ μεγάλα προβλήματα απλά όταν μιλάμε όταν λοιπόν μιλάμε για επιθετικό για υπερ υπερ εκθετικό χρόνου αλγορίθμου μιλάμε για πολυπλοκότητα στοιχειωδών βημάτων που χει μορφίνη σταθερά επί κάποια άλλη σταθερά α δύο για παράδειγμα υψωμένο εις Ξενία δυνάμει του ν επί ένα δίνανε του λογαριασμού του ν ωραία για παρά παράδειγμα όταν αυτό εδώ ένα άλλο παράδειγμα τέτοιας συνάντησης είναι αυτή εδώ ορεινή παραγωγικό πούνε δυόσμου επιλογών αυτήν ένα είπε θετική συνάρτηση πρακτική πολύπλοκων ράφτη επαναλαμβάνω η γενική της μορφή τώρα όταν μιλάμε για πολεμική πολυπλοκότητα μιλάμε για μια συνάρτηση δύο είναι πάλι μια σταθερά επί κάποιο κάποια δύναμη κάποιοι πολεμούν δι' μόνον μάλλον του ν υψωμένες την διετή λογαριασμό του ν υψωμένο σε κάποιο δυναμικά όπως των ΔΟΥ Μ3 η πράγματα όλο το έθνος του ν το 4G λογαριασμούς για η όπως λέει είναι 20 χρονος έχει αυτή την επιθυμία την λεγόμενη επιθυμητή ιδιότητα κλιμάκωσης τι σημαίνει αυτό ωραία σημαίνει το εξής ότι ευρώ τι σημαίνει ότι ιδιότητα κλίματος ότι εγώ θέλω όταν μεγαλώνει το μέγεθος της εισόδου διπλασιάζεται τριπλασιάζεται να ξέρω ότι ο χρόνος θα τους θα πολλαπλασιαστή επίσης κατά ένα σταθερό παράγοντα όχι κατά κάποιον εκδοτικό παράγοντα κάποιο αυθαίρετο πάνω από σχεδόν κανένα είσπραξη πετάξτε τότε έχετε προβλήματα για τους μ αυτό που είπαμε που επιλύεται συγχρόνως η ποινή στην διαδηλωτών αριθμός του μισθού τους μένουν στην κ εάν αυτός το ΓΔ βάλτε τώρα στα δόντια όπου η διώνη δηλαδή διπλασιάζεται είσοδος τι αποτέλεσμα θα δώσει αυτός αλγόριθμους έτσι αν έχουμε βρει τόπος στοιχειώδης πράξη κάνει θα δώσεις παραπάνω αναλογούν βάζουμε το βιώνει όπου μας βιώνει και προβλέπεται ότι εδώ επειδή το δύο θα υψωθεί εδώ στην τύχη θα βγει δύο της την αυτόνομη πρώτον διότι στην δύση είναι ένα περιβάλλον VR δηλαδή επιμείνει στην την γενιά στην παρέμβασή επί των λογαριασμός του ν λογαριασμούς του του δύο εδώ μπορεί να εξαλειφθεί επομένως αυτό είναι υπονόμευση δυναμικότερο κάνεις πράξεις μπορείτε να το Δείτε όπου εάν λοιπόν αυτή σταθερά εδώ που βλέπουν εδώ βλέπετε ότι και πάλι την ίδια μορφή κάτω εκτός από αυτόν εδώ τον πολλαπλασιαστικό παράγοντα που βλέπουν διοριστεί συναντώνται όμως μένει σταθερό είναι το δύο και πάρα πάρα το διολισθαίνει BC 9ο δύο στην δύο το 2008 για το συγκεκριμένο παράδειγμα άρα εδώ ναι διπλασιάζεται είσοδος και αντίστοιχα το πουλί οκταπλάσιες το χρόνος αλλά έχουν ένα όπου υπάρχει ένα σταθερός παράγοντας 10 παλαιών ετών δ κεφαλαίο δεν εξαρτάται από το μέγεθος της εισόδου εξαρτώνται μόνο από τις σταθερές από κάποιες σταθερές σταθερές που υπάρχουνε στην ανάλυση χρονικής πολυπλοκότητας To συγκεκριμένο αλγόριθμο το καταλαβαίνουν αυτό επαναλαμβάνω στην ιδιότητα της κλιμάκωσης λέμε το μέγεθός μας είναι απόλυτα πάει βιώνει πάει τρεις Άννη δηλαδή πολλαπλασιάζεται επί κάποιον σταθερό παρά θα θέλουμε το ίδιο να συμβαίνει και ως προς τον χρόνο δεν θέλουμε πάντα να ακολουθεί αντίστοιχη κλιμάκωση δηλαδή διπλασιασμός σου διπλασιασμό του χρόνου θα ήταν το ιδανικό αυτό μπορεί να συμβαίνει αυτό το θέμα όμως εδώ είναι ότι υπάρχει ένα σταθερός παράγοντας δ κεφαλαίο όπως βλέπετε από την ανάλυση όμως κατά τον οποίον μεγαλώνει η χρονική πολυτέλεια κότα όταν διπλασιάζεται είσοδος όταν διπλασιάζεται αντίστοιχα αυτό μας είναι αρκετό και μάλιστα λέμε έναν αλγόριθμο την πόλη νίκου χρόνου ανίσχυροι αυτοί οι παραπάνω ιδιότητες κλιμάκωσης για παράδειγμα αυτό δεν μπορεί να συμβεί στους έχει ειδικούς αλγόριθμους αυτή ιδιότητα κύματος μπορείτε να δοκιμάσετε θα δούμε για παράδειγμα σε λίγο που Manager θα δούμε τώρα το παράδειγμα υπάρχει κάποια πορεία μέχρι το παράγων αυτές είναι δύο γενικές μορφές εκδοτικών και πολεμικών συναρτήσεων και πλέον λέμε πολιτικού χρόνου αλγόριθμο εάν έχει τη συγκεκριμένη ιδιότητα κλιμάκωσης αλλιώς έτσι λίγο χρόνο ένα διαφορετικός ορισμός τώρα για να καταλάβετε την διαφορά που έχουνε η θετική άποψη που είναι τους αλγόριθμους ως προς το χρόνο πείτε ότι έχετε είναι σημαντικό να καταλάβετε αυτό παρανομία πείτε ότι έχετε έναν υπολογιστή όποιος θέλει ας ένα στοιχειώδεις λειτουργίες του δεύτερον φορέων και λέμε ότι το γράφημα έξι ένα ώρα και λέμε ότι αυτός υπολογιστής πόσο μεγάλα στιγμιότυπα λύνει αν τον αφήσουμε ένα δεδομένη προβλήματος τον αφήσουμε απέξω για ένα ώρα πείτε λοιπόν ότι έχουμε ένα πολύ γενικό και ειδικό αλγόριθμο ποιητών και πολεμικός έχει ως προς την χειρότερη περίπτωση αριθμός στοιχείων των πράξεων η αναγνω εκθετικός δύο στη ν και ότι αν αφήσουμε αυτό τον υπολογιστή που εκτελεί εσένα στοιχειώδη λειτουργία στην χώρα το σώβρακο μυστηριωδώς λειτούργησε τον χρόνο να τρέξει για ένα ώρα ότι ο πρώτος κατηγορούμενος λύνει στιγμιότυπα μέγεθος 9 ένα μικρό και δεύτερος μια ανακεφαλαίωση το ερώτημα που θέλουμε να απαντήσουμε ως προς την κλιμάκωση είναι το εξής Επιτροπή εσείς παίρνετε έναν υπολογιστή εκατό φορές πιο γρήγορο δηλαδή βρισκόμαστε στο 2014 παίρνω τώρα ένα καινούριο υπολογιστή φέτος δεν θα υπολογιστεί που είχε έξω εγώ κάποιος φίλος σας κάποιος γονιός σπουδών αγόρασε το 2007 2008 αυτός πρώτος δηλαδή έξι χρόνια παλαιός κι αυτός σε νέο σούπερ ντούπερ σύγχρονους υπολογιστές όποιος είναι κάνει εκεί είναι 100 φορές πιο γρήγορος όπως στο hardware για τον σε σχέση με τον παλιό τον υπολογιστή και το ερώτημα που θέλουμε να θα θέσουμε είναι ωραία εγώ πήρα έναν καινούργιο υπολογιστή αφού είναι πολύ 100 φορές πιο γρήγορος προφανώς θα μπορεί να λύσει σε μια ώρα μεγαλύτερα στιγμιότυπα από μεγέθους ένα ένα σε σχέση με τον ανταγωνισμό δεν είναι αφού οι πιο γρήγορος και τρέχει σε μια ώρα θα θα μπορεί να λύσει μεγαλύτερα στιγμιότυπα στο ίδιο πρέπει τον ίδιο δηλαδή δολάρια μεγαλύτερο από το ένα Νοεμβρίου και των ακροδεξιών το ερώτημα είναι πόσο μεγάλη θα είναι η στιγμή ωραία τι κάνουμε για να μπορούμε να κάνουμε το εξής λένε όλα λόγω στον πολυπλοκότητα των εδώ των στοιχειωδών πράξεων για τις διαφορετικές εισόδους ν 2ετών και 9 να φανεί διότι πράγματι λένε ένα τετράγωνο πρέπει ναναι ίσως με το λόγω των διαφόρων ταχυτήτων στους υπολογιστή των επεξεργαστών μιλάτε αφού αυτός λόγος να κλείσουν 100 κούκλες δύο είναι 100 φορές πιο γρήγορα από τους αν κάνουμε λοιπόν εδώ τις πράξεις δηλαδή παρόλες τις ρίζες αυτός λόγος είναι 100% κάνει 10 επομένως μπορούμε να λύσουμε τον στιγμιότυπα προβλήματος στο νέο υπολογιστή με τον πολιτικό αλγόριθμο που είναι 10 φορές μεγαλύτερα σε ένα ώρα από την Προύσα αναλύσουμε το μπάλωμα σχολή στη που το αγόρασαν στα μαθητικά μας χρόνια από το 2008 ο δηλαδή και πήραμε καινούργια υπολογιστή που είναι κάτοχος του γρήγορος αλγόριθμος που για την συγκεκριμένη Πολύτροπον η μπορεί επίσης να λύσει 10 φορές πιο γρήγορα μεγαλύτερα στιγμιότυπα λιανική που σε μια ώρα ταξινομούν σαμε τώρα 10000000 βαθμούς τώρα μπορούμε να αξιοποιήσουμε 100000000 με τον υπολογιστή είναι πάμε να κάνουμε την ίδια αίσθηση στον εκθετικό αλγόριθμο δηλαδή δεν σε ένα ώρα ο εκθετικός αλγόριθμος τον παλιό υπολογιστή λένι στιγμιότυπο μεγέθους ένα ένα κεφάλαιο με τον εκατό φορές πιο γρήγορο υπολογιστή αφού είναι εκατό φορές πιο γρήγορος ένα ώρα πίσω θα εξαντλήσει πολύ μεγαλύτερη στιγμή έξι η διαδικασία είναι ακριβώς ίδια αναλογία δηλαδή θα πάρω το λόγω των πολύπλοκων ειδών που πρέπει να λύσουμε το λόγο τον της ταχύτητας των επεξεργαστών μόνο που εδώ την εκθετική συνάρτηση έχουν διαφορετικό είδος πράξεων θα πρέπει δηλαδή το δύο στη Ν2 μειώνει έναν ίσο με 100 που σημαίνει ότι όταν λογαριασμοί ίσως και τα δύο μέλη των δύο τόνοι βιομηχανία να κάνει λογαριασμό στο κάτω που είναι διάδικος λογαριασμούς 100 μικρότερος η που σημαίνει ότι στο εκατό φορές πιο γρήγορο hardware με το ξωτικό αλγορίθμου μπορώ να λύσω επτά στιγμιότυπα εισόδου που είναι μόνο κατά επτά μονάδες Μιχαλίτσα δηλαδή εκεί που με τον αλγόριθμο σας στον βαλέσα υπολογιστή στη ένα ώρα μείνατε έξω λόγω τάξη μούσα 100000 στοιχεία δικός μου μου τώρα στο 100 φορές πιο γρήγορο σούπερ ντούπερ υπολογιστή μόλις αγόρασα εμπορικά Ταξινόμηση ένα ώρα 100007 στοιχεία καταλαβαίνετε λοιπόν ότι δεν γίνεται και τίποτα και κ γιώργος χώρα επομένως το πρώτο μάθημα εδώ είναι ότι η ωμή βία δηλαδή η πρώτη ιδέα που μπορεί να σκεφτεί για να επιλύσετε κάτι μπορεί να μη δουλεύει και δουλεύει ειδικά αν οδηγεί σε εκθετικό αλγόριθμο για το λόγο που ανέφερε για αυτό μιλάμε για αποδοτικούς αλγόριθμους πούνε πολωνικού χρόνο για αυτόν ακριβώς το λόγο γιατί ακόμα και 100 φορές πιο γρήγορο hardware να έχετε αυτό συμβαίνει κάθε εξαετία τουλάχιστον αυτό έχει δείξει μέχρι τώρα τεχνολογία εσείς μπορείτε μόνο κατά επτά μονάδες μεγαλύτερο προβλήματα να επιλύεται στον ίδιο χρόνο τρεξίματος υπολογιστής πρακτικά τίποτα Γιαννόπουλος είναι κατανοητό αυτό επομένως εκθετικός αλγόριθμους είναι μη αποδοτικός δεν μας ενδιαφέρει και επικεντρωνόμαστε κυρίως στους πολύ γενικούς αλγόριθμους για να δείτε κιόλας κάποιους ενδεικτικούς χρόνους εκτέλεσης σε σχέση με το μέγεθος της εισόδου για υπολογιστή που εκτελεί εκατομμύρια υψηλού επιπέδου πράξη δευτερόλεπτο και ασέβειας μέσα πιο πολύπλοκες βλέπετε ότι οι αλγόριθμοι η πολεμική μπορείτε ας πούμε ακόμα και αλγόριθμους που κατευθύνει τετράγωνο χρόνου νέα σε τρεις ώρες να να αποδώσει λύσεις σε προβλήματα που έχουν μέγεθος 100000 ωραία εάν πάτε σε εξωτικούς αλγόριθμους βλέπετε ότι πάρα πολύ γρήγορα δηλαδή στιγμιότυπα εισόδου με μόλις 30 στοιχεία που θα μπορούσαν να τα κάνει ας Man ταξινόμησης αυτό έκανε και με το χέρι λόγος θα κάνει 18 λεπτά εάν πάτε για στιγμιότυπα εισόδου Νήσων 50 θα κάνει μερικά χρόνια κλπ σε είναι τεράστια διαφορά μεταξύ λοιπόν και τεράστια πρακτική σημασία μεταξύ πολεμικών και εξωτικών αγορές Γι' αυτό σας είπα ότι αυτό που θα συζητήσουμε εδώ και θα επικεντρωθούμε στην εκμάθηση βασικών τεχνικών για το σχεδιασμό αποδοτικό αλγόριθμο που σημαίνει πολωνικών αλγόριθμο έχουν όλα αυτά πάρα πολύ μεγάλη τεχνολογική σημασία δεν έχουν μόνο θεωρητική αξία ωραία επομένως συνοψίζοντας ένα αλγόριθμος είναι αποδοτικός αν έχει πολύ λίγο χρόνο εκτέλεσης και αιτιολόγηση είναι μεγάλη μεγάλη πρακτική σημασία προφανώς υπάρχουν κάποιες εξαιρέσεις θετικών αλγορίθμου που δουλεύουν καλά στην πράξη και αυτό το λέω παραθέτει κα αυτό όμως συμβαίνει σε σπάνιες περιπτώσεις πρώτων και δεύτερων συμβαίνει επειδή κατά μέσον όρο η πολυπλοκότητα αλγορίθμων αυτών είναι εκθετική έτσι αλλά πολυπλοκότητα χειρότερες περιπτώσεις τους είναι μάλλον κατά μέσον όρο είναι Πολυνείκη πολυπλοκότητα του συγγνώμη ενώ κατά στην πολυπλοκότητα χειρότερες περιπτώσεις τους είναι εκθετική και επειδή εδώ επικεντρωνόμαστε στην ανάλυση πολυπλοκότητας χειρότερες περιπτώσεις μας ενδιαφέρει να έχουμε παρουσία στη ΔΕΘ δεν θα συζητήσουμε αυτούς αλγόριθμους απλώς στο λέω για λόγους πληρότητας τώρα επομένως θυμόμαστε τέρας αλγόριθμους αποδοτικός αν έχει πολύ μικρό χρόνο εκτέλεσης αυτό θα το θυμάστε έτσι το δίδαγμα το σημερινό μάθημα το δεύτερο η δεύτερη ερώτηση προσέξτε λίγο είναι μας αρχείο οποιοσδήποτε πολιτικός χρόνος δηλαδή οποιοδήποτε πολωνοί μέτοχοι ναπολέων ογκούμενη τετραγώνου No ένα ετών συνιδρυτής κλπ Γαβρόγλου οποιοδήποτε πολωνοί μου είμαι ικανοποιημένος προσέξτε λίγο ένα άλλο παράδειγμα 0 ότι έχουμε πάλι το κλασικό μας πρόβλημα της ταξινόμησης των στοιχείων και μετράμε τη στοιχειώδη λειτουργία τους γόνους ταξινόμησης είναι σύγκριση μεταξύ στοιχείων έτσι v κυρίως κάνουν συγκρίσεις συγκρούστηκε μεταξύ τους κατακρίνουν τα μικρότερα ποσά μπροστά και τα μεγαλύτερα προς το πίσω μέρος της εισόδου για να βγάλουν την είσοδο σε ποια σειρά του MEGA πείτε λοιπόν ότι διέθετε δύο αλγόριθμους ότι ο αλγόριθμος κάνει δεν κάνει λόγο για συγκρίσεις ο δεύτερος κάνει ν το τραγανό συγκρίσεις για παράδειγμα ο ο δεύτερος είναι πρωτοφανή στόχος να ταξινομήσει κανείς είναι αυτό να κάνει όλες οι μεταθέσεις των των στοιχείων όπως σας είπα πριν που ευτυχώς ο δεύτερος πιο απλός τρόπος πιο εύκολος τρόπος να ταξινομήσει κανείς μια αριθμούς τους είναι μπορεί κανείς να σκεφθεί οριακά μυαλά εμείς δεν μιλάμε για καθαρό χρυσό μιλάμε για οποιοδήποτε έχεις σε έναν πίνακα έτσι αναδιανείμει σου δεν είναι ένα απλό στοιχείο ποιος είναι πιο απλός τρόπος να ταξινομήσουν με και παίζονται όλα κολλάνε σε φθίνουσα όσο δίνονται φθίνουσα ακολουθία συγκρίνεις καθαρό το μυαλό του γιατί κανείς πήρε μεγάλη οκ ναι και κανείς κανείς αντιμετώπισε ένα ζευγάρι και μετά δηλαδή το τοπ πέντε τρεις το 5.3 δύο ένα το έκανες στα 45 2.9 πράγμα δεν είναι απλά δεν δουλεύει έτσι αυτός δεν είναι απλός τρόπος με ο πιο απλός τρόπος να ταξινομήσουν δεν είναι είναι υπάρχει μεταξύ τους Έλληνας αλλά δεν παίρνουν τα διαδοχικά σε Γαλλία πριν και μεγαλύτερες έβγαλε κλπ αυτονομιστών Διαβάστε Κούρκουλου ο πρώτος ένα αλγόριθμος των οποίων εσύ μπορείς να σκεφτείς χωρίς να έχει διαβάσει κάτι έτσι διατρέχει στην είσοδο και βρίσκει το μικρότερο στοιχείων στο κανείς τον Τόλη θα διαφανεί πρώτον διάτρητο αφαιρείς διατρέξει την την υπόλοιπη είσοδο στο μικρότερο στοιχείο του κανείς αυτά που διατρέχει την υπόλοιπη είσοδο το μικρότερο στοιχείο το κάνει στριπτίζ και ούτω καθεξής αυτούς αλγόριθμος όπως θα δούμε έχει πολυπλοκότητα το πράγμα κάνει τετράγωνο συγκρίσεις πολλά για τα συγκρίνει όλα όλα όπως του αλγόριθμου Κοννέκτορας πείτε τώρα ελέγχονται κάθε δύο υπολογιστές έναν που εκτελεί 110000000 πράξεις άρθρο έχω και έναν που εκτελεί 1000 εκατομμύρια έτσι ένα γίγας σύγκριση το θολό Μέγας έναντι ενδεικτικές φορολογίας αλγόριθμο και θέλουμε να ταξινομήσουν εκατομμύρια αριθμούς ωραία ικανό λένε ο χρόνος του αλγόριθμου Α1 στον αργκό υπολογιστή θα είναι αποχή είναι 17 9 πηλό μνημονεύουν 12 στην ακτή διά την ταχύτητά του υπολογιστή δηλαδή αυτό είναι C στοιχειώδεις πράξεις αυτό είναι στοιχείο της πράξαμε δευτερόλεπτο άρα μας δίνει δεύτερον εάν κάνουμε τις πράξεις παρατηρούμε ότι ο αλγόριθμος που κάνει 10 υλοποίηση κρίσης που έχει ένα πολύ ώριμο εξάρτησης από το ν μικρότερο από τον δεύτερο αλγόριθμο για αυτό λέμε πιο αποδοτικός σε 20 δευτερόλεπτα θα τελειώσει που εισπράττει 20 πραγματικά δευτερόλεπτα τέλος πάμε να δούμε τον πόσο χρόνο τελείωση ο δεύτερος αλγόριθμους των γρήγορων υπολογιστών 100 φορές πάλι πιο γρήγορο υπολογιστή ωραία παίρνουμε λοιπόν πάλι τον τετράγωνο ΠΑΣΟΚ βουλή 12 στην ακτή το σωστό τραγούδι και θεωρούμε ότι υπάρχει τ υπολογιστή δηλαδή είναι στοιχειώδεις πράξεις βίας στοιχείων εισπράξαμε ανά δευτερόλεπτο μαζί μ' αυτό ρωτάω που κάνει 16 μισή λεπτά δηλαδή εκατομμύρια φορές πιο γρήγορος υπολογιστής με τον μη αποδοτικό αλγόριθμο το τετραγωνικό ενώ άλλος τελειώνει εισήλθαν σε μερικά δευτερόλεπτα ο άλλωστε 16 μισή λεπτά ένα τελείως καταλαβαίνετε και εάν δεν είχα το ένα εκατομμύριο σήμερα κατά που ζούμε στην εποχή του πολύ μεγάλου όγκου δεδομένων με βιολογικά δεδομένα δεδομένα στον παγκόσμιο ιστό όπου έχει κάτι δισεκατομμύρια σελίδες κανείς θέλει να μηχανισμό της Google η μηχανή αναζήτησης να ψάξει έναν νόμο δισεκατομμυρίων σελίδων ιστοσελίδων ιατρούς η απάντηση ωραία το 10 στην Αθήνα ο ερωτών εκατομμύρια λοιπόν αν είχαμε κάνει στο 10 στη δομή που δεν είναι πάντα κακό μηχανάκι κατά των αστυνομικών και πάρετε την ίδια πάλι τον ίδιο την συλλογισμό πάμε να δούμε λοιπόν ο πιο γρήγορος αλγόριθμους τους στον πιο αργό υπολογιστή πιο αποδοτικός δηλαδή Αλαβάνο η εξάρτηση από τον είναι μικρότερες δυνάμεις Γι' αυτό λέμε πιο αποδοτικό τι κάνω πάλι τις πράξεις δηλαδή παίρνουμε τον τον αριθμό των συγκρίσεων βάζουν όπου ν το 10 στην 7η και δίνουμε μια μάχη τον υπολογιστή που είναι συγκρίσεις ανά δευτερόλεπτο αυτό θα μας δώσει δεύτερον το χρόνο πρώτο πραγματικό χρόνο εκτέλεσης του υπολογιστή ωραία αυτό θα μας δώσει κάτι λιγότερο από τέσσερις λεπτά Νάξου πήγαμε σε 10 φορές μεγαλύτερο μέγεθος εισόδου είναι και παλαιός πολεμιστής ωραία χάνονται τέσσερις λεπτά δεν κάναμε κάτι μερικά δευτερόλεπτα πορεία τους αλλά και επαναλαμβάνοντας με τον πιο αργό εάν κάνουν την ίδια άσκηση με τον νέοι το λιγότερο αποδοτικό αλγόριθμο πολιτικό πράγμα που κάνει το τραπεζικό χώρο χρόνο και τον βάλω στον πιο γρήγορο που κάνει 101000000000 θα σταθούμε εδώ θα δείτε ότι τελειώνει μετά από μιάμιση ημέρα πλέον έτσι με τα δύο αυτά παραδείγματα θέλω να σας πω το εξής και κάποτε θα κλείσουμε το σημερινό μάθημα να θέλω να σας πω το εξής ότι ήδη ως σχεδιασμός και η ανάπτυξη και η ανάλυση αποδοτικό αλγόριθμο έχει πολύ μεγάλη τεχνολογική σημασία το είδαμε και στη σύγκριση μεταξύ πολεμικών και αυθεντικών αλγόριθμο αλλά το βλέπουμε και στη σύγκριση μεταξύ πολεμικών αλγορίθμων που ένα εκ που έχουν διαφορετικές εξάρτησης από τον ν ως προς τον εκθέτει βλέπετε ότι στην ένα περίπτωση προφανώς έτσι αν τον αλφάνο τον παλιό στο γρήγορο υπολογιστή τελείωσε μερικά δευτερόλεπτα όλα βλέπετε λοιπόν ότι αποδοτικού ότι μόνο του το χαρτί αυτό θέλω να σας ένα σημερινή διάλεξή μην νομίζετε ότι μόνο με το hardware μπορείτε να λύσετε όλα τα προβλήματα σας δεν λύνονται όλα τα προβλήματα με τον αγοράζετε διαρκώς καινούργιο υλικό χρειάζεται μια ευφυής ιδέα πίσω απ' το λογισμικό να πείσω να τρέχει αυτή πάνω στο υλικό αυτό για να μπορεί να το κάνει απόδοση για να αλλιώς θα περιμένετε μέρες ώρες και χρόνια για να πάρετε απάντηση ακόμα και σε προβλήματα εισόδου που έχουνε θα έλεγα που δεν είναι πολύ μεγάλα επομένως η απάντηση στο αν μας αρκεί οποιοσδήποτε πολιτικός χρόνος είναι όχι μόνο καλό μεσημέρι τα λέμε αύριο |
| _version_ |
1782816453775327232 |
| description |
Εισαγωγικά - Βασικά Στοιχεία Σχεδιασμού και Ανάλυσης Αλγορίθμων (μέρος Β): Την προηγούμενη φορά είδαμε τι σημαίνει αποδοτικό αλγόριθμο και για ποιο λόγο θα επικεντρωθούμε στη λεγόμενη ανάλυση πολυπλοκότητας χειρότερες περιπτώσεις το μόνο που δεν έχουμε συζητήσει σημαντικό βεβαίως είναι το μοντέλο αξιολόγησης σε ποιο μοντέλο μετράμε την αποδοτικότητα και τι σημαίνουν στοιχειώδεις πράξεις στο μοντέλο αυτό με δύο Προσέξτε λίγο αυτό είναι πάρα πολύ βασικό για να καταλάβετε το υπόλοιπο του μαθήματος αν δεν είναι κάτι που δεν είναι τελείως σαφές παρακαλώ πολύ όπως είπα μη διστάσετε να τα το λεγόμενο μοντέλο μηχανής τυχαίας προσπέλασης είναι ουσιαστικά μου πολύ κοντά στο νου όπως πραγματικά χρίστηκε χτίστηκαν υπολογιστές δεν την εμφάνιση των πολλοί πίνουν φίλιππα υπολογιστών δηλαδή έχουμε μια κεντρική μονάδα επεξεργασίας όταν κανένας από τους η οποία έχει πρόσβαση σε μια μίνι που μπορεί να έχει έναν απεριόριστο αριθμό ωστόσο δε μας ενδιαφέρει και πρόσβαση σε κάποιους καταχωρείται μας και αυτή η κεντρική μονάδα επεξεργασίας μπορεί να εκτελεί λεγόμενος εντολές μηχανής ωραία τις οποίες δηλαδή ότι οι εντολές που μάθατε στη γλώσσα σε λοιπόν κανένας από τους το μοντέλο αυτό προτού εισιτήρια και κύριοι βλέπετε δεξιά σίγουρα στην καταγωγή αλλά ουσία μεγάλωσε σπούδασε και έδρασε στην αμερική δολοφόνο έναν έχει κάνει πολλά σημαντικά πράγματα στη ζωή του ένα από αυτά είναι το μοντέλο αρχιτεκτονικής των των υπολογιστών το δεύτερο είναι αντίθετα από τους πατέρες της θεωρίας παιγνίων μια ακόμα και χάνεται κ.ά. αν πάτε στην ιστοσελίδα του αυτό μας ενδιαφέρει λοιπόν εδώ είναι ότι έχουμε ένα ένα μοντέλο Υπολογιστικής μηχανής θεωρητικό βέβαια απαλλαγών μοιάζει πάρα πάρα πολύ με το μοντέλο το οποίο έχουν οι σύγχρονοι υπολογιστές ένα κεντρική μονάδα επεξεργασίας που έχει πρόσβαση σε έναν απεριόριστο αριθμό θέσεων μνήμης και σε ένα ευκαταφρόνητες μια ένοπλος Καλαβρύτων τώρα θα πρέπει να ξέρετε ότι εκτός από εντολές μηχανής αυτό που θέλω να συζητήσετε και να καταλάβετε είναι το εξής ότι το μέγεθος της λέξης μνήμης έχει πολύ μεγάλη σημασία έτσι ώστε να μετράμε σωστά την απόδοση ένα αλγόριθμου ξέρετε ότι όταν έχουν μεταβληθεί b της σάμι σε ένα θέση μήνυση μπορώ να παραθέσω δυο στην πλήρη στοιχεία αυτό θα πρέπει να λέγεται μαθαίνουμε είναι μια χαρά εάν το θυμάστε δεν τίποτα Λίβας βάση δύο γιατί γιατί έχουμε το δυαδικό σύστημα συμπολεμιστές στο δεκαδικό σύστημα για παράδειγμα όταν έχουμε τρεις ψηφία μπορούν να αναπαραστήσουν 10 στην τρίτη βάσει του συστήματος στο πλαι των ψηφίων διαφορετικούς αριθμούς πορεία από το χίλιους δηλαδή από 0 μέχρι 999 είναι 1000 τ.μ. αντίστοιχα μπορούμε λοιπόν με τα λόμπι για να αναπαραστήσουν δύο 61 στοιχεία γιατί το λέω αυτό διότι όταν έχουν ένα πρόβλημα το οποίο ταξινόμηση στοιχείων έχουνε στοιχεία ένα μικρό γλυκό θα πρέπει το πλήθος των στοιχείων αυτών αναπό να μπορεί να παρασταθεί στη μνήμη του υπολογιστή δηλαδή θέλω να ταξινομήσουν 100000 αριθμούς τελών ταξινόμησης το ένα εκατομμύριο αριθμούς εκατομμύρια ΑΦΜ όλων των φορολογουμένων Σαββίδη χώρας 27000000 θάνος ταξινόμηση πορεία δηλαδή θα αφού τόνοι θα πρέπει να μπορεί να παρασταθεί έτσι δηλαδή θα πρέπει να παραστεί η ποιος τα λέει αυτά στοιχεία το πλήθος των στοιχείων αυτό σημαίνει αν πάρουμε λογαριασμούς των δύο μερών λογαριασμό Novasports δύο σημαίνει ότι χρειάζομαι λογαριασμού με βάση το δύο μ BBC για να αναπαραστήσουν ένα πλήθος ν αριθμό καταλαβαίνουμε 1000 όμως σχέση μεταξύ τάβλι και δύο συναυλίες είναι εκθετική δηλαδή πάνω από έναν αριθμό κι αυτός αριθμός τάφων στον εξακριβώσατε αριθμού τση μιλεί η απόσταση μεταξύ στάβλου και βυσσοδομούν είναι εκθετική ετσι εθνική σύνταξη οι ίδιες να δουν έτσι συμβαίνει μεταξύ λογαριασμό του ν και του ν δηλαδή όλο το τόνοι είναι εκθετικά μεγαλύτερο λογαριασμό υπάρχει θετική αποστάσεις σας τα λέω όλα αυτά λείπουν για να σας πω ότι όταν έχουν μέγεθος εισόδου μ θα πρέπει οι λέξεις είναι εμείς να αποτελούνται από λογαριασμό του ν με τις δεν χρειάζομαι παραπάνω δεν βγάζουμε δηλαδή να μη μπει για να παραστήσουν λίγα πράγματα αλλά πολύ μικρότερο αριθμό ψηφίων πανό μπαλόνια να αναπαραστήσουν μας δηλαδή για να παραστεί σε αριθμούς ούτε καν οικοσύστημα από τον δεν μέχρι το 999 χρεώσουν τρεις ψηφία δε χρειάζομαι Νάρκωσαν μειοψηφία αυτοτελώς τώρα για να γράψω τον αριθμό εκατομμύρια έτσι γίναμε δηλαδή τους πόσα εκατομμύρια αριθμούς χρειάζομαι έξι ψηφία δε χρειάζομαι 1000100 του αξιόλογα ρυθμός του 10 του πλήθους τον αριθμό των εκατομμύρια αυτό λέμε εδώ καταλαβαίνουμε φορέα εκτός από το μεγάλο σου δεν υπάρχουν προβλήματα που έχουνε και τιμές στοιχείων εισόδου κεφαλαίων δηλαδή δεν είναι μόνο ότι έχω να ταξινομήσουν ένα εκατομμύριο αριθμούς αλλά θέλω να δω και τείνουμε να ταξινομήσει ωραία είναι πενταψήφιο 16100 ψηφιακά από διακόσιους γάμους στοιχεία αποτελούνται εδώ κάνουμε λοιπόν προφανώς λοιπόν με την ίδια συλλογιστική όταν έχω ένα στοιχείο το οποίο έχει τιμή ν κεφαλαιο χρειάζεται λογαριασμός του ν κεφαλαιο b για να παρασταθεί και εγώ κάνω την υπόθεση ωραία ότι αυτά τα δύο σχετίζονται με πολύ κυνικό τρόπο κρατών κεφάλαιο δεν μπορεί να είναι μεγαλύτερο από το πλήθος των στοιχείων υψωμένο στην C Σιμόπουλος είναι μια σταθερά δηλαδή έχουν ταξινομήσεις εκατομμύρια αριθμούς και έπειτα τους είναι οι δύο αυτοί οι αριθμοί δεν είναι παραπάνω από την από 1000010 στην ακτή οι αριθμοί αυτοί δεν είναι πάνω από 10 στη 12η για παράδειγμα έτσι από αν πως την τρίτη θα 10 στην 18η έτσι είναι μια λογική υπόθεση αυτή δεν μπορεί να είναι εξωτικά μεγαλύτερος δεν μπορεί να να ξανά εκατομμύρια βαθμούς και να ήδη οι τιμές που αναπαριστούν άνετο δύο στην ανά εκατομμύριο για παράδειγμα επομένως με βάση λοιπόν ότι τον κεφάλαιο είναι κάποιο κάποια δύναμη του ν όπου τους είναι μια σταθερά και αυτό πρέπει επίσης να μπορεί να παρασταθεί στη μνήμη του υπολογιστή δηλαδή πρέπει κι αυτό να ενώσουμε δύο στην παύλου ανταμοιβή λέξη γίνει μας τότε σημαίνει ότι το ήλεγξε μίνι Λαυρίου είναι ένα αν πάρετε λογαριασμούς των δύο αυτών μερών τόση γιατί δεν τονίζει στην δύση είναι ίσο με δύο στην Danone αυτό σημαίνει ότι αν πάρω λογαριασμούς και των δύο μερών με βάση το δύο εις τον οποίον δίκτυο θα σταθώ παραλείπω γιατί όλοι οι λογαριασμοί μας θεωρούμε την απόφαση των δύο όσα λέγονται ειδικά τώρα από βασικές διότι στον αριθμό που εκθέτεις εδώ πάει μπροστά και εκθέτει Ευρωπαϊκή πίστη μπροστά και ευρωομόλογα αγνώστου δύο με βάση τους δύο κάνει μονάδα επομένως το ταμπλό είναι ίσο με το συν και φίλων ν όλα αυτά σας τα λέω για να σας πω το εξής ότι εδώ λοιπόν για είσοδο ένα μέγεθος εισόδου πλήθους είναι μικρό και τιμών στοιχείο είναι κεφάλαιο χρειαζόμαστε λέξεις μνήμης πουλάνε ένα σταθερά επί λογαριασμός το πλήθος των στοιχείων b τόσα δείτε επιτρέπουν σε ένα λέξη ναι εμείς και ουσιαστικά αυτό θα το μετρήσουμε σαν ένα επίσης στοιχειώδη πράξη δηλαδή επαναλαμβάνω δεν μπορεί η δεκαδικά συστήματα υπάρχουν πάρα πολλά διάδικο ξέρετε τριαδικό δεκαδικό 16 άδικο μπορεί να υπάρχει το μοναδιαίο εσείς δηλαδή έχω ένα σύμβολο αυτό ας πούμε και μπορώ να παραστήσουν τους αριθμούς να τον αριθμό τρεις τραγούδια σύμφωνα τον αριθμό επτά γράφω καταπίεση έτσι αθύρματα στο ένα εκατομμύριο θα μπορούσα να γράψω ενα εκατομμύριο παιδιά σύμφωνα έτσι δεν είναι αυτό είναι το b αυτό δεν μας το μοναδικό σύστημα κυβερνά εκεί θέλω να σας εφιστούν την προσοχή και δε μπορούμε να πούμε ότι τον αριθμό εκατομμύρια σε οποιοδήποτε σύστημα αναπαραστάσεις έστω και στο μοναδιαίο μπορώ να τον εγγράψουν σε μια θέση μήνυση να τον διαβάσω διάθεση μνήμης με ένα στοιχειώδη πράξεις μπορώ να το κάνω αυτό σε λογαριασμό της αξίας έτσι του ν μικρό είναι κεφάλαιο MB στο δυαδικό σύστημα γιατί τόσα χρειάζονται επομένως επαναλαμβάνω στη ν π ως έχει το στοιχειώδες υπολογιστικό βήμα σημαίνει ότι όταν έχω ένα στιγμιότυπο εισόδου με πλήθος στοιχείων μικρό αγγλικό με μέγιστη τιμή στοιχειώνει κεφάλαιο χρεώνουν ένα μονάδα χρόνου για κάθε βασική λειτουργία δηλαδή αριθμητικές πράξεις λογικές πράξεις συγκρίσεις καταχωρήσεις και επίσης ένα μονάδα χρόνου για προσπέλαση στη μίνι είτε αυτοί είναι ανάγνωση είτε είναι έγγραφη αλλά ένα σταθερού αριθμού λέξεων μνήμης των λογαριασμών ν b όχι έναν απεριόριστο αριθμό πομπή καταλαβαίνουμε πόσο αυτή είναι μια λογική υπόθεση που κάνουμε και θα πρέπει πάντα να το θυμόμαστε τώρα βέβαια μπορεί κάποιος να πει ότι ισότητα γιατί Χρόνης σόργο ένα μονάδα χρόνου για όλες αυτές τις πράξεις ξέρουν πολύ καλά και πολλαπλασιασμός διαίρεση είναι κοστίζει περισσότερο χρόνο από ότι πρόσθεσε ωραία η σύγκριση δύο αριθμών προσθαφαιρέσεις συνάντησαν το υπόλοιπο είναι μεγαλύτερο του ένα μικρότερου ίσως να κάνει έτσι η σύγκριση επίσης είναι πολύ πιο χρονοβόρα αποτελεί πρόσθεσε δεν πειράζει επειδή δομεί μιλάμε για πράξεις στις τάξεις στα σύγχρονα συστήματα των δυναμικών την είναι ακόμα και το χαμηλότερο πάρτε εδώ σαν στοιχειώδη πράξη και μέγιστη σε χρόνο λειτουργίας δεν μας πειράζει έτσι αυτό το κάνουμε για να διευκολυνθούν με καλύτερα στους υπολογισμούς μας για να μην έχουμε και λέμε τόσο πρόσθεσε ωστόσο διαίρεση κλπ δεν μας ενδιαφέρει παίρνουμε λοιπόν τα στοιχειώδη υπολογιστική πράξη τη μέγιστη ας πούμε σε ένα νοσοκομείο πράξη από αυτές έχει και αυτό τη βαφτίζουμε στοιχειώδη πράξη εξάλλου αυτό συνάδει και με το μοντέλο που σας είπα τις χειρότερες περιπτώσεις και τώρα η επιθυμία και μάγος που λέγαμε πριν μεταφράζεται σαν χρονική πολυπλοκότητα η αντίστοιχη χωρικοί πολυπλοκότητα σαν μια συνάρτηση του πλήθους της εισόδου και του λογαριασμού του κεφαλαίου των τιμών δηλαδή που αναπαριστά ίσως δηλαδή μας να το πω καλύτερα εδώ θα έχουμε λοιπόν ότι ισχύει αυτό ότι χρονική θέλουμε χρονική συνάρτηση να είναι ένα συνάρτηση δύσοσμο αυτής κινητών πραγμάτων επιλογών αριθμού του μια χαρά σε κοινή θέσεων ν κρήτης θα κάνει ας πούμε αλγόριθμος αυτός στοιχειώδεις πράξεις ωραία για παράδειγμα δε δηλαδή δεν θέλουμε να πούμε ότι δεν θέλουμε να πούμε ότι αλγόριθμους μας θα κάνει τρεις ν τετραγώνου επί κεφαλαίου πράξεις αυτό δεν το θέλει θέλουμε δηλαδή αυτό δεν θα θέλουμε οι εξαρτήσεις διαθέτουν το πλήθος ήδη τις τιμές όπως των κεφαλαιαγορών είναι ως προς τον λογαριασμό των γιατί τότε μετραει σωστά μου τότε είναι σωστή αξιολόγηση και το θέμα λοιπόν είναι πλέον τη μορφή έτσι μια άλλη μορφή συναρτήσεις θα μπορούσα να κάνω που είναι επίσης σωστή το καυτό μήνα έξοδό μου δύο τη στιγμή επί λογαρισμούς του ν κεφαλαιο στην τριετία και αυτή είναι ένα συνάρτηση κλοπή πάλι πληροί αυτές προϋποθέσεις δηλαδή είναι ένα συνάντηση το σάββατο από τον από κάποια δύναμη του ν από κάποια δύναμη του λογαριασμού του ν κεφαλαιο τώρα το βασικό ερώτημα είναι τι μορφή πρέπει να έχει συναντήσεις της προσέξτε λίγο ο πιο απλός τρόπος για να επιλύσετε ένα πρόβλημα είναι η λεγόμενη μέθοδος της ωμής βίας δηλαδή θέλετε να κάνετε Ταξινόμηση ένα αριθμό μπορείτε να παράγετε όλες τις μεταθέσεις των αριθμών που είναι παραγωγικός το πλήθος ωραία να διαφυλάξετε και να Δείτε ποιες από αυτές είναι σε ταξινομεί σειρά και να πείτε έκαναν την ταξινόμηση των αριθμό συνήθως λοιπόν αυτό δηλαδή που κάνουμε είναι έλεγχο όλων των δυνατών λύσεων του προβλήματος και επιλέγουμε εκείνη που μας δίνει την επίλυση μου που θέλουν αυτό παίρνει εκθετικά μεγάλο χρόνο ακόμα χειρότερο τον παραγωγικό είναι είναι κάποια βιώσιμη λιωμένη ακόμα χειρότερα από το διαστημικό και όπως θα δούμε έχει πρακτική αξία μηδαμινή φορέα και πολύ συχνά μας δημιουργεί πολύ μεγάλα προβλήματα απλά όταν μιλάμε όταν λοιπόν μιλάμε για επιθετικό για υπερ υπερ εκθετικό χρόνου αλγορίθμου μιλάμε για πολυπλοκότητα στοιχειωδών βημάτων που χει μορφίνη σταθερά επί κάποια άλλη σταθερά α δύο για παράδειγμα υψωμένο εις Ξενία δυνάμει του ν επί ένα δίνανε του λογαριασμού του ν ωραία για παρά παράδειγμα όταν αυτό εδώ ένα άλλο παράδειγμα τέτοιας συνάντησης είναι αυτή εδώ ορεινή παραγωγικό πούνε δυόσμου επιλογών αυτήν ένα είπε θετική συνάρτηση πρακτική πολύπλοκων ράφτη επαναλαμβάνω η γενική της μορφή τώρα όταν μιλάμε για πολεμική πολυπλοκότητα μιλάμε για μια συνάρτηση δύο είναι πάλι μια σταθερά επί κάποιο κάποια δύναμη κάποιοι πολεμούν δι' μόνον μάλλον του ν υψωμένες την διετή λογαριασμό του ν υψωμένο σε κάποιο δυναμικά όπως των ΔΟΥ Μ3 η πράγματα όλο το έθνος του ν το 4G λογαριασμούς για η όπως λέει είναι 20 χρονος έχει αυτή την επιθυμία την λεγόμενη επιθυμητή ιδιότητα κλιμάκωσης τι σημαίνει αυτό ωραία σημαίνει το εξής ότι ευρώ τι σημαίνει ότι ιδιότητα κλίματος ότι εγώ θέλω όταν μεγαλώνει το μέγεθος της εισόδου διπλασιάζεται τριπλασιάζεται να ξέρω ότι ο χρόνος θα τους θα πολλαπλασιαστή επίσης κατά ένα σταθερό παράγοντα όχι κατά κάποιον εκδοτικό παράγοντα κάποιο αυθαίρετο πάνω από σχεδόν κανένα είσπραξη πετάξτε τότε έχετε προβλήματα για τους μ αυτό που είπαμε που επιλύεται συγχρόνως η ποινή στην διαδηλωτών αριθμός του μισθού τους μένουν στην κ εάν αυτός το ΓΔ βάλτε τώρα στα δόντια όπου η διώνη δηλαδή διπλασιάζεται είσοδος τι αποτέλεσμα θα δώσει αυτός αλγόριθμους έτσι αν έχουμε βρει τόπος στοιχειώδης πράξη κάνει θα δώσεις παραπάνω αναλογούν βάζουμε το βιώνει όπου μας βιώνει και προβλέπεται ότι εδώ επειδή το δύο θα υψωθεί εδώ στην τύχη θα βγει δύο της την αυτόνομη πρώτον διότι στην δύση είναι ένα περιβάλλον VR δηλαδή επιμείνει στην την γενιά στην παρέμβασή επί των λογαριασμός του ν λογαριασμούς του του δύο εδώ μπορεί να εξαλειφθεί επομένως αυτό είναι υπονόμευση δυναμικότερο κάνεις πράξεις μπορείτε να το Δείτε όπου εάν λοιπόν αυτή σταθερά εδώ που βλέπουν εδώ βλέπετε ότι και πάλι την ίδια μορφή κάτω εκτός από αυτόν εδώ τον πολλαπλασιαστικό παράγοντα που βλέπουν διοριστεί συναντώνται όμως μένει σταθερό είναι το δύο και πάρα πάρα το διολισθαίνει BC 9ο δύο στην δύο το 2008 για το συγκεκριμένο παράδειγμα άρα εδώ ναι διπλασιάζεται είσοδος και αντίστοιχα το πουλί οκταπλάσιες το χρόνος αλλά έχουν ένα όπου υπάρχει ένα σταθερός παράγοντας 10 παλαιών ετών δ κεφαλαίο δεν εξαρτάται από το μέγεθος της εισόδου εξαρτώνται μόνο από τις σταθερές από κάποιες σταθερές σταθερές που υπάρχουνε στην ανάλυση χρονικής πολυπλοκότητας To συγκεκριμένο αλγόριθμο το καταλαβαίνουν αυτό επαναλαμβάνω στην ιδιότητα της κλιμάκωσης λέμε το μέγεθός μας είναι απόλυτα πάει βιώνει πάει τρεις Άννη δηλαδή πολλαπλασιάζεται επί κάποιον σταθερό παρά θα θέλουμε το ίδιο να συμβαίνει και ως προς τον χρόνο δεν θέλουμε πάντα να ακολουθεί αντίστοιχη κλιμάκωση δηλαδή διπλασιασμός σου διπλασιασμό του χρόνου θα ήταν το ιδανικό αυτό μπορεί να συμβαίνει αυτό το θέμα όμως εδώ είναι ότι υπάρχει ένα σταθερός παράγοντας δ κεφαλαίο όπως βλέπετε από την ανάλυση όμως κατά τον οποίον μεγαλώνει η χρονική πολυτέλεια κότα όταν διπλασιάζεται είσοδος όταν διπλασιάζεται αντίστοιχα αυτό μας είναι αρκετό και μάλιστα λέμε έναν αλγόριθμο την πόλη νίκου χρόνου ανίσχυροι αυτοί οι παραπάνω ιδιότητες κλιμάκωσης για παράδειγμα αυτό δεν μπορεί να συμβεί στους έχει ειδικούς αλγόριθμους αυτή ιδιότητα κύματος μπορείτε να δοκιμάσετε θα δούμε για παράδειγμα σε λίγο που Manager θα δούμε τώρα το παράδειγμα υπάρχει κάποια πορεία μέχρι το παράγων αυτές είναι δύο γενικές μορφές εκδοτικών και πολεμικών συναρτήσεων και πλέον λέμε πολιτικού χρόνου αλγόριθμο εάν έχει τη συγκεκριμένη ιδιότητα κλιμάκωσης αλλιώς έτσι λίγο χρόνο ένα διαφορετικός ορισμός τώρα για να καταλάβετε την διαφορά που έχουνε η θετική άποψη που είναι τους αλγόριθμους ως προς το χρόνο πείτε ότι έχετε είναι σημαντικό να καταλάβετε αυτό παρανομία πείτε ότι έχετε έναν υπολογιστή όποιος θέλει ας ένα στοιχειώδεις λειτουργίες του δεύτερον φορέων και λέμε ότι το γράφημα έξι ένα ώρα και λέμε ότι αυτός υπολογιστής πόσο μεγάλα στιγμιότυπα λύνει αν τον αφήσουμε ένα δεδομένη προβλήματος τον αφήσουμε απέξω για ένα ώρα πείτε λοιπόν ότι έχουμε ένα πολύ γενικό και ειδικό αλγόριθμο ποιητών και πολεμικός έχει ως προς την χειρότερη περίπτωση αριθμός στοιχείων των πράξεων η αναγνω εκθετικός δύο στη ν και ότι αν αφήσουμε αυτό τον υπολογιστή που εκτελεί εσένα στοιχειώδη λειτουργία στην χώρα το σώβρακο μυστηριωδώς λειτούργησε τον χρόνο να τρέξει για ένα ώρα ότι ο πρώτος κατηγορούμενος λύνει στιγμιότυπα μέγεθος 9 ένα μικρό και δεύτερος μια ανακεφαλαίωση το ερώτημα που θέλουμε να απαντήσουμε ως προς την κλιμάκωση είναι το εξής Επιτροπή εσείς παίρνετε έναν υπολογιστή εκατό φορές πιο γρήγορο δηλαδή βρισκόμαστε στο 2014 παίρνω τώρα ένα καινούριο υπολογιστή φέτος δεν θα υπολογιστεί που είχε έξω εγώ κάποιος φίλος σας κάποιος γονιός σπουδών αγόρασε το 2007 2008 αυτός πρώτος δηλαδή έξι χρόνια παλαιός κι αυτός σε νέο σούπερ ντούπερ σύγχρονους υπολογιστές όποιος είναι κάνει εκεί είναι 100 φορές πιο γρήγορος όπως στο hardware για τον σε σχέση με τον παλιό τον υπολογιστή και το ερώτημα που θέλουμε να θα θέσουμε είναι ωραία εγώ πήρα έναν καινούργιο υπολογιστή αφού είναι πολύ 100 φορές πιο γρήγορος προφανώς θα μπορεί να λύσει σε μια ώρα μεγαλύτερα στιγμιότυπα από μεγέθους ένα ένα σε σχέση με τον ανταγωνισμό δεν είναι αφού οι πιο γρήγορος και τρέχει σε μια ώρα θα θα μπορεί να λύσει μεγαλύτερα στιγμιότυπα στο ίδιο πρέπει τον ίδιο δηλαδή δολάρια μεγαλύτερο από το ένα Νοεμβρίου και των ακροδεξιών το ερώτημα είναι πόσο μεγάλη θα είναι η στιγμή ωραία τι κάνουμε για να μπορούμε να κάνουμε το εξής λένε όλα λόγω στον πολυπλοκότητα των εδώ των στοιχειωδών πράξεων για τις διαφορετικές εισόδους ν 2ετών και 9 να φανεί διότι πράγματι λένε ένα τετράγωνο πρέπει ναναι ίσως με το λόγω των διαφόρων ταχυτήτων στους υπολογιστή των επεξεργαστών μιλάτε αφού αυτός λόγος να κλείσουν 100 κούκλες δύο είναι 100 φορές πιο γρήγορα από τους αν κάνουμε λοιπόν εδώ τις πράξεις δηλαδή παρόλες τις ρίζες αυτός λόγος είναι 100% κάνει 10 επομένως μπορούμε να λύσουμε τον στιγμιότυπα προβλήματος στο νέο υπολογιστή με τον πολιτικό αλγόριθμο που είναι 10 φορές μεγαλύτερα σε ένα ώρα από την Προύσα αναλύσουμε το μπάλωμα σχολή στη που το αγόρασαν στα μαθητικά μας χρόνια από το 2008 ο δηλαδή και πήραμε καινούργια υπολογιστή που είναι κάτοχος του γρήγορος αλγόριθμος που για την συγκεκριμένη Πολύτροπον η μπορεί επίσης να λύσει 10 φορές πιο γρήγορα μεγαλύτερα στιγμιότυπα λιανική που σε μια ώρα ταξινομούν σαμε τώρα 10000000 βαθμούς τώρα μπορούμε να αξιοποιήσουμε 100000000 με τον υπολογιστή είναι πάμε να κάνουμε την ίδια αίσθηση στον εκθετικό αλγόριθμο δηλαδή δεν σε ένα ώρα ο εκθετικός αλγόριθμος τον παλιό υπολογιστή λένι στιγμιότυπο μεγέθους ένα ένα κεφάλαιο με τον εκατό φορές πιο γρήγορο υπολογιστή αφού είναι εκατό φορές πιο γρήγορος ένα ώρα πίσω θα εξαντλήσει πολύ μεγαλύτερη στιγμή έξι η διαδικασία είναι ακριβώς ίδια αναλογία δηλαδή θα πάρω το λόγω των πολύπλοκων ειδών που πρέπει να λύσουμε το λόγο τον της ταχύτητας των επεξεργαστών μόνο που εδώ την εκθετική συνάρτηση έχουν διαφορετικό είδος πράξεων θα πρέπει δηλαδή το δύο στη Ν2 μειώνει έναν ίσο με 100 που σημαίνει ότι όταν λογαριασμοί ίσως και τα δύο μέλη των δύο τόνοι βιομηχανία να κάνει λογαριασμό στο κάτω που είναι διάδικος λογαριασμούς 100 μικρότερος η που σημαίνει ότι στο εκατό φορές πιο γρήγορο hardware με το ξωτικό αλγορίθμου μπορώ να λύσω επτά στιγμιότυπα εισόδου που είναι μόνο κατά επτά μονάδες Μιχαλίτσα δηλαδή εκεί που με τον αλγόριθμο σας στον βαλέσα υπολογιστή στη ένα ώρα μείνατε έξω λόγω τάξη μούσα 100000 στοιχεία δικός μου μου τώρα στο 100 φορές πιο γρήγορο σούπερ ντούπερ υπολογιστή μόλις αγόρασα εμπορικά Ταξινόμηση ένα ώρα 100007 στοιχεία καταλαβαίνετε λοιπόν ότι δεν γίνεται και τίποτα και κ γιώργος χώρα επομένως το πρώτο μάθημα εδώ είναι ότι η ωμή βία δηλαδή η πρώτη ιδέα που μπορεί να σκεφτεί για να επιλύσετε κάτι μπορεί να μη δουλεύει και δουλεύει ειδικά αν οδηγεί σε εκθετικό αλγόριθμο για το λόγο που ανέφερε για αυτό μιλάμε για αποδοτικούς αλγόριθμους πούνε πολωνικού χρόνο για αυτόν ακριβώς το λόγο γιατί ακόμα και 100 φορές πιο γρήγορο hardware να έχετε αυτό συμβαίνει κάθε εξαετία τουλάχιστον αυτό έχει δείξει μέχρι τώρα τεχνολογία εσείς μπορείτε μόνο κατά επτά μονάδες μεγαλύτερο προβλήματα να επιλύεται στον ίδιο χρόνο τρεξίματος υπολογιστής πρακτικά τίποτα Γιαννόπουλος είναι κατανοητό αυτό επομένως εκθετικός αλγόριθμους είναι μη αποδοτικός δεν μας ενδιαφέρει και επικεντρωνόμαστε κυρίως στους πολύ γενικούς αλγόριθμους για να δείτε κιόλας κάποιους ενδεικτικούς χρόνους εκτέλεσης σε σχέση με το μέγεθος της εισόδου για υπολογιστή που εκτελεί εκατομμύρια υψηλού επιπέδου πράξη δευτερόλεπτο και ασέβειας μέσα πιο πολύπλοκες βλέπετε ότι οι αλγόριθμοι η πολεμική μπορείτε ας πούμε ακόμα και αλγόριθμους που κατευθύνει τετράγωνο χρόνου νέα σε τρεις ώρες να να αποδώσει λύσεις σε προβλήματα που έχουν μέγεθος 100000 ωραία εάν πάτε σε εξωτικούς αλγόριθμους βλέπετε ότι πάρα πολύ γρήγορα δηλαδή στιγμιότυπα εισόδου με μόλις 30 στοιχεία που θα μπορούσαν να τα κάνει ας Man ταξινόμησης αυτό έκανε και με το χέρι λόγος θα κάνει 18 λεπτά εάν πάτε για στιγμιότυπα εισόδου Νήσων 50 θα κάνει μερικά χρόνια κλπ σε είναι τεράστια διαφορά μεταξύ λοιπόν και τεράστια πρακτική σημασία μεταξύ πολεμικών και εξωτικών αγορές Γι' αυτό σας είπα ότι αυτό που θα συζητήσουμε εδώ και θα επικεντρωθούμε στην εκμάθηση βασικών τεχνικών για το σχεδιασμό αποδοτικό αλγόριθμο που σημαίνει πολωνικών αλγόριθμο έχουν όλα αυτά πάρα πολύ μεγάλη τεχνολογική σημασία δεν έχουν μόνο θεωρητική αξία ωραία επομένως συνοψίζοντας ένα αλγόριθμος είναι αποδοτικός αν έχει πολύ λίγο χρόνο εκτέλεσης και αιτιολόγηση είναι μεγάλη μεγάλη πρακτική σημασία προφανώς υπάρχουν κάποιες εξαιρέσεις θετικών αλγορίθμου που δουλεύουν καλά στην πράξη και αυτό το λέω παραθέτει κα αυτό όμως συμβαίνει σε σπάνιες περιπτώσεις πρώτων και δεύτερων συμβαίνει επειδή κατά μέσον όρο η πολυπλοκότητα αλγορίθμων αυτών είναι εκθετική έτσι αλλά πολυπλοκότητα χειρότερες περιπτώσεις τους είναι μάλλον κατά μέσον όρο είναι Πολυνείκη πολυπλοκότητα του συγγνώμη ενώ κατά στην πολυπλοκότητα χειρότερες περιπτώσεις τους είναι εκθετική και επειδή εδώ επικεντρωνόμαστε στην ανάλυση πολυπλοκότητας χειρότερες περιπτώσεις μας ενδιαφέρει να έχουμε παρουσία στη ΔΕΘ δεν θα συζητήσουμε αυτούς αλγόριθμους απλώς στο λέω για λόγους πληρότητας τώρα επομένως θυμόμαστε τέρας αλγόριθμους αποδοτικός αν έχει πολύ μικρό χρόνο εκτέλεσης αυτό θα το θυμάστε έτσι το δίδαγμα το σημερινό μάθημα το δεύτερο η δεύτερη ερώτηση προσέξτε λίγο είναι μας αρχείο οποιοσδήποτε πολιτικός χρόνος δηλαδή οποιοδήποτε πολωνοί μέτοχοι ναπολέων ογκούμενη τετραγώνου No ένα ετών συνιδρυτής κλπ Γαβρόγλου οποιοδήποτε πολωνοί μου είμαι ικανοποιημένος προσέξτε λίγο ένα άλλο παράδειγμα 0 ότι έχουμε πάλι το κλασικό μας πρόβλημα της ταξινόμησης των στοιχείων και μετράμε τη στοιχειώδη λειτουργία τους γόνους ταξινόμησης είναι σύγκριση μεταξύ στοιχείων έτσι v κυρίως κάνουν συγκρίσεις συγκρούστηκε μεταξύ τους κατακρίνουν τα μικρότερα ποσά μπροστά και τα μεγαλύτερα προς το πίσω μέρος της εισόδου για να βγάλουν την είσοδο σε ποια σειρά του MEGA πείτε λοιπόν ότι διέθετε δύο αλγόριθμους ότι ο αλγόριθμος κάνει δεν κάνει λόγο για συγκρίσεις ο δεύτερος κάνει ν το τραγανό συγκρίσεις για παράδειγμα ο ο δεύτερος είναι πρωτοφανή στόχος να ταξινομήσει κανείς είναι αυτό να κάνει όλες οι μεταθέσεις των των στοιχείων όπως σας είπα πριν που ευτυχώς ο δεύτερος πιο απλός τρόπος πιο εύκολος τρόπος να ταξινομήσει κανείς μια αριθμούς τους είναι μπορεί κανείς να σκεφθεί οριακά μυαλά εμείς δεν μιλάμε για καθαρό χρυσό μιλάμε για οποιοδήποτε έχεις σε έναν πίνακα έτσι αναδιανείμει σου δεν είναι ένα απλό στοιχείο ποιος είναι πιο απλός τρόπος να ταξινομήσουν με και παίζονται όλα κολλάνε σε φθίνουσα όσο δίνονται φθίνουσα ακολουθία συγκρίνεις καθαρό το μυαλό του γιατί κανείς πήρε μεγάλη οκ ναι και κανείς κανείς αντιμετώπισε ένα ζευγάρι και μετά δηλαδή το τοπ πέντε τρεις το 5.3 δύο ένα το έκανες στα 45 2.9 πράγμα δεν είναι απλά δεν δουλεύει έτσι αυτός δεν είναι απλός τρόπος με ο πιο απλός τρόπος να ταξινομήσουν δεν είναι είναι υπάρχει μεταξύ τους Έλληνας αλλά δεν παίρνουν τα διαδοχικά σε Γαλλία πριν και μεγαλύτερες έβγαλε κλπ αυτονομιστών Διαβάστε Κούρκουλου ο πρώτος ένα αλγόριθμος των οποίων εσύ μπορείς να σκεφτείς χωρίς να έχει διαβάσει κάτι έτσι διατρέχει στην είσοδο και βρίσκει το μικρότερο στοιχείων στο κανείς τον Τόλη θα διαφανεί πρώτον διάτρητο αφαιρείς διατρέξει την την υπόλοιπη είσοδο στο μικρότερο στοιχείο του κανείς αυτά που διατρέχει την υπόλοιπη είσοδο το μικρότερο στοιχείο το κάνει στριπτίζ και ούτω καθεξής αυτούς αλγόριθμος όπως θα δούμε έχει πολυπλοκότητα το πράγμα κάνει τετράγωνο συγκρίσεις πολλά για τα συγκρίνει όλα όλα όπως του αλγόριθμου Κοννέκτορας πείτε τώρα ελέγχονται κάθε δύο υπολογιστές έναν που εκτελεί 110000000 πράξεις άρθρο έχω και έναν που εκτελεί 1000 εκατομμύρια έτσι ένα γίγας σύγκριση το θολό Μέγας έναντι ενδεικτικές φορολογίας αλγόριθμο και θέλουμε να ταξινομήσουν εκατομμύρια αριθμούς ωραία ικανό λένε ο χρόνος του αλγόριθμου Α1 στον αργκό υπολογιστή θα είναι αποχή είναι 17 9 πηλό μνημονεύουν 12 στην ακτή διά την ταχύτητά του υπολογιστή δηλαδή αυτό είναι C στοιχειώδεις πράξεις αυτό είναι στοιχείο της πράξαμε δευτερόλεπτο άρα μας δίνει δεύτερον εάν κάνουμε τις πράξεις παρατηρούμε ότι ο αλγόριθμος που κάνει 10 υλοποίηση κρίσης που έχει ένα πολύ ώριμο εξάρτησης από το ν μικρότερο από τον δεύτερο αλγόριθμο για αυτό λέμε πιο αποδοτικός σε 20 δευτερόλεπτα θα τελειώσει που εισπράττει 20 πραγματικά δευτερόλεπτα τέλος πάμε να δούμε τον πόσο χρόνο τελείωση ο δεύτερος αλγόριθμους των γρήγορων υπολογιστών 100 φορές πάλι πιο γρήγορο υπολογιστή ωραία παίρνουμε λοιπόν πάλι τον τετράγωνο ΠΑΣΟΚ βουλή 12 στην ακτή το σωστό τραγούδι και θεωρούμε ότι υπάρχει τ υπολογιστή δηλαδή είναι στοιχειώδεις πράξεις βίας στοιχείων εισπράξαμε ανά δευτερόλεπτο μαζί μ' αυτό ρωτάω που κάνει 16 μισή λεπτά δηλαδή εκατομμύρια φορές πιο γρήγορος υπολογιστής με τον μη αποδοτικό αλγόριθμο το τετραγωνικό ενώ άλλος τελειώνει εισήλθαν σε μερικά δευτερόλεπτα ο άλλωστε 16 μισή λεπτά ένα τελείως καταλαβαίνετε και εάν δεν είχα το ένα εκατομμύριο σήμερα κατά που ζούμε στην εποχή του πολύ μεγάλου όγκου δεδομένων με βιολογικά δεδομένα δεδομένα στον παγκόσμιο ιστό όπου έχει κάτι δισεκατομμύρια σελίδες κανείς θέλει να μηχανισμό της Google η μηχανή αναζήτησης να ψάξει έναν νόμο δισεκατομμυρίων σελίδων ιστοσελίδων ιατρούς η απάντηση ωραία το 10 στην Αθήνα ο ερωτών εκατομμύρια λοιπόν αν είχαμε κάνει στο 10 στη δομή που δεν είναι πάντα κακό μηχανάκι κατά των αστυνομικών και πάρετε την ίδια πάλι τον ίδιο την συλλογισμό πάμε να δούμε λοιπόν ο πιο γρήγορος αλγόριθμους τους στον πιο αργό υπολογιστή πιο αποδοτικός δηλαδή Αλαβάνο η εξάρτηση από τον είναι μικρότερες δυνάμεις Γι' αυτό λέμε πιο αποδοτικό τι κάνω πάλι τις πράξεις δηλαδή παίρνουμε τον τον αριθμό των συγκρίσεων βάζουν όπου ν το 10 στην 7η και δίνουμε μια μάχη τον υπολογιστή που είναι συγκρίσεις ανά δευτερόλεπτο αυτό θα μας δώσει δεύτερον το χρόνο πρώτο πραγματικό χρόνο εκτέλεσης του υπολογιστή ωραία αυτό θα μας δώσει κάτι λιγότερο από τέσσερις λεπτά Νάξου πήγαμε σε 10 φορές μεγαλύτερο μέγεθος εισόδου είναι και παλαιός πολεμιστής ωραία χάνονται τέσσερις λεπτά δεν κάναμε κάτι μερικά δευτερόλεπτα πορεία τους αλλά και επαναλαμβάνοντας με τον πιο αργό εάν κάνουν την ίδια άσκηση με τον νέοι το λιγότερο αποδοτικό αλγόριθμο πολιτικό πράγμα που κάνει το τραπεζικό χώρο χρόνο και τον βάλω στον πιο γρήγορο που κάνει 101000000000 θα σταθούμε εδώ θα δείτε ότι τελειώνει μετά από μιάμιση ημέρα πλέον έτσι με τα δύο αυτά παραδείγματα θέλω να σας πω το εξής και κάποτε θα κλείσουμε το σημερινό μάθημα να θέλω να σας πω το εξής ότι ήδη ως σχεδιασμός και η ανάπτυξη και η ανάλυση αποδοτικό αλγόριθμο έχει πολύ μεγάλη τεχνολογική σημασία το είδαμε και στη σύγκριση μεταξύ πολεμικών και αυθεντικών αλγόριθμο αλλά το βλέπουμε και στη σύγκριση μεταξύ πολεμικών αλγορίθμων που ένα εκ που έχουν διαφορετικές εξάρτησης από τον ν ως προς τον εκθέτει βλέπετε ότι στην ένα περίπτωση προφανώς έτσι αν τον αλφάνο τον παλιό στο γρήγορο υπολογιστή τελείωσε μερικά δευτερόλεπτα όλα βλέπετε λοιπόν ότι αποδοτικού ότι μόνο του το χαρτί αυτό θέλω να σας ένα σημερινή διάλεξή μην νομίζετε ότι μόνο με το hardware μπορείτε να λύσετε όλα τα προβλήματα σας δεν λύνονται όλα τα προβλήματα με τον αγοράζετε διαρκώς καινούργιο υλικό χρειάζεται μια ευφυής ιδέα πίσω απ' το λογισμικό να πείσω να τρέχει αυτή πάνω στο υλικό αυτό για να μπορεί να το κάνει απόδοση για να αλλιώς θα περιμένετε μέρες ώρες και χρόνια για να πάρετε απάντηση ακόμα και σε προβλήματα εισόδου που έχουνε θα έλεγα που δεν είναι πολύ μεγάλα επομένως η απάντηση στο αν μας αρκεί οποιοσδήποτε πολιτικός χρόνος είναι όχι μόνο καλό μεσημέρι τα λέμε αύριο |