Εντάξει, έτσι, υπολογιστική πολυπλοκότητα. Ακριβώς ένα κομμάτι της προειδοποίησης πριν βουτήξει σε πάρα εως τώρα Αυτό κατά πάσα πιθανότητα θα είναι μεταξύ Οι πιο μαθηματικά-βαριά πράγματα μιλάμε για σε CS50. Ας ελπίσουμε ότι δεν θα είναι πάρα πολύ συντριπτική και εμείς θα προσπαθήσουμε και να σας καθοδηγήσει μέσω της διαδικασίας, αλλά απλά ένα κομμάτι από μια δίκαιη προειδοποίηση. Υπάρχει ένα μικρό κομμάτι των μαθηματικών που εμπλέκονται εδώ. Εντάξει, έτσι ώστε να καταστεί χρήση των υπολογιστικών πόρων μας στον πραγματικό world-- είναι πραγματικά σημαντικό να κατανοήσουμε αλγορίθμων και πώς να επεξεργάζονται δεδομένα. Αν έχουμε μια πραγματικά αποδοτικό αλγόριθμο, μπορούμε μπορεί να ελαχιστοποιήσει το ποσό των πόρων έχουμε στη διάθεσή μας για να ασχοληθεί με το θέμα. Αν έχουμε έναν αλγόριθμο ο οποίος πρόκειται να πάρει πολλή δουλειά να επεξεργαστεί ένα πραγματικά μεγάλο σύνολο των δεδομένων, είναι θα απαιτήσει περισσότερο και περισσότερους πόρους, η οποία είναι τα χρήματα, μνήμη RAM, όλα τα τέτοιου είδους πράγματα. 

Έτσι, είναι σε θέση να αναλύσει μια αλγόριθμο χρησιμοποιώντας αυτό το σύνολο εργαλείων, Βασικά, ζητά από την question-- Πώς αυτό κλίμακας αλγόριθμο όπως έχουμε ρίξει όλο και περισσότερα δεδομένα σε αυτό; Σε CS50, το ποσό των δεδομένων που είμαστε που εργάζονται με είναι αρκετά μικρό. Σε γενικές γραμμές, τα προγράμματα μας θα να τρέχει σε ένα δεύτερο ή less-- πιθανώς πολύ λιγότερο ιδιαίτερα νωρίς. 

Αλλά σκεφτείτε για μια εταιρεία που ασχολείται με εκατοντάδες εκατομμύρια πελάτες. Και πρέπει να επεξεργαστούν ότι τα δεδομένα των πελατών. Καθώς ο αριθμός των πελατών που έχουν παίρνει όλο και μεγαλύτερες, πρόκειται να απαιτήσει όλο και περισσότερους πόρους. Πόσες περισσότερους πόρους; Λοιπόν, αυτό εξαρτάται από το πόσο αναλύουμε τον αλγόριθμο, χρησιμοποιώντας τα εργαλεία της εργαλειοθήκης. Όταν μιλάμε για την πολυπλοκότητα των ένα algorithm-- το οποίο μερικές φορές θα ακούσετε να αναφέρεται ως χρόνος πολυπλοκότητας ή χωρική πολυπλοκότητα αλλά είμαστε ακριβώς πρόκειται να καλέσει complexity-- είμαστε γενικά μιλάμε για το χειρότερο σενάριο. Με δεδομένη την απόλυτη χειρότερο σωρός του στοιχεία που θα μπορούσαν να ρίχνουν σε αυτό, πώς ο αλγόριθμος αυτός θα επεξεργάζονται ή να ασχοληθούν με αυτά τα δεδομένα; Εμείς γενικά ονομάζουμε την χειρότερη περίπτωση εκτέλεσης ενός αλγορίθμου big-O. Έτσι, ένας αλγόριθμος θα μπορούσε να ειπωθεί ότι εκτελείται σε O Ν ή Ο Ν τετράγωνο. Και περισσότερα για το τι εκείνων σημαίνει σε ένα δευτερόλεπτο. 

Μερικές φορές, όμως, κάνουμε φροντίδα σχετικά με το αισιόδοξο σενάριο. Εάν τα δεδομένα είναι όλα όσα θέλαμε να είναι και ήταν απολύτως τέλεια και μας στέλνει αυτό το τέλειο το σύνολο των δεδομένων μέσω του αλγορίθμου μας. Πώς θα το χειριστεί σε αυτήν την κατάσταση; Εμείς μερικές φορές αναφέρονται σε αυτό ως big-Omega, τόσο σε αντίθεση με τα μεγάλα-O, έχουμε μεγάλη-Ωμέγα. Big-Omega για το καλύτερο σενάριο. Big-O για το χειρότερο σενάριο. Σε γενικές γραμμές, όταν μιλάμε για η πολυπλοκότητα ενός αλγορίθμου, μιλάμε για το στη χειρότερη περίπτωση. Έτσι κρατήστε αυτό κατά νου. 

Και σε αυτή την κατηγορία, είμαστε γενικά θα να αποχωρήσει από την αυστηρή ανάλυση άκρη. Υπάρχουν επιστήμες και τομείς προορίζεται για αυτό το είδος της ουσίας. Όταν μιλάμε για το σκεπτικό μέσω αλγορίθμων, το οποίο θα κάνουμε το κομμάτι-από-κομμάτι για πολλούς αλγόριθμοι μιλάμε για μέσα στην τάξη. Είμαστε πραγματικά ακριβώς μιλάμε για σκεπτικό μέσα από αυτό με την κοινή λογική, όχι με τους τύπους, ή αποδείξεις, ή κάτι τέτοιο. Γι 'αυτό μην ανησυχείτε, δεν θα είναι να μετατραπεί σε ένα μεγάλο μάθημα των Μαθηματικών. 

Έτσι είπα εμείς ενδιαφερόμαστε για την πολυπλοκότητα γιατί θέτει το ερώτημα, πώς δεν αλγορίθμων μας χειρίζονται μεγαλύτερα και μεγαλύτερα σύνολα δεδομένων που ρίχνονται σε αυτούς. Λοιπόν, τι είναι ένα σύνολο δεδομένων; Τι εννοούσα όταν είπα αυτό; Αυτό σημαίνει ότι ό, τι κάνει το πιο νόημα στο πλαίσιο, για να είμαι ειλικρινής. Αν έχουμε έναν αλγόριθμο, το Διεργασίες Strings-- είμαστε πιθανώς μιλάμε για το μέγεθος του string. Αυτό είναι τα δεδομένα set-- το μέγεθος, ο αριθμός των χαρακτήρων που συνθέτουν τη σειρά. Αν μιλάμε για ένα αλγόριθμο που επεξεργάζεται αρχεία, θα μπορούσαμε να μιλάμε για το πώς πολλές kilobytes περιλαμβάνει αυτό το αρχείο. Και αυτό είναι το σύνολο των δεδομένων. Αν μιλάμε για έναν αλγόριθμο ότι χειρίζεται συστοιχίες γενικότερα, όπως αλγορίθμων ταξινόμησης ή την αναζήτηση αλγορίθμων, πιθανόν μιλάμε για τον αριθμό των στοιχείων που περιλαμβάνουν μία συστοιχία. 

Τώρα, μπορούμε να μετρήσουμε μια algorithm-- ειδικότερα, όταν λέω ότι μπορούμε μετρούν έναν αλγόριθμο, που σημαίνει ότι μπορεί να μετρήσει πόσο πολλοί πόροι που καταλαμβάνει. Είτε είναι οι πόροι αυτοί, πόσα bytes της RAM-- ή ΜΒ RAM χρησιμοποιεί. Ή πόσο χρόνο χρειάζεται για να τρέξει. Και μπορούμε να ονομάσουμε αυτό μετρούν, αυθαίρετα, στ ν. Όπου n είναι ο αριθμός των στοιχείων στο σύνολο δεδομένων. Και στ του ν είναι πόσα Κάτι. Πόσες μονάδες των πόρων δεν απαιτεί να επεξεργαστεί τα δεδομένα. 

Τώρα, έχουμε πραγματικά δεν με νοιάζει για το τι στ ν είναι ακριβώς. Στην πραγματικότητα, πολύ σπάνια will-- Σίγουρα δεν θα είναι ποτέ σε αυτό το class-- μου βουτιά σε οποιαδήποτε πραγματικά βαθιά ανάλυση του τι στ ν είναι. Εμείς απλά θα μιλήσουμε για το τι στ της n είναι περίπου ή τι τείνει να. Και η τάση ενός αλγορίθμου είναι υπαγορεύεται από το ανώτατο όρο της τάξης. Και μπορούμε να δούμε τι θα εννοούμε με τον όρο ότι με τη λήψη Μια ματιά σε ένα πιο συγκεκριμένο παράδειγμα. 

Ας πούμε ότι έχουμε τρεις διαφορετικοί αλγόριθμοι. Η πρώτη από τις οποίες λαμβάνει n κύβους, ορισμένες μονάδες των πόρων να επεξεργαστεί ένα σύνολο δεδομένων μεγέθους n. Έχουμε ένα δεύτερο αλγόριθμο που λαμβάνει n κύβο συν n τετράγωνο πόρων να επεξεργαστεί ένα σύνολο δεδομένων μεγέθους n. Και έχουμε ένα τρίτο αλγόριθμος που τρέχει in-- ότι καταλαμβάνει n κύβους μείον 8η τετράγωνο συν 20 n μονάδες των πόρων να επεξεργαστεί έναν αλγόριθμο με τα δεδομένα που του μεγέθους n. 

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

Εάν το σύνολο δεδομένων μας είναι μέγεθος 10, η οποία είναι μεγαλύτερο, αλλά όχι απαραίτητα τεράστιο, μπορούμε να δούμε ότι υπάρχει στην πραγματικότητα ένα κομμάτι της διαφοράς. Η τρίτη αλγόριθμος γίνεται πιο αποτελεσματική. Πρόκειται για πραγματικά 40% - ή 60% πιο αποτελεσματική. Παίρνει 40%, το ποσό του χρόνου. Μπορεί run-- μπορεί να πάρει 400 μονάδες πόρων να επεξεργαστεί ένα σύνολο δεδομένων μεγέθους 10. Ότι η πρώτη αλγόριθμο, αντιθέτως, παίρνει 1.000 μονάδες πόρων να επεξεργαστεί ένα σύνολο δεδομένων μεγέθους 10. Αλλά κοιτάξτε τι συμβαίνει ως αριθμοί μας να πάρει ακόμη μεγαλύτερο. 

Τώρα, η διαφορά μεταξύ αυτών των αλγορίθμων αρχίζουν να γίνονται λίγο λιγότερο εμφανής. Και το γεγονός ότι υπάρχουν χαμηλότερης τάξης terms-- ή μάλλον, όρους με χαμηλότερο exponents-- αρχίζουν να καταστεί άνευ αντικειμένου. Εάν ένα σύνολο δεδομένων είναι το μέγεθος 1000 και το πρώτο αλγόριθμο τρέχει σε ένα δισεκατομμύριο βήματα. Και ο δεύτερος αλγόριθμος τρέχει σε ένα δισεκατομμύριο και ένα εκατομμύριο βήματα. Και ο τρίτος αλγόριθμος τρέχει σε μόλις ντροπαλός του ενός δισεκατομμυρίου βήματα. Είναι λίγο πολύ ένα δισεκατομμύριο βήματα. Αυτοί οι όροι κατώτερο προκειμένου να ξεκινήσει να γίνει πραγματικά άσχετη. Και ακριβώς για να πραγματικά σφυρί το σπίτι της point-- αν η είσοδος δεδομένων είναι ένα μέγεθος million-- τα τρία από αυτά λίγο πολύ πάρτε ένα quintillion-- αν μαθηματικά μου είναι correct-- βήματα να επεξεργαστεί μια είσοδο δεδομένων του μεγέθους του ένα εκατομμύριο. Αυτό είναι πολλά βήματα. Και το γεγονός ότι ένας από αυτούς μπορεί να πάρτε ένα ζευγάρι από 100.000, ή ένα ζευγάρι 100 εκατομμύρια ακόμη λιγότερο όταν μιλάμε για έναν αριθμό big-- ότι αυτό είναι το είδος της άσχετο. Όλα τείνουν να λάβουν περίπου n κύβους, και γι 'αυτό θα αναφερθώ στην πραγματικότητα σε όλες αυτές τις αλγορίθμων ως της τάξης του n κύβους ή μεγάλο-Ο Ν κύβους. 

Εδώ είναι μια λίστα με μερικά από τα πιο κοινή υπολογιστική πολυπλοκότητα κατηγορίες ότι θα συναντήσετε στο αλγορίθμων, σε γενικές γραμμές. Και, επίσης, ειδικά σε CS50. Αυτά είναι παραγγελθούν από γενικά ταχύτερος στην κορυφή, για γενικά βραδύτερη στο κάτω μέρος. Έτσι, οι αλγόριθμοι τείνουν σταθερά χρόνου να είναι ο ταχύτερος, ανεξαρτήτως του μεγέθους του εισαγωγής δεδομένων περνάτε. Παίρνουν πάντα μία πράξη ή μία μονάδα των πόρων για την αντιμετώπιση. Θα μπορούσε να είναι 2, θα μπορούσε να είναι 3, θα μπορούσε να είναι 4. Αλλά είναι ένας σταθερός αριθμός. Αυτό δεν μεταβάλλεται. 

Λογαριθμική αλγόριθμοι χρόνο είναι ελαφρώς καλύτερη. Και ένα πολύ καλό παράδειγμα λογαριθμική αλγόριθμο έχετε σίγουρα δει μέχρι τώρα είναι η σχίσιμο του τηλεφωνικού καταλόγου να βρείτε Mike Smith στον τηλεφωνικό κατάλογο. Κόβουμε το πρόβλημα στη μέση. Και έτσι καθώς το n μεγαλώνει και μεγαλύτερα και larger-- Στην πραγματικότητα, κάθε φορά που θα διπλασιαστεί n, παίρνει μόνο ένα ακόμη βήμα. Οπότε αυτό είναι ένα πολύ καλύτερο από ό, τι, ας πούμε, γραμμικό χρόνο. Ποια είναι αν διπλασιαστεί η, το Δέχεται διπλούς τον αριθμό των βημάτων. Αν τριπλασιαστεί n, παίρνει τριπλασιάσει τον αριθμό των βημάτων. Ένα βήμα ανά μονάδα. 

Στη συνέχεια, τα πράγματα παίρνουν μια μικρή more-- Λίγο λιγότερο μεγάλη από εκεί. Έχετε γραμμική ρυθμική χρόνο, μερικές φορές που ονομάζεται log γραμμικού χρόνου ή απλά n log n. Και θα αποτελεί παράδειγμα από έναν αλγόριθμο που τρέχει στο n log n, η οποία είναι ακόμη καλύτερα από τετραγωνική time-- n τετράγωνο. Ή πολυωνυμικό χρόνο, n δύο οποιοσδήποτε αριθμός μεγαλύτερος από δύο. Ή εκθετικό χρόνο, η οποία είναι ακόμη worse-- C έως το n. Έτσι, κάποιοι σταθερός αριθμός αυξήθηκε σε η ισχύς του μεγέθους της εισόδου. Έτσι, αν υπάρχει 1,000-- εάν η εισαγωγή δεδομένων έχει μέγεθος 1.000, θα χρειαζόταν C στην 1000η εξουσία. Είναι μια πολύ χειρότερα από ό, τι πολυωνυμικό χρόνο. 

Παραγοντικό χρόνος είναι ακόμη χειρότερη. Και στην πραγματικότητα, πραγματικά υπάρχει Υπάρχουν άπειρες αλγορίθμων χρόνου, όπως το λεγόμενο ηλίθιο sort-- των οποίων δουλειά είναι να ανακατέψετε τυχαία μια σειρά και, στη συνέχεια, ελέγξτε για να δείτε αν αυτό είναι ταξινομημένο. Και αν δεν είναι, τυχαία ανακατέψει και πάλι τον πίνακα και ελέγξτε για να δείτε αν είναι ταξινομημένο. Και όπως μπορείτε να imagine-- μπορείτε να φανταστείτε μια κατάσταση όπου στην χειρότερη περίπτωση, ότι βούληση στην πραγματικότητα ποτέ δεν ξεκινήσει με τη συστοιχία. Ότι ο αλγόριθμος θα τρέχει για πάντα. Και έτσι ώστε θα ήταν μια άπειρο χρόνο αλγόριθμος. Ας ελπίσουμε ότι δεν θα πρέπει να γράφει κάθε παραγοντικό ή άπειρο χρόνο αλγορίθμων σε CS50. 

Έτσι, ας ρίξουμε λίγο περισσότερο σκυρόδεμα ματιά σε κάποια απλούστερη υπολογιστική κλάσεις πολυπλοκότητας. Έτσι, έχουμε μια example-- ή δύο παραδείγματα here-- σταθερής αλγορίθμων χρόνου, η οποία να λαμβάνει πάντα μια ενιαία πράξη στη χειρότερη περίπτωση. Έτσι, το πρώτο example-- έχουμε μια συνάρτηση κάλεσε 4 για σας, η οποία λαμβάνει μια σειρά μεγέθους 1.000. Στη συνέχεια, όμως προφανώς στην πραγματικότητα δεν φαίνονται σε it-- δεν ενδιαφέρονται πραγματικά ό, τι είναι στο εσωτερικό του, της εν λόγω διάταξης. Πάντα επιστρέφει μόλις τέσσερις. Έτσι, ότι ο αλγόριθμος, παρά το γεγονός ότι παίρνει 1.000 στοιχεία δεν κάνει τίποτα μαζί τους. Απλά επιστρέφει τέσσερις. Είναι πάντα ένα βήμα. 

Στην πραγματικότητα, προσθέστε 2 nums-- οποία έχουμε δει στο παρελθόν, όπως well-- επεξεργάζεται μόνο δύο ακέραιους αριθμούς. Δεν είναι ένα μόνο βήμα. Είναι πραγματικά βήματα ένα ζευγάρι. Μπορείτε να πάρετε ένα, μπορείτε να πάρετε b, μπορείτε να τους προσθέσετε μαζί, και θα εξάγει τα αποτελέσματα. Έτσι είναι 84 βήματα. Αλλά είναι πάντα σταθερή, ανεξάρτητα από α ή β. Θα πρέπει να πάρετε ένα, να πάρει β, προσθέστε μαζί, το αποτέλεσμα εξόδου. Οπότε αυτό είναι ένα σταθερό χρόνο αλγόριθμος. 

Εδώ είναι ένα παράδειγμα ενός γραμμικό χρόνο algorithm-- ένας αλγόριθμος που gets-- ότι παίρνει ένα επιπλέον βήμα, ενδεχομένως, ως συμβολή σας αυξάνεται κατά 1. Έτσι, ας πούμε ότι ψάχνετε ο αριθμός 5 στο εσωτερικό μιας συστοιχίας. Μπορεί να έχετε μια κατάσταση όπου μπορείτε να το βρείτε αρκετά νωρίς. Αλλά θα μπορούσε επίσης να έχει μια κατάσταση όπου θα μπορούσε να είναι το τελευταίο στοιχείο της συστοιχίας. Σε μια σειρά μεγέθους 5, εάν ψάχνουμε για τον αριθμό 5. Θα χρειαστούν 5 βήματα. Και στην πραγματικότητα, να φανταστείτε ότι υπάρχει Δεν 5 οπουδήποτε σε αυτό το φάσμα. Είμαστε ακόμα στην πραγματικότητα πρέπει να εξετάσουμε κάθε στοιχείο της συστοιχίας προκειμένου να καθοριστεί έστω 5 υπάρχει. 

Έτσι, στη χειρότερη περίπτωση, η οποία είναι η το στοιχείο είναι η τελευταία στη συστοιχία ή δεν υπάρχει καθόλου. Έχουμε ακόμη να δούμε όλα τα n στοιχεία. Και έτσι αυτό αλγόριθμος εκτελείται σε γραμμικό χρόνο. Μπορείτε να επιβεβαιώσετε ότι από προέκταση λίγο λέγοντας, αν είχαμε μια σειρά 6-στοιχείων και ψάχναμε για τον αριθμό 5, μπορεί να πάρει 6 βήματα. Αν έχουμε μια σειρά 7 στοιχείο και ψάχνουμε για τον αριθμό 5. Θα μπορούσε να λάβει 7 βήματα. Καθώς προσθέτουμε ένα ακόμη στοιχείο που πρέπει να μας σειρά, παίρνει ένα ακόμη βήμα. Αυτό είναι ένα γραμμικό αλγόριθμο στη χειρότερη περίπτωση. 

Ζευγάρι γρήγορες ερωτήσεις για σας. Ποια είναι η runtime-- τι είναι η χειρότερη περίπτωση εκτέλεσης του συγκεκριμένου αποσπάσματος κώδικα; Έτσι έχω ένα 4 βρόχο που τρέχει εδώ από j ισούται με 0, σε όλη τη διαδρομή μέχρι το m. Και ό, τι βλέπω εδώ, είναι ότι η σώμα του βρόχου εκτελείται σε σταθερό χρόνο. Έτσι, χρησιμοποιώντας την ορολογία που έχουμε ήδη μιλήσει about-- τι θα είναι η χειρότερη περίπτωση runtime αυτού του αλγορίθμου; Πάρτε ένα δευτερόλεπτο. Το εσωτερικό μέρος του βρόχου εκτελείται σε σταθερό χρόνο. Και το εξωτερικό μέρος του βρόχος πρόκειται να τρέξει m φορές. Έτσι ποια είναι η χειρότερη περίπτωση χρόνου εκτέλεσης εδώ; Μήπως να μαντέψετε μεγάλος-O του m; Θα ήθελα να είναι σωστή. 

Τι θα λέγατε για ένα άλλο; Αυτή τη φορά έχουμε ένα βρόχος μέσα από ένα βρόχο. Έχουμε ένα εξωτερικό βρόχο που εκτείνεται από μηδέν έως σ. Και έχουμε ένα εσωτερικό βρόχο που τρέχει από μηδέν σε p, και στο εσωτερικό του ότι, Δηλώνω ότι το σώμα της βρόχος εκτελείται σε σταθερό χρόνο. Έτσι ποια είναι η χειρότερη περίπτωση εκτέλεσης του συγκεκριμένου αποσπάσματος κώδικα; Λοιπόν, και πάλι, έχουμε μια εξωτερικός βρόχος που τρέχει φορές σ. Και κάθε time-- επανάληψη του εν λόγω βρόχου, μάλλον. Έχουμε ένα εσωτερικό βρόχο που τρέχει επίσης φορές σ. Και στη συνέχεια, μέσα από αυτό, υπάρχει η σταθερή time-- μικρό απόσπασμα εκεί. 

Έτσι, αν έχουμε ένα εξωτερικό βρόχο που τρέχει φορές p εντός του οποίου είναι ένα εσωτερικό βρόχο που τρέχει σ times-- ό, τι είναι η χειρότερη περίπτωση εκτέλεσης αυτής απόσπασμα του κώδικα; Μήπως να μαντέψετε μεγάλο-Ο π τετράγωνο; 

Είμαι ο Νταγκ Lloyd. Αυτό είναι CS50.