[Powered by Google Translate] [Ενότητα 3 - Περισσότερα Άνετα] [Rob Bowden - Πανεπιστήμιο του Χάρβαρντ] 

[Αυτό είναι CS50. - CS50.TV] 

Έτσι, το πρώτο ερώτημα είναι διατυπωμένο παράξενα. GDB σας επιτρέπει να "διορθώσετε" ένα πρόγραμμα, αλλά, πιο συγκεκριμένα, τι χρειάζεται για να σας κάνουμε; Θα απαντήσω ότι μία, και δεν ξέρω τι ακριβώς αναμενόταν, οπότε υποθέτω ότι είναι κάτι κατά μήκος των γραμμών του σας επιτρέπει να το βήμα προς βήμα περπατήσετε μέσα από το πρόγραμμα, αλληλεπιδρούν με αυτό, οι μεταβλητές αλλαγή, κάνει όλα αυτά τα πράγματα - ουσιαστικά ελέγχουν πλήρως την εκτέλεση ενός προγράμματος και να επιθεωρεί κάθε δεδομένη μέρος της εκτέλεσης του προγράμματος. Έτσι, αυτά τα χαρακτηριστικά σας επιτρέπουν να διορθώσετε τα πράγματα. Εντάξει. Γιατί η δυαδική αναζήτηση απαιτεί μια σειρά να ταξινομηθούν; Ποιος θέλει να απαντήσει σε αυτό; [Φοιτητής] Επειδή δεν λειτουργεί αν δεν είναι ταξινομημένο. Ναι >>. [Γέλια] Εάν δεν είναι ταξινομημένο, τότε είναι αδύνατο να χωριστεί στη μέση και να ξέρετε ότι πάντα στα αριστερά είναι μικρότερη και τα πάντα προς τα δεξιά είναι μεγαλύτερη από την μέση τιμή. Γι 'αυτό πρέπει να διευθετηθεί. Εντάξει. Γιατί είναι είδος φούσκας των n O τετράγωνο; Μήπως κάποιος πρέπει πρώτα να δώσει μια πολύ γρήγορη επισκόπηση υψηλού επιπέδου των τι είδους είναι φούσκα; [Φοιτητής] Μπορείτε βασικά να περάσουν από κάθε στοιχείο και να ελέγξετε τα πρώτα στοιχεία. Αν είστε από όπου μπορείτε να ανταλλάξετε, τότε ελέγξτε τις επόμενες στοιχεία και ούτω καθεξής. Όταν φτάσετε στο τέλος, τότε ξέρετε ότι το μεγαλύτερο στοιχείο τοποθετείται στο τέλος, έτσι ώστε να αγνοήσουμε ότι ένας τότε θα συνεχίσουμε να προχωράμε μέσα, και κάθε φορά που θα πρέπει να ελέγξετε ένα λιγότερο στοιχείο μέχρι να κάνετε καμία αλλαγή. Ναι >>. Λέγεται είδος φούσκα γιατί αν αναστρέψετε τη σειρά από την πλευρά της, γι 'αυτό είναι πάνω-κάτω, κάθετα, τότε οι μεγάλες τιμές θα βυθίζονται στον πυθμένα και οι μικρές τιμές θα φούσκα μέχρι την κορυφή. Αυτό είναι το πώς πήρε το όνομά του. Και ναι, μπορείτε απλά να περάσει. Θα συνεχίζουμε μέσω του πίνακα, αλλάζουν τη μεγαλύτερη αξία για να πάρει τις μεγαλύτερες τιμές προς τα κάτω. 

Γιατί είναι n Ξ τετράγωνο; Κατ 'αρχάς, δεν θέλει κανείς να πει γιατί είναι από n O τετράγωνο; [Φοιτητής] Επειδή για κάθε επιχείρηση πηγαίνει n φορές. Μπορείτε να είστε σίγουροι ότι έχετε πάρει το μεγαλύτερο στοιχείο σε όλη τη διαδρομή προς τα κάτω, τότε θα πρέπει να επαναλάβω ότι για όσο πολλά στοιχεία. Ναι >>. Έτσι, έχετε κατά νου τι σημαίνει μεγάλη O μεγάλος και τι σημαίνει Omega. Η μεγάλη O είναι σαν το άνω όριο για το πώς αργή μπορεί πραγματικά να τρέξει. Έτσι, λέγοντας O αυτό του n στο τετράγωνο, δεν είναι από O n ή αλλιώς θα είναι σε θέση να τρέξει σε γραμμικό χρόνο, αλλά είναι Ο κ κύβους επειδή οριοθετείται από O κ κύβους. Αν αυτό είναι που οριοθετείται από O ν τετράγωνο, τότε είναι που οριοθετείται επίσης από n κύβους. Γι 'αυτό είναι ν τετράγωνο, και στην απόλυτη χειρότερη περίπτωση δεν μπορεί να κάνει καλύτερα από ό, τι n τετράγωνο, η οποία είναι ο λόγος για αυτό είναι n Ξ τετράγωνο. Έτσι για να δείτε μικρή μαθηματικά το πώς πρόκειται να είναι n τετράγωνο, αν έχουμε πέντε πράγματα στην λίστα μας, είναι η πρώτη φορά πόσα swaps θα μπορούσαμε ενδεχομένως να χρειαστεί να προκειμένου να πάρει αυτό; Ας πραγματικά μόνο - Πόσες swaps θα πάμε να πρέπει να κάνει το πρώτο τρέξιμο του bubble sort μέσω του πίνακα; [Φοιτητής] n - 1. Ναι >>. 

Αν υπάρχουν 5 στοιχεία, θα πάμε να χρειαστεί να κάνετε n - 1. Στη συνέχεια, στο δεύτερο πόσες swaps θα πάμε να πρέπει να κάνουμε; [Φοιτητής] n - 2. Ναι >>. Και η τρίτη θα είναι n - 3, και στη συνέχεια, για λόγους ευκολίας θα γράψω τα δύο τελευταία όπως και τότε θα πάμε να χρειαστεί να κάνει 2 swaps και 1 swap. Υποθέτω ότι το τελευταίο μπορεί ή δεν μπορεί πραγματικά να συμβεί. Είναι ένα swap; Δεν ξέρω. Αυτά λοιπόν είναι τα συνολικά ποσά των συμβάσεων ανταλλαγής ή τουλάχιστον συγκρίσεις που έχετε να κάνετε. Ακόμα κι αν δεν έχετε ανταλλάξει, θα πρέπει ακόμα να συγκρίνουν τις τιμές. Έτσι, υπάρχουν n - 1 συγκρίσεις σε πρώτη εκτέλεση, μέσω του πίνακα. Αν οργανώσετε αυτά τα πράγματα, ας το κάνει στην πραγματικότητα έξι πράγματα έτσι πήγαν τα πράγματα καλά, και στη συνέχεια θα κάνω 3, 2, 1. Έτσι απλά αναδιάταξη των ποσών αυτών, θέλουμε να δούμε πόσα κάνουμε συγκρίσεις σε ολόκληρο το αλγόριθμο. Έτσι, αν φέρουμε αυτά τα παιδιά εδώ κάτω, τότε είμαστε ακόμα αθροίζοντας ακριβώς όμως πολλές συγκρίσεις ήταν εκεί. Αλλά αν θέλουμε να τα συλλέξετε και να τα συλλέξετε και να συνοψίσω αυτά, είναι ακόμα το ίδιο πρόβλημα. Θα συνοψίσω ακριβώς αυτές τις συγκεκριμένες ομάδες. 

Έτσι τώρα είμαστε αθροίζοντας 3 είναι n. Δεν είναι μόνο 3 n του. Είναι πάντα θα είναι n / 2 n. Έτσι, εδώ τυχαίνει να έχει 6. Αν είχαμε 10 πράγματα, τότε θα μπορούσαμε να κάνουμε αυτή την ομάδα για 5 διαφορετικά ζεύγη των πραγμάτων και καταλήγουν με n + n + ν + ν + ν. Έτσι είστε πάντα πρόκειται να πάρει n / 2 n, και έτσι αυτό θα το σημειώνω για να τετράγωνο n / 2. Και έτσι ακόμα κι αν είναι ο παράγοντας της μισό, η οποία συμβαίνει να έρχονται σε λόγω του γεγονότος ότι κάθε επανάληψη μέσα πάνω από την συστοιχία 1 συγκρίνουμε λιγότερα έτσι ώστε να είναι το πώς θα πάρει το πάνω από 2, αλλά εξακολουθεί να είναι n τετράγωνο. Δεν νοιάζονται για το σταθερό παράγοντα του μισού. Έτσι, πολλά από τα μεγάλα πράγματα O όπως αυτό βασίζεται σε ακριβώς το είδος του να κάνει αυτό το είδος των μαθηματικών, κάνει ποσά αριθμητική και γεωμετρική σειρά πράγματα, αλλά οι περισσότεροι από αυτούς σε αυτή την πορεία είναι αρκετά απλή. Εντάξει. Γιατί είναι είδος εισαγωγής σε ωμέγα του n; Τι σημαίνει ωμέγα; [Δύο μαθητές μιλώντας ταυτόχρονα - ακατάληπτο] >> Ναι. Omega μπορείτε να σκεφτείτε ως το κατώτερο όριο. 

Έτσι, δεν έχει σημασία πόσο αποτελεσματική εισαγωγή αλγόριθμος σας είναι είδος, ανεξάρτητα από τη λίστα που πέρασε, θα πρέπει πάντα να συγκρίνει τουλάχιστον n πράγματα ή πρέπει να επαναλάβει πάνω από n πράγματα. Γιατί συμβαίνει αυτό; [Φοιτητής] Διότι, αν η λίστα έχει ήδη ταξινομημένο, στη συνέχεια, μέσα από το πρώτο επανάληψη μπορείτε μόνο να εγγυηθεί ότι το πρώτο στοιχείο είναι το λιγότερο, και η δεύτερη επανάληψη μπορείτε να εγγυηθούν μόνο οι δυο πρώτες είναι επειδή δεν ξέρετε ότι το υπόλοιπο της λίστας είναι ταξινομημένο. Ναι >>. Αν περάσει σε ένα εντελώς ταξινομημένη λίστα, τουλάχιστον θα πρέπει να πάει πέρα ​​από όλα τα στοιχεία για να δείτε ότι τίποτα δεν πρέπει να μετακινούνται. Έτσι, περνώντας πάνω από τον κατάλογο και λέγοντας OH, αυτό είναι ήδη ταξινομημένο, είναι αδύνατο για σας να ξέρετε ότι είναι ταξινομημένο μέχρι να ελέγξετε κάθε στοιχείο για να δείτε ότι είναι σε ταξινομημένη σειρά. Έτσι, το κάτω φράγμα για το είδος είναι η εισαγωγή της Omega n. Ποια είναι η χειρότερη περίπτωση χρόνος λειτουργίας του είδους συγχώνευση, χειρότερη περίπτωση είναι O μεγάλος και πάλι; Έτσι, στη χειρότερη περίπτωση, πώς συγχώνευση είδος τρέχει; [Φοιτητής] Ν log n. Ναι >>. Τα ταχύτερα γενικές αλγόριθμοι ταξινόμησης είναι n log n. Δεν μπορείτε να το κάνετε καλύτερα. 

Υπάρχουν ειδικές περιπτώσεις, και αν έχουμε χρόνο σήμερα - αλλά πιθανώς won't - θα μπορούσαμε να δούμε αυτό που κάνει καλύτερα από ό, τι n log n. Όμως, στη γενική περίπτωση, δεν μπορείτε να κάνετε καλύτερα από ό, τι n log n. Και συγχώνευση είδος συμβαίνει να είναι το ένα που πρέπει να ξέρετε για αυτό το μάθημα, που είναι n log n. Και έτσι θα είναι στην πραγματικότητα ότι σήμερα εφαρμογή. Και τέλος, σε όχι περισσότερες από τρεις προτάσεις, πώς εργασίες επιλογής του είδους; Μήπως κάποιος θέλει να απαντήσει, και θα μετρήσει τις προτάσεις σας γιατί αν πάει πάνω από 3 - Θυμάται κανείς είδος επιλογής; Η επιλογή του είδους είναι συνήθως αρκετά εύκολο να θυμόμαστε μόνο από το όνομα. Απλά επαναλάβει πάνω στον πίνακα, να βρουν ό, τι η μεγαλύτερη τιμή είναι μικρότερη ή - Για ό, τι είστε μέσα διαλογή Ας πούμε ότι είμαστε διαλογή από το μικρότερο στο μεγαλύτερο. Θα επαναλάβει πάνω στον πίνακα, ψάχνει για ό, τι το ελάχιστο στοιχείο είναι, επιλέξτε το και, στη συνέχεια ανταλλάξουν ακριβώς ό, τι είναι στην πρώτη θέση. Και στη συνέχεια, στο δεύτερο πέρασμα πάνω από τον πίνακα, αναζητήστε το ελάχιστο στοιχείο και πάλι, επιλέξτε το και στη συνέχεια ανταλλάσσουν με ό, τι είναι στη δεύτερη θέση. Γι 'αυτό ακριβώς να πάρει και την επιλογή των ελάχιστων τιμών και την εισαγωγή τους στο μπροστινό μέρος του πίνακα, μέχρι να είναι ταξινομημένος. Ερωτήσεις σχετικά με αυτό; 

Αυτά αναπόφευκτα εμφανίζονται στα έντυπα που πρέπει να συμπληρώσετε όταν την υποβολή της PSET. Αυτά είναι βασικά οι απαντήσεις σε αυτά. Εντάξει, έτσι τώρα τα προβλήματα κωδικοποίησης. Έχω ήδη στείλει email από πάνω - Μήπως κάποιος δεν πάρει το μήνυμα ηλεκτρονικού ταχυδρομείου; Εντάξει. Έχω ήδη στείλει email πάνω από το χώρο που θα πάμε να χρησιμοποιούν, και αν κάνετε κλικ στο όνομά μου - έτσι νομίζω ότι είμαι πρόκειται να είναι στο κάτω μέρος λόγω της προς τα πίσω r - αλλά αν κάνετε κλικ στο όνομά μου, θα δείτε 2 αναθεωρήσεις. Αναθεώρηση 1 πρόκειται να έχω ήδη αντιγραφεί και επικολληθεί τον κώδικα σε χώρους για την αναζήτηση πράγμα που πρόκειται να πρέπει να εφαρμόσουν. Και Αναθεώρηση 2 θα είναι το πράγμα είδος που θα εφαρμόσουν μετά από αυτό. Έτσι, μπορείτε να κάνετε κλικ για την αναθεώρηση μου 1 και εργάζονται από εκεί. Και τώρα θέλουμε να εφαρμόσουμε δυαδική αναζήτηση. 

Υπάρχει κάποιος που θέλει να δώσει μόνο ένα ψευδοκώδικα υψηλού επιπέδου εξήγηση από ό, τι θα πάμε να πρέπει να κάνουμε για αναζήτηση; Ναι. [Φοιτητής] Παίρνετε ακριβώς στη μέση του πίνακα και να δούμε αν αυτό που ψάχνετε είναι μικρότερη από εκείνη ή περισσότερο από αυτό. Και αν είναι λιγότερο, θα πάτε με το μισό που είναι λιγότερο, και αν είναι περισσότερα, πηγαίνετε στο μισό που είναι περισσότερο και σας επαναλαμβάνω ότι μέχρι να πάρει μόνο ένα πράγμα. [Bowden] Ναι. Σημειώστε ότι οι αριθμοί μας σειρά είναι ήδη ταξινομημένο, και έτσι αυτό σημαίνει ότι μπορούν να επωφεληθούν από αυτό και θα μπορούσαμε να πρώτα να ελέγξετε, εντάξει, εγώ ψάχνω για τον αριθμό 50. Έτσι, μπορώ να πάω στη μέση. Μέση είναι δύσκολο να καθοριστεί, όταν πρόκειται για ένα ακόμα πολλά πράγματα, αλλά ας πούμε ότι θα περικόψει πάντα στη μέση. Έτσι, εδώ έχουμε 8 πράγματα, έτσι ώστε η μέση θα είναι 16. Ψάχνω για το 50, έτσι 50 είναι μεγαλύτερο από 16. Έτσι τώρα μπορώ να τη θεραπεία βασικά σειρά μου, όπως τα στοιχεία αυτά. Μπορώ να ρίξει μακριά τα πάντα πάνω από 16. Τώρα σειρά μου είναι μόνο αυτά τα 4 στοιχεία, και το επαναλαμβάνω. Μέχρι τότε θέλω να βρω και πάλι τη μέση, η οποία θα είναι 42. 42 είναι μικρότερο από 50, ώστε να μπορώ να πετάξετε αυτά τα δύο στοιχεία. Αυτή είναι η σειρά μου απομένει. Πάω να βρείτε τη μέση και πάλι. Υποθέτω ότι 50 ήταν ένα κακό παράδειγμα, γιατί ήμουν πάντα πετώντας μακριά τα πράγματα προς τα αριστερά, αλλά με το ίδιο μέτρο, αν ψάχνω για κάτι και είναι λιγότερο από ό, τι το στοιχείο είμαι σήμερα κοιτάζοντας, τότε Πάω να ρίξει μακριά τα πάντα προς τα δεξιά. Έτσι, τώρα θα πρέπει να εφαρμόσουν αυτό. Σημειώστε ότι θα πρέπει να περάσει σε μέγεθος. Μπορούμε, επίσης, δεν χρειάζεται να σκληρό κωδικό μέγεθος. Έτσι, αν θέλουμε να απαλλαγούμε από ότι # define - Εντάξει. Πώς μπορώ να καταλάβω πολύ καλά ποιο είναι το μέγεθος του πίνακα αριθμών είναι σήμερα; 

Πόσα είναι τα στοιχεία του πίνακα αριθμών; [Φοιτητής] Αριθμοί, στηρίγματα,. Μήκος; [Bowden] που δεν υπάρχει σε C. Χρειάζεστε. Μήκος. Συστοιχίες δεν έχουν ιδιότητες, έτσι δεν υπάρχει καμία ιδιότητα μήκος των συστοιχιών που θα σας δώσω όσο χρόνο και να συμβαίνει να είναι. [Φοιτητής] Δείτε πόση μνήμη έχει και διαιρέστε με το πόσο - >> Ναι. Πώς, λοιπόν, μπορούμε να δούμε πόση μνήμη έχει; >> [Φοιτητής] sizeof. >> Ναι, sizeof. Sizeof είναι ο φορέας που πρόκειται να επιστρέψει το μέγεθος του πίνακα αριθμών. Και αυτό πρόκειται να είναι πολλές, ωστόσο υπάρχουν ακέραιοι φορές το μέγεθος του ακεραίου δεδομένου ότι είναι πόση μνήμη είναι πραγματικά ανάληψη. Έτσι, αν θέλω τον αριθμό των πραγμάτων στη συστοιχία, τότε Πάω να θέλετε να διαιρέσετε με το μέγεθος του ακεραίου. Εντάξει. Έτσι, αυτό μου επιτρέπει να περάσει σε μέγεθος εδώ. Γιατί πρέπει να περάσει σε μέγεθος σε όλα; Γιατί δεν μπορώ να κάνω μόνο εδώ int size = sizeof (άχυρα) / sizeof (int); Γιατί αυτό δεν λειτουργεί; [Φοιτητής] Δεν είναι μια καθολική μεταβλητή. [Bowden] Haystack υπάρχει και είμαστε περνώντας σε αριθμούς, όπως άχυρα, και αυτό είναι το είδος της μια προαναγγελία του τι είναι να έρθει. Ναι. [Φοιτητής] Haystack είναι μόνο η αναφορά σε αυτό, γι 'αυτό θα επιστρέψει πόσο μεγάλη είναι η αναφορά. Ναι. Αμφιβάλλω σε διάλεξη που έχετε δει ακόμα τη στοίβα πραγματικά, έτσι δεν είναι; Έχουμε μιλήσει μόνο γι 'αυτό. Έτσι, η στοίβα είναι όπου όλοι οι μεταβλητές σας πρόκειται να αποθηκευτεί. 

Κάθε μνήμης που διατίθενται για τις τοπικές μεταβλητές συμβαίνει στη στοίβα, και κάθε λειτουργία έχει το δικό του χώρο στη στοίβα, τις δικές πλαίσιο της στοίβας είναι ό, τι λέγεται. Έτσι, έχει κύρια πλαίσιο της στοίβας, και μέσα από αυτό θα υπάρχει αυτή σειρά αριθμών, και πρόκειται να είναι του μεγέθους sizeof (αριθμοί). Είναι πρόκειται να έχουν το μέγεθος των αριθμών που χωρίζονται ανάλογα με το μέγεθος των στοιχείων, αλλά ότι όλες οι ζωές μέσα στο πλαίσιο της κύριας στοίβα. Όταν λέμε αναζήτηση, έρευνα αποκτά το δικό του πλαίσιο της στοίβας, δικό του χώρο για να αποθηκεύσετε όλες τις τοπικές μεταβλητές. Αλλά αυτά τα επιχειρήματα - έτσι άχυρα δεν είναι ένα αντίγραφο ολόκληρου του πίνακα. Δεν περνούν σε ολόκληρο τον πίνακα ως αντίγραφο στην αναζήτηση. Περνάει μόνο μια αναφορά στο εν λόγω πίνακα. Έτσι, αναζήτηση μπορεί να έχει πρόσβαση αυτούς τους αριθμούς μέσω αυτής της αναφοράς. Είναι πρόσβαση ακόμα τα πράγματα που ζουν στο εσωτερικό του πλαισίου στοίβας κύριο του, αλλά βασικά, όταν φτάνουμε στο δείκτες, η οποία θα πρέπει να είναι σύντομα, αυτό είναι ό, τι είναι δείκτες. Οι δείκτες είναι απλά αναφορές σε πράγματα, και μπορείτε να χρησιμοποιήσετε δείκτες να έχουν πρόσβαση τα πράγματα που βρίσκονται σε πλαίσια σωρό άλλα πράγματα ». Έτσι ακόμα κι αν οι αριθμοί είναι το τοπικό έως το κύριο, μπορούμε να έχουμε πρόσβαση ακόμα μέσω αυτού του δείκτη. Αλλά δεδομένου ότι είναι μόνο ένα δείκτη και αυτό είναι ακριβώς μια αναφορά, sizeof (άχυρα) επιστρέφει μόνο το μέγεθος της αναφοράς η ίδια. Δεν επιστρέφει το μέγεθος του πράγματος είναι ότι δείχνει να. Δεν επιστρέφει το πραγματικό μέγεθος των αριθμών. Και έτσι αυτό δεν πρόκειται να λειτουργήσει όπως θέλουμε να. 

Ερωτήσεις σχετικά με αυτό; Οι δείκτες θα πρέπει να πάει σε σημαντικά πιο φρικιαστικές λεπτομέρειες στις εβδομάδες που έρχονται. Και αυτός είναι ο λόγος πολλά πράγματα που βλέπετε, τα περισσότερα πράγματα αναζήτησης ή είδος πράγματα, από όπου και αν σχεδόν όλοι θα πρέπει να λάβει το πραγματικό μέγεθος του πίνακα, επειδή σε C, δεν έχουμε καμία ιδέα ποιο είναι το μέγεθος του πίνακα είναι. Θα πρέπει να περάσει με το χέρι μέσα Και δεν μπορείτε να περάσετε το χέρι σε όλη τη σειρά, επειδή είστε απλά περνώντας κατά την περίοδο αναφοράς και δεν μπορεί να πάρει από το μέγεθος της αναφοράς. Εντάξει. Έτσι, τώρα θέλουμε να εφαρμόσουμε ό, τι εξηγήθηκε πριν. Μπορείτε να εργάζονται σε αυτό για ένα λεπτό, και δεν έχετε να ανησυχείτε για να πάρει τα πάντα τέλεια 100% εργασίας. Απλά γράψτε το ψευδοκώδικα το ήμισυ για το πώς νομίζετε ότι θα πρέπει να λειτουργεί. Εντάξει. Δεν πρέπει να γίνεται με εντελώς αυτό ακόμα. Αλλά κανείς δεν αισθάνεται άνετα με ό, τι μέχρι τώρα, σαν κάτι που μπορούμε να εργαστούμε από κοινού; Υπάρχει κάποιος που θέλουν να γίνουν εθελοντές; Ή θα πάρει τυχαία. Δεν χρειάζεται να είναι σωστό από κάθε μέτρο, αλλά κάτι μπορούμε να τροποποιήσουμε σε μια κατάσταση εργασίας. [Φοιτητής] Σίγουρα. Εντάξει >>. Έτσι, μπορείτε να αποθηκεύσετε την αναθεώρηση κάνοντας κλικ στο εικονίδιο Αποθήκευση. Είσαι Ramya, έτσι δεν είναι; >> [Φοιτητής] Ναι. >> [Bowden] Εντάξει. Έτσι τώρα μπορώ να προβάλλω την αναθεώρηση σας και ο καθένας μπορεί να τραβήξει μέχρι και την αναθεώρηση. Και εδώ έχουμε - Εντάξει. Έτσι Ramya πήγε με την αναδρομική λύση, η οποία είναι σίγουρα μια έγκυρη λύση. Υπάρχουν δύο τρόποι που μπορείτε να κάνετε αυτό το πρόβλημα. Μπορείτε να το κάνετε είτε επαναληπτικά ή αναδρομικά. Τα περισσότερα προβλήματα που αντιμετωπίζετε αυτό μπορεί να γίνει κατ 'επανάληψη μπορεί να γίνει και επαναληπτικά. Έτσι, εδώ έχουμε κάνει κατ 'επανάληψη. 

Μήπως κάποιος θέλει να ορίσει τι σημαίνει να κάνει μια αναδρομική συνάρτηση; [Φοιτητής] Όταν έχετε μια λειτουργία αυτοαποκαλείται και αυτοαποκαλείται συνέχεια μέχρι να βγαίνει με πραγματική και αληθινή. Ναι >>. Μια αναδρομική συνάρτηση είναι απλώς μια λειτουργία που καλεί τον εαυτό της. Υπάρχουν τρία μεγάλα πράγματα που μια αναδρομική συνάρτηση πρέπει να έχει. Το πρώτο είναι προφανώς, η ίδια αποκαλεί. Το δεύτερο είναι η βασική περίπτωση. Έτσι, σε κάποιο σημείο η λειτουργία πρέπει να σταματήσει να αυτοαποκαλείται, και αυτό είναι η βασική περίπτωση είναι για. Έτσι, εδώ ξέρουμε ότι θα πρέπει να σταματήσει, θα πρέπει να δώσουμε σε αναζήτηση μας όταν έναρξης ισούται τέλος - και θα πάμε πάνω τι σημαίνει αυτό. Αλλά τελικά, το τελευταίο πράγμα που είναι σημαντικό για αναδρομικές συναρτήσεις: οι λειτουργίες πρέπει να προσεγγίσουμε με κάποιο τρόπο την βασική περίπτωση. Όπως και αν δεν είστε ενημέρωση στην πραγματικότητα τίποτα όταν κάνετε τη δεύτερη αναδρομική κλήση, αν είστε κυριολεκτικά καλώντας απλά τη λειτουργία και πάλι με τα ίδια επιχειρήματα και καθολικές μεταβλητές δεν έχουν αλλάξει ή τίποτα, ποτέ δεν θα φτάσει την υπόθεση βάσης, οπότε αυτό είναι κακό. Θα είναι μια άπειρη αναδρομή και μια υπερχείλιση στοίβας. Αλλά εδώ βλέπουμε ότι η ενημέρωση συμβαίνει επειδή είμαστε ενημέρωση ξεκινήσει + τέλος / 2, είμαστε ενημέρωση τέλος το επιχείρημα εδώ, είμαστε ενημέρωση το επιχείρημα εκκίνησης εδώ. Έτσι, σε όλες τις αναδρομικές κλήσεις μας ενημερώνετε κάτι. Εντάξει. Θέλετε να μας καθοδηγήσει λύση σας; Σίγουρα >>. Είμαι χρησιμοποιώντας SearchHelp έτσι ώστε κάθε φορά που κάνω αυτή την κλήση της συνάρτησης Έχω την έναρξη της όπου ψάχνω στη σειρά και το τέλος από όπου ψάχνω τον πίνακα. 

Σε κάθε βήμα, όπου λέει ότι είναι το μεσαίο στοιχείο, το οποίο είναι αρχή + τέλος / 2, είναι ότι η ισότητα σε ό, τι ψάχνουμε; Και αν είναι, τότε το βρήκαμε, και υποθέτω ότι παίρνει πέρασε πάνω από τα επίπεδα αναδρομή. Και αν αυτό δεν είναι αλήθεια, τότε θα ελέγξει αν η μέση τιμή του πίνακα είναι πολύ μεγάλη, οπότε κοιτάμε το αριστερό μισό του πίνακα με τη μετάβαση από την αρχή μέχρι το μέσο δείκτη. Και αλλιώς κάνουμε το μισό τέλος. [Bowden] Εντάξει. Καλό ακούγεται. Εντάξει, έτσι, ένα ζευγάρι πράγματα, και στην πραγματικότητα, αυτό είναι ένα πολύ υψηλού επιπέδου πράγμα ότι ποτέ δεν θα πρέπει να ξέρετε για αυτό το μάθημα, αλλά είναι αλήθεια. Αναδρομικές συναρτήσεις, μπορείτε πάντα να ακούω ότι είναι μια κακή συμφωνία γιατί αν κατ 'επανάληψη καλέσει τον εαυτό σας πάρα πολλές φορές, μπορείτε να πάρετε υπερχείλιση στοίβας δεδομένου ότι, όπως είπα και πριν, κάθε λειτουργία έχει το δικό του πλαίσιο στοίβας. Έτσι, κάθε κλήση της επαναληπτικής λειτουργίας αποκτά το δικό του πλαίσιο στοίβας του. Έτσι, αν κάνετε 1.000 αναδρομικές κλήσεις, μπορείτε να πάρετε 1.000 καρέ στοίβα, και γρήγορα να σας οδηγήσουν να έχει πάρα πολλές πλαίσια στοίβα και να σπάσει τα πράγματα απλά. Έτσι, γι 'αυτό και αναδρομικές συναρτήσεις είναι γενικά κακή. Αλλά υπάρχει ένα ωραίο υποσύνολο των αναδρομικές συναρτήσεις που ονομάζεται ουρά-αναδρομικές συναρτήσεις, και αυτό συμβαίνει να είναι ένα παράδειγμα ενός όπου εάν ο μεταγλωττιστής προσέχει και θα έπρεπε, νομίζω - σε Clang αν περάσει αυτό το O2-σημαία τότε θα παρατηρήσετε αυτό είναι ουρά αναδρομική και να κάνει τα πράγματα καλά. 

Θα χρησιμοποιείτε τον ίδιο πλαίσιο στοίβα ξανά και ξανά για κάθε αναδρομική κλήση. Και έτσι επειδή είστε χρησιμοποιώντας το ίδιο πλαίσιο στοίβας, δεν χρειάζεται να ανησυχείτε για ποτέ στοίβα ξεχειλίζει, και την ίδια στιγμή, όπως σας είπα πριν, όπου τη στιγμή που θα επιστρέψει αληθής, τότε θα πρέπει να επιστρέψει μέχρι όλα αυτά τα πλαίσια στοίβας και το 10ο κλήση SearchHelp πρέπει να επιστρέψει στο 9ο, πρέπει να επιστρέψει στον 8ο. Έτσι, αυτό δεν πρέπει να συμβεί όταν οι λειτουργίες είναι αναδρομική ουρά. Και έτσι αυτό που κάνει αυτή η ουρά είναι αναδρομική λειτουργία ειδοποίηση ότι για οποιαδήποτε πρόσκληση για searchHelp η αναδρομική κλήση ότι είναι κάνει είναι αυτό που είναι επιστροφή. Έτσι, στην πρώτη πρόσκληση για SearchHelp, είτε θα επιστρέψει αμέσως ψευδή, επιστρέψει αμέσως αλήθεια, ή κάνουμε μια αναδρομική κλήση για SearchHelp όπου ό, τι είμαστε επιστροφή είναι αυτό που κλήση επιστρέφει. Και δεν θα μπορούσαμε να το κάνουμε αυτό, αν κάναμε κάτι σαν int x = SearchHelp, επιστροφή x * 2, μερικά μόνο τυχαία αλλαγή. 

Έτσι τώρα αυτή η αναδρομική κλήση, αυτό int x = SearchHelp αναδρομική κλήση, δεν είναι πλέον ουρά επαναληπτικό, γιατί πραγματικά δεν πρέπει να επιστρέψει πίσω σε μια προηγούμενη στοίβα πλαίσιο, έτσι ώστε ότι η προηγούμενη κλήση σε λειτουργία μπορεί στη συνέχεια να κάνουμε κάτι με την τιμή επιστροφής. Έτσι, αυτό δεν είναι αναδρομική ουρά, αλλά ό, τι είχαμε πριν είναι ωραία ουρά αναδρομική. Ναι. [Φοιτητής] Δεν θα έπρεπε η δεύτερη βασική περίπτωση να ελέγχονται πρώτα επειδή θα μπορούσε να υπάρξει μια κατάσταση όπου όταν περνάτε το επιχείρημα ότι έχετε ξεκινήσει = τέλος, αλλά είναι η αξία της βελόνας. Το ερώτημα αυτό δεν μπορεί να τρέξει σε περίπτωση όπου τέλος είναι η αξία της βελόνας ή να ξεκινήσετε = τέλος, κατάλληλα, ξεκινήστε = τέλος και δεν έχετε πραγματικά ελεγχθεί ότι η ιδιαίτερη αξία ακόμη, στη συνέχεια, ξεκινήστε + τέλος / 2 είναι ακριβώς πρόκειται να είναι η ίδια αξία. Αλλά έχουμε ήδη επιστρέψει ψευδείς και ποτέ δεν ελέγχεται πραγματικά την αξία. Έτσι, τουλάχιστον, στην πρώτη κλήση, αν το μέγεθος είναι 0, τότε θέλουμε να επιστρέψουμε ψευδείς. Αλλά αν το μέγεθος είναι 1, τότε ξεκίνημα δεν πρόκειται να ισούται τέλος, και θα ελέγχει τουλάχιστον το ένα στοιχείο. Αλλά νομίζω ότι έχετε δίκιο στο ότι μπορούμε να καταλήξουμε σε μια περίπτωση κατά την οποία αρχίζουν + τέλος / 2, έναρξη καταλήγει να είναι το ίδιο με την έναρξη + τέλος / 2, αλλά ποτέ δεν ελέγξαμε πραγματικότητα αυτό το στοιχείο. 

Έτσι, αν εμείς πρώτα να ελέγξετε είναι το μεσαίο στοιχείο η τιμή που ψάχνουμε, τότε μπορούμε να επιστρέψουν αμέσως αλήθεια. Αλλιώς αν είναι ίσες, τότε δεν υπάρχει νόημα να συνεχιστεί αφού είμαστε ακριβώς πρόκειται να ενημερώσει σε περίπτωση που είμαστε σε μια ενιαία στοιχείο του πίνακα. Αν μόνο στοιχείο που δεν είναι αυτός που ψάχνουμε, τότε όλα είναι λάθος. Ναι. [Μαθητής] Το θέμα είναι ότι, δεδομένου ότι το μέγεθος είναι στην πραγματικότητα μεγαλύτερο από τον αριθμό των στοιχείων στη συστοιχία, υπάρχει ήδη μια μετατόπιση - >> Έτσι θα μέγεθος - [Φοιτητής] Πείτε αν η σειρά ήταν μεγέθους 0, τότε η SearchHelp θα ελέγξει πραγματικά άχυρα από το 0 για την πρώτη πρόσκληση. Η σειρά έχει μέγεθος 0, έτσι το 0 είναι - >> Ναι. Υπάρχει ένα άλλο πράγμα που - θα μπορούσε να είναι καλή. Ας σκεφτούμε. Έτσι, αν η σειρά είχε 10 στοιχεία και το μεσαίο θα πάμε για να ελέγξετε δείκτη είναι 5, έτσι είμαστε έλεγχο 5, και ας πούμε ότι η τιμή είναι μικρότερη. Έτσι, είμαστε ρίχνουν τα πάντα μακριά από τις 5 και μετά. Έτσι ξεκινούν + τέλος / 2 θα είναι το τέλος μας νέα, Οπότε ναι, είναι πάντα πρόκειται να μείνουν και μετά το τέλος της σειράς. Εάν είναι μια περίπτωση που ήταν ακόμη ή περίεργο, τότε θα ελέγξει, ας πούμε, 4, αλλά είμαστε ακόμα μακριά ρίχνουν - Οπότε ναι, τέλος είναι πάντα πρόκειται να είναι πέρα ​​από το πραγματικό τέλος του πίνακα. Έτσι, τα στοιχεία που έχουμε με επίκεντρο, τέλος πάντα θα είναι η μία μετά από αυτό. Και έτσι, αν ποτέ κάνει έναρξη ίση τέλος, είμαστε σε μια σειρά μεγέθους 0. 

Το άλλο πράγμα που σκεφτόμουν είναι να ενημερώνετε την αρχή μέχρι να ξεκινήσει + τέλος / 2, έτσι αυτό είναι η υπόθεση ότι έχω πρόβλημα με, όπου αρχίζουν + τέλος / 2 είναι το στοιχείο είμαστε έλεγχο. Ας πούμε ότι είχαμε αυτό το 10-στοιχείο του πίνακα. Όποια και αν είναι. Έτσι ξεκινούν + τέλος / 2 πρόκειται να είναι κάτι σαν κι αυτό, και αν αυτό δεν είναι η τιμή, ας πούμε ότι θέλετε να ενημερώσετε. Η τιμή είναι μεγαλύτερη, έτσι θέλουμε να δούμε σε αυτό το μισό του πίνακα. Πώς, λοιπόν, είμαστε ενημέρωση ξεκίνημα, είμαστε ενημέρωση ξεκίνημα τώρα είναι αυτό το στοιχείο. Αλλά αυτό μπορεί να εξακολουθούν να εργάζονται, ή τουλάχιστον, μπορείτε να κάνετε εκκίνηση + τέλος / 2 + 1. [Φοιτητής] Δεν χρειάζεται να ξεκινήσετε + τέλος [δεν ακούγεται] >> Ναι. Έχουμε ήδη ελέγξει αυτό το στοιχείο και να ξέρετε ότι δεν είναι αυτό που ψάχνουμε. Γι 'αυτό και δεν χρειάζεται να ενημερώσετε ξεκίνημα να είναι αυτό το στοιχείο. Μπορούμε να παραλείψετε αυτό ακριβώς και ενημέρωση αρχίσει να είναι αυτό το στοιχείο. Και υπάρχει πάντα μια περίπτωση, ας πούμε, ότι αυτό ήταν τέλος, ώστε στη συνέχεια, ξεκινήστε θα είναι αυτό, ξεκινήστε το τέλος + / 2 θα είναι αυτό, + ξεκινήσει τέλος - Ναι, νομίζω ότι μπορεί να καταλήξει σε άπειρη αναδρομή. Ας πούμε ότι είναι απλά ένας πίνακας μεγέθους 2 ή σε ένα πίνακα μεγέθους 1. Νομίζω ότι αυτό θα λειτουργήσει. Έτσι, σήμερα, είναι ότι η αρχή και το τέλος στοιχείο είναι 1 πέρα ​​από αυτό. Έτσι, το στοιχείο ότι θα πάμε για να ελέγξετε είναι αυτό, και στη συνέχεια, όταν θα ενημερώσετε ξεκίνημα, είμαστε ενημέρωση αρχή να είναι 0 + 1/2, η οποία πρόκειται να μας τελειώσει πάλι με την έναρξη να είναι αυτό το στοιχείο. 

Έτσι είμαστε έλεγχο το ίδιο στοιχείο ξανά και ξανά. Έτσι, αυτή είναι η περίπτωση κατά την οποία κάθε αναδρομική κλήση πρέπει να ενημερώσετε πραγματικά κάτι. Έτσι πρέπει να κάνουμε αρχή + τέλος / 2 + 1, ή αλλιώς υπάρχει περίπτωση όπου δεν είμαστε πραγματικά έναρξη ενημέρωση. Όλοι είδατε αυτό; Εντάξει. Υπάρχει κάποιος που έχει ερωτήσεις σχετικά με αυτή τη λύση ή περισσότερα σχόλια; Εντάξει. Υπάρχει κάποιος που έχει μια επαναληπτική λύση που όλοι μπορούμε να δούμε; Μήπως κάνουμε όλοι αναδρομικά; Ή, επίσης, υποθέτω ότι αν ανοίξει το δικό της, τότε μπορεί να έχετε παρακαμφθεί προηγούμενο. Μήπως αυτόματα σώσει; Δεν είμαι θετικός. Υπάρχει κάποιος που έχει επαναληπτική; Μπορούμε να περπατάς με τα πόδια μαζί, αν δεν. Η ιδέα θα είναι η ίδια. Επαναληπτική λύση. Εμείς πάμε να θέλουν να κάνουν ουσιαστικά την ίδια ιδέα όπου θέλουμε να παρακολουθείτε το νέο τέλος της σειράς και τη νέα αρχή του πίνακα και να κάνουμε ότι ξανά και ξανά. Και αν αυτό που είμαστε την παρακολούθηση της ως την αρχή και το τέλος τέμνονται ποτέ, τότε δεν το βρείτε και μπορούμε να επιστρέψουμε ψευδείς. Λοιπόν, πώς μπορώ να το κάνω αυτό; Όποιος έχει προτάσεις ή κωδικό για μένα να σηκώσει; [Φοιτητής] Κάνετε ένα βρόχο while. Ναι >>. Θα έχετε την ευκαιρία να θέλουν να κάνουν ένα βρόχο. 

Μήπως έχετε κωδικό που θα μπορούσε να σηκώσει, ή ό, τι ήταν πας να προτείνετε; [Φοιτητής] Νομίζω πως ναι. >> Εντάξει. Αυτό κάνει τα πράγματα πιο εύκολα. Ποιο ήταν το όνομα σας; [Φοιτητής] Lucas. Αναθεώρηση 1. Εντάξει. Χαμηλή είναι αυτό που ονομάζεται ξεκινήσει πριν. Up δεν είναι αρκετά αυτό που ονομάζεται τέλος πριν. Στην πραγματικότητα, το τέλος είναι τώρα μέσα στον πίνακα. Είναι ένα στοιχείο που πρέπει να εξετάσουμε. Τόσο χαμηλό είναι 0, είναι μέχρι το μέγεθος του πίνακα - 1, και τώρα είμαστε looping, και εμείς τον έλεγχο - Υποθέτω ότι μπορείτε να περπατήσετε μέσα από αυτό. Ποια ήταν η σκέψη σας μέσα από αυτό; Περπατήστε μαζί μας μέσω κωδικού σας. [Φοιτητής] Σίγουρα. Κοιτάξτε την αξία άχυρα στη μέση και η σύγκρισή της με βελόνα. Έτσι, αν αυτό είναι μεγαλύτερο από ό, τι βελόνα σας, τότε θα θέλετε να - Ω, στην πραγματικότητα, αυτό θα πρέπει να είναι προς τα πίσω. Θα πάμε να θέλουν να πετάξουν το δεξί μισό, και έτσι ναι, αυτό θα πρέπει να είναι ο τρόπος. [Bowden] Έτσι, αυτό πρέπει να είναι μικρότερη; Είναι ότι αυτό που είπατε; >> [Φοιτητής] Ναι. [Bowden] Εντάξει. Λιγότερο. Έτσι, αν αυτό που ψάχνουμε σε είναι μικρότερη από ό, τι θέλουμε, τότε ναι, θέλουμε να ρίξει μακριά το αριστερό μισό, πράγμα που σημαίνει ότι ενημερώνετε ό, τι σκέφτεστε με μετακίνηση χαμηλά προς τα δεξιά της συστοιχίας. Αυτό φαίνεται καλό. Νομίζω ότι έχει το ίδιο θέμα που είπαμε στο προηγούμενο, όπου αν χαμηλό είναι 0 μέχρι και είναι 1, τότε χαμηλή έως + / 2 πρόκειται να συσταθεί για να είναι το ίδιο πράγμα ξανά. 

Και ακόμα κι αν αυτό δεν είναι η περίπτωση, είναι ακόμα πιο αποτελεσματική τουλάχιστον απλά να ρίξει μακριά το στοιχείο που μόλις κοίταξε την οποία γνωρίζουμε ότι είναι λάθος. Έτσι, χαμηλή έως + / 2 + 1 - >> [φοιτητής] Αυτό θα πρέπει να είναι ο άλλος τρόπος. [Bowden] Ή αυτό θα πρέπει να είναι - 1 και το άλλο πρέπει να είναι + 1. [Φοιτητής] Και θα πρέπει να υπάρχει ένα διπλό ίσον. >> [Bowden] Ναι. [Φοιτητής] Ναι. Εντάξει. Και τέλος, τώρα που έχουμε αυτό το + 1 - 1 πράγμα, είναι - δεν μπορεί να είναι - είναι ποτέ δυνατόν για χαμηλό για να καταλήξουμε σε μια τιμή μεγαλύτερη από ό, τι μέχρι; Νομίζω ότι ο μόνος τρόπος που μπορεί να συμβεί - Είναι δυνατόν; >> [Φοιτητής] Δεν ξέρω. Αλλά αν παίρνει περικοπεί και στη συνέχεια να παίρνει μείον 1 και ότι στη συνέχεια - >> Ναι. [Φοιτητής] Θα ήταν ίσως πάρει μπέρδεμα πάνω. Νομίζω ότι θα είναι καλό μόνο και μόνο επειδή για να καταλήξουν κάτω θα πρέπει να είναι ίση, νομίζω. Αλλά αν είναι ίσες, τότε δεν θα είχαμε κάνει το βρόχο, ενώ για να αρχίσει με και εμείς απλώς θα επιστρέψει την αξία. Έτσι, νομίζω ότι είμαστε καλά τώρα. Σημειώστε ότι ακόμη και αν αυτό το πρόβλημα δεν είναι πλέον αναδρομικό το ίδιο είδος των ιδεών ισχύουν όπου μπορούμε να δούμε πώς αυτό το τόσο εύκολα προσφέρεται σε ένα αναδρομικό διάλυμα από το γεγονός ότι είμαστε μόνο την ενημέρωση τους δείκτες ξανά και ξανά, φτιάχνουμε το πρόβλημα όλο και μικρότερα, είμαστε εστιάζοντας σε ένα υποσύνολο του πίνακα. [Φοιτητής] Αν χαμηλή είναι 0 και είναι μέχρι 1, θα είναι και οι δύο 0 + 1/2, η οποία θα πάει στο 0, και τότε κάποιος θα είναι + 1, το ένα θα είναι - 1. [Φοιτητής] Όταν εμείς τον έλεγχο της ισότητας; Όπως και αν το μεσαίο είναι πραγματικά βελόνα; Εμείς δεν κάνουμε σήμερα αυτό; Oh! Αν it's - Ναι. Εμείς απλά δεν μπορεί να κάνει το τεστ εδώ κάτω, γιατί ας πούμε το πρώτο μεσαίο - [Φοιτητής] Είναι πραγματικά ήθελε να μην πετάτε το δεσμευμένο. Έτσι, αν έχετε ρίξει μακριά το δεσμευμένο, θα πρέπει να το ελέγξει πρώτα ή οτιδήποτε άλλο. Αχ. Ναι. >> [Φοιτητής] Ναι. Έτσι τώρα έχουμε ρίξει μακριά το ένα αυτή τη στιγμή κοίταξε, πράγμα που σημαίνει ότι τώρα πρέπει να έχουν επίσης αν (άχυρα [(χαμηλή έως +) / 2] == βελόνα), τότε μπορούμε να επιστρέψουμε αλήθεια. Και αν έβαλα άλλο ή αν απλά, αυτό σημαίνει κυριολεκτικά το ίδιο πράγμα επειδή αυτό θα είχε επιστρέψει αλήθεια. Γι 'αυτό και θα βάλει άλλο αν, αλλά δεν πειράζει. 

Έτσι, αν αυτό το άλλο, άλλο αυτό, και αυτό είναι ένα κοινό πράγμα που κάνω όπου ακόμα κι αν είναι η περίπτωση κατά την οποία όλα είναι καλά εδώ, όπως το χαμηλό δεν μπορεί ποτέ να είναι μεγαλύτερη από ό, τι μέχρι, δεν αξίζει λογική για το αν αυτό είναι αλήθεια. Έτσι, μπορείτε επίσης να πούμε, ενώ χαμηλά είναι μικρότερη ή ίση με ή χαμηλή, ενώ είναι λιγότερο από ό, τι έτσι αν είναι ποτέ ίσες ή χαμηλό συμβαίνει για να περάσει επάνω, τότε μπορούμε να ξεφύγουμε από αυτόν τον βρόχο. Ερωτήσεις, προβλήματα, παρατηρήσεις; Εντάξει. Αυτό φαίνεται καλό. Τώρα θέλουμε να κάνουμε το είδος. Αν πάμε στη δεύτερη αναθεώρηση μου, βλέπουμε αυτούς τους ίδιους αριθμούς, αλλά τώρα που δεν είναι πλέον σε ταξινομημένη σειρά. Και θέλουμε να υλοποιήσουμε τη χρήση οποιουδήποτε είδους αλγόριθμο του O n log n. Έτσι, ο αλγόριθμος που νομίζετε ότι θα πρέπει να εφαρμόσουμε εδώ; >> [Φοιτητής] είδος συγχώνευσης. [Bowden] Ναι. Συγχώνευση sort είναι O (n log n), έτσι ώστε να είναι αυτό που πάμε να κάνουμε. Και το πρόβλημα θα είναι αρκετά παρόμοια, όπου προσφέρεται εύκολα σε μια αναδρομική λύση. Μπορούμε επίσης να καταλήξουμε σε μια επαναληπτική λύση, αν θέλουμε, αναδρομή, αλλά θα είναι πιο εύκολο εδώ και θα πρέπει να κάνουμε αναδρομή. Υποθέτω ότι θα περπατήσετε μέσα από το είδος συγχώνευσης κατ 'αρχάς, αν και υπάρχει ένα υπέροχο βίντεο για το είδος συγχώνευσης ήδη. [Γέλια] Έτσι συγχώνευση είδος υπάρχουν - Είμαι σπατάλη τόσο πολύ από αυτό το χαρτί. Ω, υπάρχει μόνο μία αριστερά. Έτσι συγχώνευση. Ω, 1, 3, 5. Εντάξει. Συγχώνευση παίρνει δύο χωριστές σειρές. Ατομικά οι δύο αυτές σειρές τόσο ταξινομημένο. Έτσι, αυτή η σειρά, 1, 3, 5, ταξινομημένο. Αυτός ο πίνακας, 0, 2, 4, ταξινομημένο. Τώρα τι συγχώνευση πρέπει να κάνουμε είναι να συνδυάσει σε ένα ενιαίο πίνακα που είναι η ίδια ταξινόμηση. Έτσι, θέλουμε μια σειρά μεγέθους 6 που θα έχουν αυτά τα στοιχεία στο εσωτερικό του σε ταξινομημένη σειρά. 

Και γι 'αυτό μπορούν να επωφεληθούν από το γεγονός ότι είναι ταξινομημένο αυτά τα δύο συστοιχίες να το κάνετε αυτό σε γραμμικό χρόνο, γραμμική έννοια του χρόνου, αν αυτή η σειρά είναι x μέγεθος και αυτό είναι y μέγεθος, τότε ο συνολικός αλγόριθμος θα πρέπει να είναι Ο (x + y). Εντάξει. Έτσι προτάσεις. [Φοιτητής] Θα μπορούσαμε να ξεκινήσουμε από την αριστερά; Έτσι, θα βάλετε το 0 κάτω πρώτα και στη συνέχεια το 1 και στη συνέχεια, εδώ είστε στο 2. Έτσι είναι το είδος του σαν να έχετε μια καρτέλα που κινείται προς τα δεξιά. >> [Bowden] Ναι. Για δύο από αυτούς τους πίνακες, αν επικεντρώνεται μόνο στην αριστερή στοιχείο. Επειδή είναι ταξινομημένο δύο συστοιχίες, γνωρίζουμε ότι αυτά τα 2 στοιχεία είναι τα μικρότερα στοιχεία σε οποιαδήποτε συστοιχία. Έτσι, αυτό σημαίνει ότι 1 από τα 2 αυτά στοιχεία θα πρέπει να είναι το μικρότερο στοιχείο σε νέα σειρά μας. Συμβαίνει ότι η μικρότερη είναι η μία στη δεξιά αυτή τη φορά. Έτσι παίρνουμε 0, τοποθετήστε το στην αριστερή πλευρά, επειδή το 0 είναι μικρότερο από 1, έτσι ώστε να λάβει 0, τοποθετήστε την στην πρώτη θέση μας, και στη συνέχεια θα ενημερώσει το να τώρα να επικεντρωθούν στο πρώτο στοιχείο. Και τώρα επαναλαμβάνουμε. Έτσι τώρα συγκρίνουμε 2 και 1. 1 είναι μικρότερη, οπότε θα εισάγετε 1. Ενημερώνουμε το δείκτη στο σημείο με αυτόν τον τύπο. Τώρα μπορούμε να το κάνουμε και πάλι, έτσι 2. Αυτό θα ενημερώσει, να συγκρίνουν αυτά τα 2, 3. Αυτή η ενημέρωση, στη συνέχεια, 4 και 5. Έτσι, αυτό είναι συγχώνευσης. 

Θα πρέπει να είναι αρκετά προφανές ότι είναι γραμμικό χρόνο από τότε που πήγαινε σε κάθε στοιχείο μια φορά. Και αυτό είναι το μεγαλύτερο βήμα για την εφαρμογή της συγχώνευσης είδος κάνει αυτό. Και δεν είναι ότι σκληρά. Ένα ζευγάρι πράγματα για να ανησυχούν είναι ας πούμε ότι ήταν συγχώνευση 1, 2, 3, 4, 5, 6. Στην περίπτωση αυτή, καταλήγουμε στο σενάριο όπου αυτό πρόκειται να είναι μικρότερο, τότε θα ενημερώσει αυτό το δείκτη, αυτό πρόκειται να είναι μικρότερο, να ενημερώσετε αυτό, αυτό είναι μικρότερο, και τώρα θα πρέπει να αναγνωρίσουν όταν έχετε ξεμείνει από πραγματικά στοιχεία για να συγκρίνουμε με. Από τη στιγμή που έχουν ήδη χρησιμοποιήσει όλη αυτή τη σειρά, τα πάντα σε αυτή την σειρά είναι τώρα μόλις εισαχθεί εδώ. Έτσι, αν ποτέ τρέξει στο σημείο όπου ένας από τους πίνακες μας είναι εντελώς συγχωνεύονται ήδη, τότε παίρνουμε μόνο όλα τα στοιχεία του άλλου πίνακα και τοποθετήστε τα μέσα στο άκρο της συστοιχίας. Έτσι μπορούμε να εισάγουμε μόνο 4, 5, 6. Εντάξει. Αυτό είναι ένα πράγμα που πρέπει να προσέξετε. Η εφαρμογή αυτή θα πρέπει να είναι το βήμα 1. Συγχώνευση ταξινομήσετε τότε με βάση αυτό, είναι 2 βήματα, 2 ανόητη βήματα. Ας δώσουμε ακριβώς αυτό το φάσμα. Έτσι συγχώνευση είδος, βήμα 1 είναι να σπάσει αναδρομικά τον πίνακα στη μέση. Έτσι, αυτή χωρίζεται σε σειρά μισά. Έχουμε τώρα 4, 15, 16, 50 και 8, 23, 42, 108. Και τώρα το κάνουμε ξανά και χωρίζουμε σε αυτά τα μισά. Απλά θα το κάνω σε αυτή την πλευρά. Έτσι 4, 15 και 16, 50. Εμείς θα κάνουμε το ίδιο πράγμα εδώ. Και τώρα που χωρίζεται στη μέση και πάλι. Και έχουμε 4, 15, 16, 50. Έτσι, αυτό είναι βασική περίπτωση μας. Μόλις οι συστοιχίες είναι μεγέθους 1, τότε θα σταματήσει με τη διάσπαση στη μέση. 

Τώρα τι θα κάνουμε με αυτό; Καταλήγουμε αυτό θα σπάσει σε 8, 23, 42, και 108. Έτσι, τώρα που είμαστε σε αυτό το σημείο, τώρα το βήμα δύο από είδος συγχώνευσης συγχώνευση μόνο ζεύγη στους καταλόγους. Έτσι θέλουμε να συγχωνεύσει αυτά. Απλά καλέστε συγχώνευση. Γνωρίζουμε συγχώνευση θα επιστρέψει αυτά σε ταξινομημένη σειρά. 4, 15. Τώρα θέλουμε να συγχώνευσή τους, και ότι θα επιστρέψει μια λίστα με αυτούς σε ταξινομημένη σειρά, 16, 50. Θα συγχωνεύσει αυτά - δεν μπορώ να γράψω - 8, 23 και 42, 108. Έτσι έχουμε νέα ζευγάρια φορά. Τώρα μόλις συγχώνευση και πάλι. Σημειώστε ότι κάθε μία από αυτές τις λίστες είναι ταξινομημένο από μόνη της, και στη συνέχεια μπορούμε να συγχωνευθούν μόνο αυτές τις λίστες για να πάρετε μια λίστα με μέγεθος 4, το οποίο είναι ταξινομημένο και να συγχωνεύσει τις δύο λίστες για να πάρετε μια λίστα με μέγεθος 4 που είναι ταξινομημένο. Και τέλος, μπορούμε να συγχωνεύσει τις δύο λίστες του μεγέθους 4 για να πάρετε μία λίστα μέγεθος 8 που είναι ταξινομημένο. Έτσι για να δείτε ότι αυτό είναι συνολικά n log n, έχουμε ήδη είδαμε ότι συγχώνευσης είναι γραμμική, έτσι όταν έχουμε να κάνουμε με τη συγχώνευση αυτών, έτσι όπως το συνολικό κόστος της συγχώνευσης για αυτές τις δύο λίστες είναι μόλις 2 επειδή - Ή επίσης, είναι από O n, n αλλά εδώ είναι μόνο αυτά τα 2 στοιχεία, γι 'αυτό είναι 2. Και οι 2 θα είναι 2 και οι 2 θα είναι 2 και οι 2 θα είναι 2, έτσι σε όλες τις συγχωνεύσεις που πρέπει να κάνουμε, καταλήγουν να κάνουν n. Like 2 + 2 + 2 + 2 είναι 8, η οποία είναι η, έτσι το κόστος της συγχώνευσης σε αυτό το σύνολο είναι n. Και τότε το ίδιο πράγμα εδώ. Θα συγχωνευθούν αυτά τα 2, τότε αυτά τα 2, και ατομικά συγχώνευση αυτή θα λάβει τέσσερις πράξεις, αυτή η συγχώνευση θα λάβει τέσσερις πράξεις, αλλά για μια ακόμη φορά, μεταξύ όλων αυτών, καταλήγουμε συγχώνευση n συνολικά τα πράγματα, έτσι και αυτό το βήμα παίρνει n. Και έτσι κάθε επίπεδο διαρκεί n στοιχεία που συγχωνεύονται. 

Και πόσα επίπεδα υπάρχουν; Σε κάθε επίπεδο, σειρά μας μεγαλώνει ανάλογα με το μέγεθος 2. Εδώ συστοιχίες μας είναι μεγέθους 1, εδώ από όπου και αν το μέγεθος της 2, εδώ από όπου και αν μεγέθους 4, και, τέλος, από όπου και αν το μέγεθος 8. Έτσι, δεδομένου ότι ο διπλασιασμός, υπάρχουν πρόκειται να είναι ένα σύνολο από n log από αυτά τα επίπεδα. Έτσι, με log n επίπεδα, κάθε επίπεδο, λαμβάνοντας n σύνολο της δραστηριότητας, έχουμε ένα log n n αλγόριθμο. Ερωτήσεις; Έχουν οι άνθρωποι ήδη σημειώσει πρόοδο σχετικά με το πώς να εφαρμόσουν αυτό; Υπάρχει κάποιος ήδη σε μια κατάσταση όπου μπορώ ακριβώς να σηκώσει τον κωδικό τους; Μπορώ να σας δώσω ένα λεπτό. Αυτός πρόκειται να είναι περισσότερο. Συστήνω ιδιαίτερα επαναληφθεί - Δεν χρειάζεται να κάνετε αναδρομή για συγχώνευση γιατί να κάνω αναδρομή για συγχώνευση, εσείς πρόκειται να πρέπει να περάσει μια δέσμη των διαφορετικών μεγεθών. Μπορείτε, αλλά είναι ενοχλητικό. Αλλά αναδρομή για το ίδιο είδος είναι αρκετά εύκολο. Απλά καλέστε κυριολεκτικά είδος στο αριστερό μισό, είδος στο δεξί μισό. Εντάξει. Όποιος έχει κάτι που μπορώ να σηκώσει ακόμα; Ή αλλιώς θα σας δώσω ένα λεπτό. Εντάξει. Όποιος έχει κάτι που μπορεί να λειτουργήσει με; Ή αλλιώς θα δουλέψουν με αυτό και στη συνέχεια, αναπτύξτε από εκεί. 

Όποιος έχει περισσότερο από αυτό που μπορώ να σηκώσει; [Φοιτητής] Ναι. Μπορείτε να σηκώσει ορυχείο. >> Εντάξει. Ναι! [Φοιτητής] Υπήρχαν πολλές προϋποθέσεις. >> Ω, πυροβολούν. Μπορείτε να - [Φοιτητής] Έχω να το αποθηκεύσετε. Ναι >>. Γι 'αυτό και έκανα τη συγχώνευση χωριστά. Ναι, αλλά δεν είναι τόσο άσχημα. Εντάξει. Έτσι το είδος είναι η ίδια ακριβώς ζητούν mergeSortHelp. Εξηγήστε μας τι mergeSortHelp κάνει. [Φοιτητής] MergeSortHelp λίγο πολύ κάνει τα δύο βασικά βήματα, η οποία είναι να ταξινομεί κάθε μισό της συστοιχίας και κατόπιν να συγχωνεύσει και τους δύο. [Bowden] Εντάξει, έτσι ώστε να μου δώσει μια δεύτερη. Νομίζω ότι αυτό - >> [φοιτητής] θα πρέπει να - Ναι. Είμαι λείπει κάτι. Σε συγχώνευση, συνειδητοποιώ ότι πρέπει να δημιουργηθεί μια νέα σειρά γιατί δεν θα μπορούσε να το κάνει στη θέση του. Ναι >>. Δεν μπορείς. Διορθώστε. [Φοιτητής] Έτσι, μπορώ να δημιουργήσω ένα νέο πίνακα. Ξέχασα το τέλος της συγχώνευσης την εκ νέου αλλαγή. Εντάξει. Χρειαζόμαστε μια νέα σειρά. Σε τέτοια συγχώνευση, αυτό είναι σχεδόν πάντα αλήθεια. Μέρος του κόστους για ένα καλύτερο αλγόριθμο-σοφός είναι σχεδόν πάντα χρειάζεται να χρησιμοποιήσετε λίγο περισσότερη μνήμη. Μέχρι εδώ, δεν έχει σημασία πώς θα το κάνετε συγχώνευση είδος, αναπόφευκτα θα χρειαστεί να χρησιμοποιήσετε κάποια επιπλέον μνήμη. Αυτός ή αυτή δημιούργησε μια νέα σειρά. Και μετά λέτε στο τέλος το μόνο που χρειάζεται να αντιγράψετε νέα σειρά στην αρχική σειρά. [Φοιτητής] Έτσι νομίζω, ναι. Δεν ξέρω αν αυτό λειτουργεί από την άποψη της καταμέτρησης από την αναφορά ή οτιδήποτε άλλο - Ναι, αυτό θα λειτουργήσει. >> [Φοιτητής] Εντάξει. Μήπως προσπαθείτε λειτουργεί αυτό; >> [Φοιτητής] Όχι, όχι ακόμα. Εντάξει >>. Δοκιμάστε να εκτελέσετε αυτό, και στη συνέχεια θα μιλήσω γι 'αυτό για ένα δευτερόλεπτο. [Φοιτητής] θα πρέπει να έχει όλα τα πρωτότυπα λειτουργία και τα πάντα, όμως, έτσι δεν είναι; Τα πρωτότυπα συναρτήσεων. Εννοείς όπως - Ναι. Ταξινόμηση καλεί mergeSortHelp. 

Έτσι, προκειμένου για το είδος να καλέσετε mergeSortHelp, mergeSortHelp πρέπει είτε έχουν καθοριστεί πριν από το είδος ή το μόνο που χρειάζεται το πρωτότυπο. Απλά αντιγράψτε και επικολλήστε αυτό. Και ομοίως, mergeSortHelp καλεί συγχώνευση, αλλά η συγχώνευση δεν έχει οριστεί ακόμη, έτσι ώστε να μπορούμε να την αφήσουμε mergeSortHelp ξέρω ότι η συγχώνευση είναι αυτό πρόκειται να μοιάσει, και αυτό είναι αυτό. Έτσι mergeSortHelp. Έχουμε εδώ ένα ζήτημα όπου δεν έχουμε καμία περίπτωση βάση. MergeSortHelp είναι αναδρομικές, έτσι ώστε κάθε αναδρομική συνάρτηση θα χρειαστεί κάποιο είδος της υπόθεσης βάση για να ξέρει πότε να σταματήσει κατ 'επανάληψη το ίδιο καλώντας. Τι είναι η βασική περίπτωση μας πρόκειται να εδώ; Ναι. [Φοιτητής] Εάν το μέγεθος είναι 1; >> [Bowden] Ναι. Έτσι, όπως είδαμε εκεί, σταματήσαμε συστοιχίες διάσπαση μόλις φτάσαμε σε συστοιχίες μεγέθους 1, το οποίο αναπόφευκτα οι ίδιοι ταξινομημένο. Έτσι, αν το μέγεθος είναι ίσο με 1, γνωρίζουμε ότι ο πίνακας είναι ήδη ταξινομημένο, έτσι μπορούμε απλά να επιστρέψουν. 

Σημειώστε ότι είναι άκυρη, έτσι δεν επιστρέφουν τίποτα συγκεκριμένο, απλά επιστρέφει. Εντάξει. Έτσι, αυτό είναι βασική περίπτωση μας. Υποθέτω ότι βασική περίπτωση μας θα μπορούσε επίσης να είναι, αν τυχαίνει να συγχωνεύονται μια σειρά μεγέθους 0, που πιθανώς να θέλετε να σταματήσει σε κάποιο σημείο, έτσι μπορούμε να πούμε μόνο μέγεθος μικρότερο από 2 ή μικρότερη από ή ίση με 1 έτσι ώστε αυτό θα λειτουργήσει για οποιαδήποτε συστοιχία τώρα. Εντάξει. Έτσι, αυτό είναι βασική περίπτωση μας. Τώρα θέλετε να μας καθοδηγήσει συγχώνευση; Τι σημαίνουν όλες αυτές οι περιπτώσεις; Μέχρι εδώ, κάνουμε ακριβώς την ίδια ιδέα, η - [Φοιτητής] θα πρέπει να περνούν το μέγεθος με όλες τις κλήσεις mergeSortHelp. Πρόσθεσα μέγεθος ως πρόσθετη πρωτοβάθμιας και δεν υπάρχει, όπως το μέγεθος / 2. [Bowden] Ω, μέγεθος / 2, το μέγεθος / 2. >> [Μαθητής] Ναι, και επίσης στην ανωτέρω λειτουργία, καθώς και. [Bowden] Εδώ; >> [Φοιτητής] Απλά μέγεθος. >> [Bowden] Αχ. Μέγεθος, το μέγεθος; >> [Φοιτητής] Ναι. [Bowden] Εντάξει. Επιτρέψτε μου να σκεφτούμε για ένα δευτερόλεπτο. Έχουμε τρέξει σε ένα θέμα; Είμαστε θεραπεία πάντα το αριστερό ως 0. >> [Φοιτητής] Όχι. Αυτό είναι πολύ λάθος. Λυπάμαι. Θα πρέπει να είναι εκκίνηση. Ναι. [Bowden] Εντάξει. Μου αρέσει ότι η καλύτερη. Και τέλος. Εντάξει. Έτσι, τώρα θέλετε να μας καθοδηγήσει συγχώνευση; >> [Φοιτητής] Εντάξει. Είμαι απλά περπατώντας μέσα από αυτή τη νέα σειρά που έχω δημιουργήσει. Το μέγεθός του είναι το μέγεθος του τμήματος της συστοιχίας που θέλουμε να ταξινόμηση και προσπαθεί να βρει το στοιχείο που θα πρέπει να τεθούν σε νέα σειρά βήμα. Έτσι, για να γίνει αυτό, πρώτα Φεύγω αν το αριστερό μισό του πίνακα εξακολουθεί να έχει κάποια περισσότερα στοιχεία, και αν δεν το κάνει, τότε θα πάει κάτω σε αυτό το άλλο όρο, που λέει ακριβώς εντάξει, πρέπει να είναι στη σωστή σειρά, και θα βάλουμε ότι στην τρέχουσα δείκτη του newArray. 

Και στη συνέχεια, αλλιώς, Φεύγω εάν η δεξιά πλευρά του πίνακα είναι επίσης τελειώσει, οπότε εγώ απλά βάλτε στο αριστερό. Αυτό δεν θα μπορούσε πράγματι να είναι απαραίτητη. Δεν είμαι σίγουρος. Αλλά έτσι κι αλλιώς, οι άλλες δύο επιταγή ποια από τις δύο είναι μικρότερα στην αριστερή ή τη δεξιά. Και επίσης, σε κάθε περίπτωση, είμαι προσαύξηση ανάλογα με το ποια θα αυξήσετε κράτησης θέσης. [Bowden] Εντάξει. Αυτό φαίνεται καλό. Υπάρχει κάποιος που έχει τα σχόλια ή ανησυχίες ή ερωτήσεις; Έτσι, οι τέσσερις περιπτώσεις που έχουμε να φέρει τα πράγματα σε λίγο είναι - ή θα μοιάζει με πέντε - αλλά θα πρέπει να εξετάσει κατά πόσον η αριστερή παράταξη έχει εξαντληθεί τα πράγματα που πρέπει να συγχωνευθούν, αν η δεξιά διάταξη έχει εξαντληθεί τα πράγματα που πρέπει να συγχωνευθούν - Είμαι δείχνει σε τίποτα. Έτσι, αν η αριστερή παράταξη έχει εξαντληθεί τα πράγματα ή η δεξιά διάταξη έχει εξαντληθεί τα πράγματα. Πρόκειται για δύο περιπτώσεις. Χρειαζόμαστε επίσης την τετριμμένη περίπτωση του αν η αριστερά πράγμα είναι λιγότερο από ό, τι το σωστό πράγμα. Στη συνέχεια, θέλουμε να επιλέξετε το αριστερό πράγμα. Αυτοί είναι οι περιπτώσεις. Έτσι, αυτό ήταν σωστό, έτσι ώστε να είναι αυτό. Array αριστερά. Είναι 1, 2, 3. Εντάξει. Οπότε ναι, αυτά είναι τα τέσσερα πράγματα που ίσως να θέλετε να το κάνετε. Και εμείς δεν θα πάει πέρα ​​από μια επαναληπτική λύση. Δεν θα συνιστούσα - Συγχώνευση είδος είναι ένα παράδειγμα μιας συνάρτησης που είναι και οι δύο δεν ουρά αναδρομικό δεν είναι εύκολο να γίνει ουρά αναδρομικό αλλά επίσης δεν είναι πολύ εύκολο να γίνει επαναληπτική. Αυτό είναι πολύ εύκολο. Αυτό το είδος της εφαρμογής της συγχώνευσης, συγχώνευση, δεν έχει σημασία τι θα κάνεις, θα πάμε να οικοδομήσουμε συγχώνευση. 

Έτσι συγχώνευση είδος χτισμένο στην κορυφή της συγχώνευσης είναι αναδρομικά μόνο αυτές οι τρεις γραμμές. Επαναληπτικά, είναι πιο ενοχλητικό και πιο δύσκολο να σκεφτούμε. Να σημειωθεί όμως ότι δεν είναι αναδρομική από την ουρά mergeSortHelp - όταν αυτοαποκαλείται - χρειάζεται ακόμη να κάνουμε τα πράγματα μετά από αυτό επιστρέφει αναδρομική κλήση. Έτσι, αυτό το πλαίσιο στοίβας πρέπει να συνεχίσει να υπάρχει ακόμα και μετά την κλήση αυτή. Και στη συνέχεια, όταν σας καλούν αυτό, το πλαίσιο στοίβας πρέπει να συνεχίσει να υπάρχει γιατί ακόμα και μετά από αυτή την κλήση, θα πρέπει ακόμα να συγχωνευθούν. Και αυτό είναι προβληματικό να κάνουν αυτό το αναδρομικό ουρά. Ερωτήσεις; Εντάξει. Έτσι, πηγαίνει πίσω για να ταξινομήσετε - ω, υπάρχουν δύο πράγματα που θέλω να δείξω. Εντάξει. Πηγαίνοντας πίσω στο είδος, θα το κάνετε αυτό γρήγορα. 'Η ψάξτε. Ταξινόμηση; Ταξινόμηση. Ναι. Πηγαίνοντας πίσω στις απαρχές του είδους. Θέλουμε να δημιουργήσουμε έναν αλγόριθμο που ταξινομεί το array χρησιμοποιώντας οποιοδήποτε αλγόριθμο O από το n. Λοιπόν, πώς είναι αυτό δυνατόν; Υπάρχει κάποιος που να έχει οποιοδήποτε είδος του - I υπαινίχθηκε πριν σε - Αν είμαστε έτοιμοι να βελτιωθεί από n log n Ξ της n, έχουμε βελτιώσει τον αλγόριθμο μας χρόνος-σοφός, πράγμα που σημαίνει τι πρόκειται να πρέπει να κάνουμε για να αναπληρώσετε αυτό; [Φοιτητής] Space. Ναι >>. Εμείς πάμε για να χρησιμοποιεί περισσότερο χώρο. Και δεν είναι καν μόνο περισσότερο χώρο, είναι εκθετικά περισσότερο χώρο. Νομίζω λοιπόν ότι αυτό το είδος του αλγορίθμου είναι ψευδο κάτι, polynom ψευδο - ψευδο - Δεν μπορώ να θυμηθώ. Ψευδο κάτι. Αλλά αυτό συμβαίνει γιατί πρέπει να χρησιμοποιήσουμε τόσο πολύ χώρο ότι αυτό είναι εφικτό, αλλά δεν είναι ρεαλιστικό. 

Και πώς θα επιτευχθεί αυτό; Μπορούμε να το επιτύχουμε αυτό, αν εγγυόμαστε ότι κάποιο συγκεκριμένο στοιχείο του πίνακα είναι κάτω από ένα ορισμένο μέγεθος. Έτσι, ας πούμε ότι το μέγεθος είναι 200, κάθε στοιχείο σε μία συστοιχία είναι κάτω από το μέγεθος 200. Και αυτό είναι πραγματικά πολύ ρεαλιστικό. Μπορείτε πολύ εύκολα να έχουν μια σειρά που ξέρετε τα πάντα σε αυτό πρόκειται να είναι μικρότερη από κάποιο αριθμό. Όπως και αν έχετε κάποια απολύτως μαζική φορέα ή κάτι αλλά ξέρετε τα πάντα πρόκειται να είναι μεταξύ 0 και 5, τότε πρόκειται να είναι πολύ πιο γρήγορα για να γίνει αυτό. Και η δεσμευμένη σε οποιοδήποτε από τα στοιχεία είναι 5, έτσι αυτό δεσμεύεται, δηλαδή πόση μνήμη θα πάμε να χρησιμοποιούν. Έτσι, το όριο είναι 200. Στη θεωρία υπάρχει πάντα ένα δεσμευμένο αφού ένας ακέραιος μπορεί να είναι μόνο μέχρι 4 δισεκατομμύρια, αλλά αυτό είναι ρεαλιστικό δεδομένου ότι τότε θα ήμασταν χρήση χώρου της τάξης των 4 δισ. ευρώ. Έτσι, αυτό είναι εξωπραγματικό. Αλλά εδώ θα σας πούμε δεσμεύεται μας είναι 200. Το τέχνασμα για να το κάνουμε σε n Ξ είναι να κάνουμε μια άλλη σειρά που ονομάζεται Η ΔΕΣΜΕΥΣΗ του μεγέθους. Έτσι, στην πραγματικότητα, αυτό είναι μια συντόμευση για - Εγώ πραγματικά δεν ξέρω αν Clang το κάνει αυτό. Αλλά στο GCC τουλάχιστον - I'm Clang υποθέτοντας ότι κάνει πάρα πολύ - αυτό θα προετοιμαστεί μόνο ολόκληρη τη συστοιχία να είναι 0s. Έτσι, αν δεν θέλω να το κάνω αυτό, τότε θα μπορούσα να κάνω χωριστά για (int i = 0? i <BOUND? i + +) και Η [i] = 0? Μέχρι τώρα όλα είναι αρχικοποιείται σε 0. Έχω επαναλάβει κατά σειρά μου, και αυτό που κάνω εγώ είναι μετρώντας τον αριθμό των κάθε - Ας πάμε εδώ κάτω. Έχουμε 4, 15, 16, 50, 8, 23, 42, 108. Τι είμαι καταμέτρηση είναι ο αριθμός των εμφανίσεων του καθενός από αυτά τα στοιχεία. Ας πραγματικά να προσθέσει ένα ζευγάρι περισσότερο εδώ με μερικές επαναλήψεις. Έτσι, η αξία που έχουμε εδώ, η αξία της θα είναι array [i]. Έτσι val θα μπορούσε να είναι 4 ή 8 ή οτιδήποτε άλλο. Και τώρα είμαι μετρώντας πόσα από αυτή την τιμή που έχω δει, Η ούτως [val] + +? Αφού γίνει αυτό, Η πρόκειται να δούμε κάτι σαν 0001. Ας κάνουμε Η [val] - BOUND + 1. 

Τώρα αυτό είναι μόνο να λογοδοτήσουν για το γεγονός ότι είμαστε ξεκινώντας από το 0. Έτσι, εάν 200 πρόκειται να είναι μεγαλύτερο αριθμό μας, τότε 0-200 είναι 201 πράγματα. Η Οπότε, αυτό θα μοιάζει 00001, γιατί έχουμε ένα 4. Τότε θα έχουμε 0001, όπου θα έχουμε ένα 1 στο 8ο δείκτη του αριθμού. Θα έχει 2 στην 23η δείκτη του αριθμού. Θα έχουμε ένα 2 στο δείκτη 42η μετράνε. Έτσι, μπορούμε να χρησιμοποιήσουμε μετράνε. Έτσι num_of_item = Η [i]. Και έτσι αν num_of_item είναι 2, αυτό σημαίνει ότι θέλουμε να εισάγετε 2 του αριθμού i ταξινομημένο σε σειρά μας. Γι 'αυτό και πρέπει να παρακολουθείτε πόσο μακριά είμαστε στη σειρά. Έτσι δείκτης = 0. Array - Θα γράψω απλά. Μετρά - array [index + +] = i? Είναι αυτό που θέλω; Νομίζω ότι είναι αυτό που θέλω. Ναι, αυτό φαίνεται καλό. Εντάξει. Έτσι, ο καθένας έχει καταλάβει ποιος είναι ο σκοπός του Η σειρά μου είναι; Είναι μετρώντας τον αριθμό των εμφανίσεων καθενός από αυτούς τους αριθμούς. Στη συνέχεια, είμαι πάνω από την επανάληψη αυτού του πίνακα Η, και η i-θέση στη συστοιχία Η είναι ο αριθμός του i είναι που θα πρέπει να εμφανίζονται σε ταξινομημένη σειρά μου. Γι 'Η από 4 πρόκειται να είναι 1 Η και από 8 πρόκειται να είναι 1, Η από 23 θα είναι 2. Έτσι, αυτό είναι το πώς πολλοί από αυτούς θέλω να εισαγάγει ταξινομημένο σειρά μου. Στη συνέχεια, εγώ απλά κάνω αυτό. Είμαι εισαγωγή num_of_item i είναι ταξινομημένο σε σειρά μου. 

Ερωτήσεις; Και έτσι πάλι, αυτό είναι γραμμικό χρόνο από τη στιγμή που είναι ακριβώς πάνω από την επανάληψη αυτή τη φορά, αλλά είναι επίσης γραμμική σε ό, τι ο αριθμός αυτός τυχαίνει να είναι, και γι 'αυτό εξαρτάται σε μεγάλο βαθμό από το τι σας είναι συνδεδεμένη. Με δεσμεύεται από 200, αυτό δεν είναι τόσο άσχημα. Αν δεσμευμένο σας πρόκειται να είναι 10.000, τότε αυτό είναι λίγο χειρότερα, αλλά αν δεσμεύεται σας πρόκειται να είναι 4 δισ. ευρώ, αυτό είναι τελείως ρεαλιστικό και αυτή η σειρά θα πρέπει να είναι μεγέθους 4 δισ. ευρώ, το οποίο δεν είναι ρεαλιστικό. Έτσι αυτό είναι αυτό. Ερωτήσεις; [Ακούγεται ανταπόκριση των φοιτητών] >> Εντάξει. Κατάλαβα ένα άλλο πράγμα, όταν πηγαίναμε κατευθείαν. Νομίζω ότι το πρόβλημα ήταν του Lucas και πιθανώς κάθε ένα που έχουμε δει. Ξέχασα εντελώς. Το μόνο πράγμα που ήθελα να σχολιάσω είναι ότι όταν έχουμε να κάνουμε με πράγματα όπως δείκτες, δεν μπορείτε ποτέ πραγματικά να δείτε αυτό όταν είστε γραπτώς μια για βρόχο, αλλά τεχνικά, όταν έχουμε να κάνουμε με αυτούς τους δείκτες, θα πρέπει να είναι πάντα λίγο πολύ ασχολούνται με μη προσημασμένους ακεραίους. Ο λόγος για αυτό είναι όταν έχεις να κάνεις με υπογραφή ακέραιοι, οπότε αν έχετε 2 υπογράψει ακέραιοι και τα προσθέτετε μαζί και καταλήγουν πάρα πολύ μεγάλο, τότε θα καταλήξετε με έναν αρνητικό αριθμό. Έτσι, αυτό είναι ό, τι είναι ακέραιος υπερχείλιση. 

Αν μπορώ να προσθέσω 2 δισεκατομμυρίων και 1 δισ. ευρώ, θα καταλήξετε με αρνητικό 1 δισ. ευρώ. Αυτό είναι το πώς ακέραιοι λειτουργεί σε υπολογιστές. Έτσι, το πρόβλημα με τη χρήση - Αυτό είναι πρόστιμο, εκτός αν χαμηλό συμβαίνει να είναι 2 δις και μέχρι να συμβεί αυτό είναι 1 δισ. ευρώ, τότε αυτό θα είναι αρνητική 1 δισ. ευρώ και στη συνέχεια θα πάμε να τα διαιρέσουμε με το 2 και καταλήγουν με αρνητική 500 εκατ. ευρώ. Έτσι, αυτό είναι μόνο ένα θέμα, αν τυχαίνει να ψάχνουν μέσα από μια σειρά δισεκατομμύρια των πραγμάτων. Αλλά αν συμβεί + χαμηλή έως υπερχείλιση, τότε αυτό είναι ένα πρόβλημα. Μόλις κάνουμε τους ανυπόγραφο, στη συνέχεια, 2 δισεκατομμύρια συν 1 δισεκατομμύριο 3 δισ. ευρώ. 3 δισεκατομμύρια διαιρούμενο δια του 2 είναι 1,5 δισ. ευρώ. Έτσι, από τη στιγμή που είσαι ανυπόγραφο, όλα είναι τέλεια. Και έτσι αυτό είναι επίσης ένα θέμα όταν είστε γραπτώς σας για βρόχους, και στην πραγματικότητα, κάνει πιθανώς αυτόματα. Θα πραγματικά φωνάζω μόνο σε σας. Έτσι, αν ο αριθμός αυτός είναι πολύ μεγάλο για να είναι μέσα σε μόλις έναν ακέραιο, αλλά θα ταίριαζε σε ένα ανυπόγραφο ακέραιος, θα φωνάζω σε σας, έτσι ώστε να είναι γιατί ποτέ δεν θα τρέξει σε πραγματικά το θέμα. Μπορείτε να δείτε ότι ο δείκτης δεν πρόκειται ποτέ να είναι αρνητική, και έτσι όταν είστε επανάληψη πάνω από έναν πίνακα, μπορείτε σχεδόν πάντα λένε unsigned int i, αλλά πραγματικά δεν χρειάζεται να. Τα πράγματα πηγαίνουν να εργαστούν λίγο πολύ το ίδιο καλά. Εντάξει. [Ψίθυροι] Τι ώρα είναι; Το τελευταίο πράγμα που ήθελα να δείξω - και εγώ θα κάνω μόνο αυτό πραγματικά γρήγορα. Ξέρεις πώς έχουμε # define έτσι μπορούμε να ορίσουμε ως MAX # 5 ή κάτι άλλο; Ας μην κάνουμε MAX. # Define δεσμεύονται ως 200. Αυτό είναι ό, τι κάναμε πριν. Που καθορίζει μια σταθερή, το οποίο είναι ακριβώς πρόκειται να αντιγραφεί και επικολληθεί όπου τυχαίνει να γράψει ΔΕΣΜΕΥΣΗ. 

Έτσι, μπορούμε να κάνουμε στην πραγματικότητα περισσότερο με # ορίζει. Μπορούμε να ορίσουμε # λειτουργίες. Δεν είναι πραγματικά λειτουργίες, αλλά θα καλέσει τους λειτουργίες. Ένα παράδειγμα θα ήταν κάτι σαν MAX (x, y) ορίζεται ως (χ <y y:? X). Εντάξει. Έτσι, θα πρέπει να συνηθίσουν στην τριμερή σύνταξη του τελεστή, αλλά είναι μικρότερη από χ y; Επιστροφή y, x επιστρέψουν άλλο. Έτσι, μπορείτε να δείτε μπορείτε να κάνετε αυτό μια ξεχωριστή λειτουργία, και η λειτουργία θα μπορούσε να είναι όπως bool MAX διαρκεί 2 επιχειρήματα, επιστρέφει αυτό. Αυτό είναι ένα από τα πιο κοινά βλέπω γίνει σαν αυτό. Καλούμε τους μακροεντολές. Αυτή είναι μια μακροεντολή. Αυτό είναι μόνο η σύνταξη γι 'αυτό. Μπορείτε να γράψετε μια μακροεντολή για να κάνετε ό, τι θέλετε. Βλέπετε συχνά μακροεντολές για τον εντοπισμό σφαλμάτων και printfs πράγματα. Έτσι, ένα είδος printf, υπάρχουν ειδικές σταθερές σε C, όπως υπογραμμίζουν LINE υπογραμμίζουν, 2 υπογραμμίζει LINE υπογραμμίζουν, και υπάρχει επίσης νομίζω 2 υπογραμμίζει FUNC. Αυτό θα μπορούσε να είναι αυτό. Κάτι σαν αυτό. Αυτά τα πράγματα θα αντικατασταθεί με το όνομα της συνάρτησης ή ο αριθμός της γραμμής που βρίσκεστε. Συχνά, μπορείτε να γράψετε τον εντοπισμό σφαλμάτων printfs ότι εδώ κάτω θα μπορούσα να γράψω στη συνέχεια, μόλις DEBUG και θα εκτυπώσει τον αριθμό της γραμμής και τη λειτουργία που τυχαίνει να είναι σε ότι αντιμετώπισε τη δήλωση DEBUG. Και μπορείτε επίσης να εκτυπώσετε άλλα πράγματα. Έτσι, ένα πράγμα που πρέπει να προσέξετε είναι αν τυχαίνει να καθορίσει # DOUBLE_MAX ως κάτι σαν 2 * y και x 2 *. Έτσι, για λόγους οτιδήποτε άλλο, τυχαίνει να το κάνουμε αυτό πολύ. Έτσι, βεβαιωθείτε ότι μια μακροεντολή. Αυτό είναι στην πραγματικότητα σπάσει. Θα ήθελα να το αποκαλούν κάνοντας κάτι σαν DOUBLE_MAX (3, 6). Λοιπόν, τι πρέπει να επιστραφεί; [Φοιτητής] 12. Ναι, 12 θα πρέπει να επιστραφούν, και 12 επιστρέφεται. 3 παίρνει αντικατασταθεί για χ, 6 παίρνει αντικαθίσταται για y, και επιστρέφουμε 2 * 6, η οποία είναι 12. Τώρα τι γίνεται με αυτό; Τι θα πρέπει να επιστραφούν; [Φοιτητής] 14. >> Ιδανικά, 14. Το θέμα είναι ότι το πώς ορίζει την εργασία του κατακερματισμού, να θυμάστε ότι είναι μια κυριολεκτική αντιγραφή και επικόλληση του σχεδόν τα πάντα, έτσι ώστε ό, τι αυτό θα πρέπει να ερμηνευθεί ως 3 είναι μικρότερη από 1 συν 6, 2 φορές 1 συν 6, 2 φορές 3. 

Έτσι, για το λόγο αυτό σχεδόν πάντα τυλίξτε τα πάντα σε παρένθεση. Κάθε μεταβλητή που σχεδόν πάντα τυλίγετε σε παρένθεση. Υπάρχουν περιπτώσεις όπου δεν έχετε να, όπως ξέρω ότι δεν χρειάζεται να το κάνουμε αυτό εδώ επειδή λιγότερο από ό, τι είναι λίγο πολύ πάντα ακριβώς πρόκειται να λειτουργήσει, αν και αυτό δεν θα μπορούσε ακόμη και να είναι αλήθεια. Αν υπάρχει κάτι γελοίο, όπως DOUBLE_MAX (1 == 2), τότε που πρόκειται να πάρει αντικατασταθεί με 3 λιγότερο από 1 ισούται ισούται με 2, και έτσι στη συνέχεια πρόκειται να κάνετε 3 λιγότερο από 1, ότι η ισότητα δεν 2, το οποίο δεν είναι αυτό που θέλουμε. Έτσι, προκειμένου να αποτραπούν τυχόν προβλήματα χειριστή προτεραιότητα, πάντα τυλίγετε σε παρένθεση. Εντάξει. Και αυτό είναι όλο, 5:30. Αν έχετε οποιεσδήποτε ερωτήσεις σχετικά με τη PSET, ενημερώστε μας. Θα πρέπει να είναι διασκέδαση, και η έκδοση χάκερ είναι επίσης πολύ πιο ρεαλιστική από την έκδοση του χάκερ του περασμένου έτους, έτσι ελπίζουμε ότι πολλοί από εσάς να το δοκιμάσετε. Πέρυσι ήταν πολύ εντυπωσιακή. 

[CS50.TV]