1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Παίζει μουσική] 3 00:00:10,800 --> 00:00:13,500 DAVID MALAN: Εντάξει. 4 00:00:13,500 --> 00:00:14,670 Εντάξει, να καλωσορίσω πίσω. 5 00:00:14,670 --> 00:00:18,120 Έτσι, αυτή είναι η Εβδομάδα 4, η αρχή Εκτιμώντας ήδη. 6 00:00:18,120 --> 00:00:21,320 Και θα θυμάστε ότι την περασμένη εβδομάδα, βάζουμε κωδικοποιεί μέρος μόνο για λίγο 7 00:00:21,320 --> 00:00:24,240 και αρχίσαμε να μιλάμε λίγο περισσότερο υψηλού επιπέδου, για τα πράγματα όπως 8 00:00:24,240 --> 00:00:28,130 αναζήτηση και την ταξινόμηση, η οποία όμως κάπως απλές ιδέες, είναι 9 00:00:28,130 --> 00:00:31,840 αντιπροσωπευτικό μιας κατηγορίας προβλημάτων θα αρχίσετε να λύσει ιδιαίτερα 10 00:00:31,840 --> 00:00:34,820 όπως μπορείτε να αρχίσετε να σκέφτεστε για τις τελικές έργα και ενδιαφέρουσες λύσεις που 11 00:00:34,820 --> 00:00:36,760 ίσως χρειαστεί να προβλήματα του πραγματικού κόσμου. 12 00:00:36,760 --> 00:00:39,490 Τώρα είδος φούσκα ήταν ένα από τα απλούστερα τέτοιων αλγορίθμων, και 13 00:00:39,490 --> 00:00:42,900 εργάστηκε από την κατοχή αυτών των μικρών αριθμών σε μια λίστα ή σε είδος σειρά 14 00:00:42,900 --> 00:00:46,530 φούσκα δρόμο τους μέχρι την κορυφή, και η μεγάλους αριθμούς κινηθεί το δρόμο τους προς τα κάτω για να 15 00:00:46,530 --> 00:00:47,930 το τέλος του εν λόγω καταλόγου. 16 00:00:47,930 --> 00:00:50,650 >> Και υπενθυμίζουν ότι θα μπορούσαμε να απεικονίσει Ταξινόμηση φούσκα λίγο 17 00:00:50,650 --> 00:00:52,310 κάτι σαν αυτό. 18 00:00:52,310 --> 00:00:53,640 Επιτρέψτε μου λοιπόν να προχωρήσει και κάντε κλικ στο Έναρξη. 19 00:00:53,640 --> 00:00:55,350 Έχω προεπιλεγεί είδος φούσκα. 20 00:00:55,350 --> 00:00:58,920 Και αν θυμηθούμε ότι το ψηλότερο μπλε γραμμές αντιπροσωπεύουν μεγάλους αριθμούς, μικρές 21 00:00:58,920 --> 00:01:03,300 μπλε γραμμές αντιπροσωπεύουν μικρούς αριθμούς, όπως πάμε μέσα από αυτό ξανά και ξανά και 22 00:01:03,300 --> 00:01:07,680 πάλι, συγκρίνοντας δύο ράβδους δίπλα σε κάθε άλλα σε κόκκινο, θα πάμε να ανταλλάξουν το 23 00:01:07,680 --> 00:01:11,010 μεγαλύτερο και το μικρότερο, αν είναι εκτός λειτουργίας. 24 00:01:11,010 --> 00:01:14,150 >> Έτσι, αυτό θα συνεχιστεί και πάει και πάει σχετικά με, και θα δείτε ότι το μεγαλύτερο 25 00:01:14,150 --> 00:01:16,700 στοιχεία που κάνουν το δρόμο τους προς το δεξιά, και τα μικρότερα στοιχεία 26 00:01:16,700 --> 00:01:17,900 καθιστώντας το δρόμο τους προς τα αριστερά. 27 00:01:17,900 --> 00:01:21,380 Αλλά αρχίσαμε να ποσοτικοποιηθούν η απόδοση, η 28 00:01:21,380 --> 00:01:22,970 ποιότητα αυτού του αλγορίθμου. 29 00:01:22,970 --> 00:01:25,200 Και είπαμε ότι στη χειρότερη περίπτωση, ο αλγόριθμος αυτός πήρε 30 00:01:25,200 --> 00:01:27,940 περίπου πόσα βήματα; 31 00:01:27,940 --> 00:01:28,980 >> Έτσι, n τετράγωνο. 32 00:01:28,980 --> 00:01:30,402 Και ποια ήταν n; 33 00:01:30,402 --> 00:01:31,650 >> ΚΟΙΝΟ: Αριθμός στοιχείων. 34 00:01:31,650 --> 00:01:32,790 >> DAVID MALAN: Έτσι n ήταν η αριθμό στοιχείων. 35 00:01:32,790 --> 00:01:33,730 Και έτσι θα κάνουμε αυτό συχνά. 36 00:01:33,730 --> 00:01:36,650 Κάθε φορά που θέλουμε να μιλήσουμε για το μέγεθος ενός προβλήματος ή το μέγεθος της 37 00:01:36,650 --> 00:01:39,140 εισόδου, ή το ποσό του χρόνου που χρειάζεται για την παραγωγή προϊόντος, απλά θα 38 00:01:39,140 --> 00:01:41,610 γενικευμένη ό, τι η είσοδος είναι το κ. 39 00:01:41,610 --> 00:01:45,970 Έτσι, πίσω στην Εβδομάδα 0, ο αριθμός σελίδων στον τηλεφωνικό κατάλογο ήταν n. 40 00:01:45,970 --> 00:01:47,550 Ο αριθμός των φοιτητών στην αίθουσα ήταν Ν. 41 00:01:47,550 --> 00:01:49,630 Έτσι κι εδώ, είμαστε μετά αυτό το μοτίβο. 42 00:01:49,630 --> 00:01:52,800 >> Τώρα n τετράγωνο δεν είναι ιδιαίτερα γρήγορα, έτσι προσπαθήσαμε να κάνουμε κάτι καλύτερο. 43 00:01:52,800 --> 00:01:55,970 Και γι 'αυτό κοίταξε σε μια-δυο άλλους αλγορίθμους, μεταξύ των οποίων 44 00:01:55,970 --> 00:01:57,690 ήταν είδος επιλογής. 45 00:01:57,690 --> 00:01:59,180 Έτσι, το είδος επιλογής ήταν λίγο διαφορετική. 46 00:01:59,180 --> 00:02:03,130 Ήταν σχεδόν απλούστερο, τολμώ να πω, σύμφωνα με την οποία άρχισα κατά την έναρξη της 47 00:02:03,130 --> 00:02:06,740 κατάλογο των εθελοντών μας και εγώ μόλις και πάλι και ξανά και ξανά πέρασε 48 00:02:06,740 --> 00:02:10,060 ο κατάλογος, το μάδημα το μικρότερο στοιχείο σε μια στιγμή και τη θέση του ή 49 00:02:10,060 --> 00:02:13,040 της στην αρχή της λίστας. 50 00:02:13,040 --> 00:02:16,410 >> Αλλά αυτό, επίσης, από τη στιγμή που άρχισαν να σκέφτονται μέσα από τα μαθηματικά και μεγαλύτερες 51 00:02:16,410 --> 00:02:19,860 εικόνα, σκεφτεί πόσες φορές Πήγαινα πίσω και εμπρός και πίσω 52 00:02:19,860 --> 00:02:24,090 και πίσω, είπαμε, στη χειρότερη περίπτωση, Ταξινόμηση επιλογής, επίσης, ήταν αυτό; 53 00:02:24,090 --> 00:02:24,960 n τετράγωνο. 54 00:02:24,960 --> 00:02:27,490 Τώρα, στον πραγματικό κόσμο, θα μπορούσε στην πραγματικότητα να είναι οριακά πιο γρήγορα. 55 00:02:27,490 --> 00:02:30,620 Επειδή και πάλι, δεν είχα να κρατήσει οπισθοχωρούν όταν είχα την ταξινόμηση 56 00:02:30,620 --> 00:02:31,880 μικρότερα στοιχεία. 57 00:02:31,880 --> 00:02:35,090 Αλλά αν το σκεφτούμε πολύ μεγάλο n, και αν το είδος του κάνουν από τα μαθηματικά ως 58 00:02:35,090 --> 00:02:39,170 Το έκανα στο διοικητικό συμβούλιο, με το n τετράγωνο μείον κάτι, ό, τι άλλο 59 00:02:39,170 --> 00:02:41,850 εκτός από το n τετράγωνο, αφού n παίρνει πραγματικά μεγάλη, δεν 60 00:02:41,850 --> 00:02:42,850 πραγματικά έχει σημασία τόσο πολύ. 61 00:02:42,850 --> 00:02:45,470 Έτσι, οι επιστήμονες ηλεκτρονικών υπολογιστών, ταξινομούμε της εθελοτυφλούμε στο μικρότερο 62 00:02:45,470 --> 00:02:49,220 παράγοντες και να επικεντρωθεί μόνο στο παράγοντας μια έκφραση που πρόκειται να κάνει 63 00:02:49,220 --> 00:02:50,330 η μεγαλύτερη διαφορά. 64 00:02:50,330 --> 00:02:52,840 >> Λοιπόν, τέλος, ψάξαμε σε είδος εισαγωγής. 65 00:02:52,840 --> 00:02:56,620 Και αυτό ήταν παρόμοια ως προς το πνεύμα, αλλά αντί να περνούν επαναληπτικό και 66 00:02:56,620 --> 00:03:01,250 επιλέξτε το μικρότερο στοιχείο σε μια χρόνο, πήρα αντί το χέρι που 67 00:03:01,250 --> 00:03:04,070 εξετάστηκε, και αποφάσισα, όλα δεξιά, ανήκετε εδώ. 68 00:03:04,070 --> 00:03:06,160 Τότε μετακόμισε στο επόμενο στοιχείο και αποφάσισε ότι αυτός ή 69 00:03:06,160 --> 00:03:07,470 ανήκε εδώ. 70 00:03:07,470 --> 00:03:08,810 Και τότε θα μετακινηθεί και επάνω. 71 00:03:08,810 --> 00:03:11,780 Και θα μπορούσα να, κατά μήκος του τρόπου, μετατόπιση αυτά τα παιδιά, προκειμένου να 72 00:03:11,780 --> 00:03:13,030 να δημιουργηθεί χώρος για αυτούς. 73 00:03:13,030 --> 00:03:16,880 Έτσι, αυτό ήταν το είδος της ψυχικής αντιστροφή της επιλογής του είδους που 74 00:03:16,880 --> 00:03:18,630 ονομάζεται ταξινόμηση με εισαγωγή. 75 00:03:18,630 --> 00:03:20,810 >> Έτσι, τα θέματα αυτά να συμβούν στον πραγματικό κόσμο. 76 00:03:20,810 --> 00:03:23,640 Μόλις λίγα χρόνια πριν, όταν ένα ορισμένο γερουσιαστής έτρεχε για τον Πρόεδρο, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt, κατά τη στιγμή ο διευθύνων σύμβουλος της Google, είχε πράγματι τη δυνατότητα 78 00:03:27,160 --> 00:03:28,040 να του πάρει συνέντευξη. 79 00:03:28,040 --> 00:03:32,010 Και σκεφτήκαμε να μοιραστούμε αυτό το YouTube κλιπ για σας εδώ, αν θα μπορούσαμε να γυρίσουμε up 80 00:03:32,010 --> 00:03:32,950 ο όγκος. 81 00:03:32,950 --> 00:03:39,360 >> [PLAYBACK VIDEO] 82 00:03:39,360 --> 00:03:44,620 >> -Τώρα, γερουσιαστής, είσαι εδώ στο Google, και μου αρέσει να σκέφτομαι την προεδρία 83 00:03:44,620 --> 00:03:46,042 όπως μια συνέντευξη για δουλειά. 84 00:03:46,042 --> 00:03:47,770 >> [Γέλια] 85 00:03:47,770 --> 00:03:50,800 >> -Τώρα είναι δύσκολο να πάρει μια δουλειά ως πρόεδρος. 86 00:03:50,800 --> 00:03:52,480 Και θα πάμε μέσα τις ακαμψίες τώρα. 87 00:03:52,480 --> 00:03:54,330 Είναι επίσης δύσκολο να βρουν μια θέση εργασίας στη Google. 88 00:03:54,330 --> 00:03:59,610 Έχουμε τις ερωτήσεις και ζητούμε υποψήφιοι ερωτήσεις μας. 89 00:03:59,610 --> 00:04:02,250 Και αυτό είναι από Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Γέλια] 91 00:04:05,325 --> 00:04:06,400 -Εσείς νομίζετε ότι αστειεύομαι; 92 00:04:06,400 --> 00:04:08,750 Είναι ακριβώς εδώ. 93 00:04:08,750 --> 00:04:12,110 Ποιος είναι ο πιο αποτελεσματικός τρόπος για να ταξινομήσετε ένα εκατομμύριο δύο-bit ακεραίων; 94 00:04:12,110 --> 00:04:15,810 >> [Γέλια] 95 00:04:15,810 --> 00:04:18,260 >> -Λοιπόν, εεε - 96 00:04:18,260 --> 00:04:19,029 >> -Συγγνώμη. 97 00:04:19,029 --> 00:04:19,745 Ίσως θα έπρεπε - 98 00:04:19,745 --> 00:04:21,000 >> -Όχι, όχι, όχι, όχι, όχι. 99 00:04:21,000 --> 00:04:21,470 >> -Αυτό δεν είναι ένα - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Νομίζω ότι το είδος των φυσαλίδων θα να είναι ο λάθος τρόπος να πάει. 102 00:04:25,328 --> 00:04:26,792 >> [Γέλια] 103 00:04:26,792 --> 00:04:28,510 >> [Επευφημίες και χειροκροτήματα] 104 00:04:28,510 --> 00:04:31,211 >> -Έλα, ο οποίος είπε αυτό; 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [PLAYBACK VIDEO END] 107 00:04:33,350 --> 00:04:35,070 >> DAVID MALAN: Έτσι εκεί το έχετε. 108 00:04:35,070 --> 00:04:39,600 Έτσι αρχίσαμε να ποσοτικοποιηθούν αυτές τρέξιμο φορές, να το πω έτσι, με κάτι 109 00:04:39,600 --> 00:04:43,480 ονομάζεται ασυμπτωτική σημειογραφία, το οποίο είναι αναφέρομαι μόνο στο είδος μας της στροφής 110 00:04:43,480 --> 00:04:47,420 τα στραβά μάτια σε αυτές τις μικρότερες διαστάσεις και μόνο κοιτάζοντας το χρόνο λειτουργίας, 111 00:04:47,420 --> 00:04:51,250 η απόδοση αυτών των αλγορίθμων, καθώς το n παίρνει πραγματικά μεγάλη την πάροδο του χρόνου. 112 00:04:51,250 --> 00:04:55,110 Και γι 'αυτό παρουσιάζει μεγάλο O. Και η μεγάλη O αντιπροσώπευε κάτι που νομίζαμε 113 00:04:55,110 --> 00:04:57,000 της ως άνω όριο. 114 00:04:57,000 --> 00:04:59,570 Και στην πραγματικότητα, Barry, μπορούμε να μειώσουμε από το μικρόφωνο λίγο; 115 00:04:59,570 --> 00:05:01,040 >> Έχουμε σκεφτεί αυτό είναι ένα άνω όριο. 116 00:05:01,040 --> 00:05:04,710 Τόσο μεγάλος O Ν τετράγωνο σημαίνει ότι στην η χειρότερη περίπτωση, κάτι σαν 117 00:05:04,710 --> 00:05:07,780 Ταξινόμηση επιλογής θα λάβει n τετράγωνο βήματα. 118 00:05:07,780 --> 00:05:10,310 Ή κάτι σαν είδος εισαγωγής θα n τετράγωνο βήματα. 119 00:05:10,310 --> 00:05:15,150 Τώρα για κάτι σαν εισαγωγή Ταξινόμηση, ποια ήταν η χειρότερη περίπτωση; 120 00:05:15,150 --> 00:05:18,200 Λαμβάνοντας υπόψη μια σειρά, ποιο είναι το χειρότερο δυνατό σενάριο που μπορείτε να βρείτε 121 00:05:18,200 --> 00:05:20,650 τον εαυτό σας αντιμετωπίζουν; 122 00:05:20,650 --> 00:05:21,860 >> Είναι εντελώς προς τα πίσω, έτσι δεν είναι; 123 00:05:21,860 --> 00:05:24,530 Διότι αν είναι τελείως προς τα πίσω, που έχετε να κάνετε ένα σωρό δουλειά. 124 00:05:24,530 --> 00:05:26,420 Διότι, αν είστε εντελώς προς τα πίσω, θα πάμε να βρει το 125 00:05:26,420 --> 00:05:28,840 μεγαλύτερο στοιχείο εδώ, ακόμη και αν ανήκει εκεί κάτω. 126 00:05:28,840 --> 00:05:31,140 Έτσι θα πάμε να πούμε, εντάξει, σε αυτή τη στιγμή, θα ανήκουν εδώ, 127 00:05:31,140 --> 00:05:32,310 έτσι ώστε να το αφήσετε μόνο του. 128 00:05:32,310 --> 00:05:35,425 >> Τότε θα συνειδητοποιήσει, ω, γαμώτο, έχω να μετακινήσετε αυτό το ελαφρώς μικρότερο στοιχείο για 129 00:05:35,425 --> 00:05:36,470 η αριστερά σας. 130 00:05:36,470 --> 00:05:38,770 Τότε θα πρέπει να το κάνουμε αυτό και πάλι και ξανά και ξανά. 131 00:05:38,770 --> 00:05:41,410 Και αν μπήκα μπροστά και πίσω, που θα είδος αισθάνονται την απόδοση του 132 00:05:41,410 --> 00:05:45,540 ότι ο αλγόριθμος, γιατί είμαι συνεχώς ανακάτεμα όλοι οι άλλοι κάτω στην 133 00:05:45,540 --> 00:05:46,510 συστοιχία για να δημιουργηθεί χώρος για αυτό. 134 00:05:46,510 --> 00:05:47,750 Έτσι, αυτή είναι η χειρότερη περίπτωση. 135 00:05:47,750 --> 00:05:48,570 >> Αντίθετα - 136 00:05:48,570 --> 00:05:50,320 και αυτό ήταν μια δραματική στιγμή την τελευταία φορά - 137 00:05:50,320 --> 00:05:54,065 είπαμε ότι η ταξινόμηση με εισαγωγή ήταν ένα ωμέγα τι; 138 00:05:54,065 --> 00:05:57,530 Ποια είναι η καλύτερη περίπτωση λειτουργίας στιγμή της εισαγωγής του είδους; 139 00:05:57,530 --> 00:05:58,520 Έτσι είναι στην πραγματικότητα n. 140 00:05:58,520 --> 00:06:00,980 Αυτό ήταν το κενό που αφήσαμε στο διοικητικό συμβούλιο την τελευταία φορά. 141 00:06:00,980 --> 00:06:03,160 >> Και είναι ωμέγα n γιατί γιατί; 142 00:06:03,160 --> 00:06:06,630 Λοιπόν, στην καλύτερη περίπτωση, τι είναι ταξινόμηση με εισαγωγή πρόκειται να παραδοθεί; 143 00:06:06,630 --> 00:06:09,830 Λοιπόν, μια λίστα που είναι εντελώς ταξινόμηση ήδη, ελάχιστη δουλειά να κάνουμε. 144 00:06:09,830 --> 00:06:12,460 Αλλά τι είναι τακτοποιημένο για το είδος εισαγωγής είναι ότι επειδή ξεκινά εδώ και 145 00:06:12,460 --> 00:06:15,340 αποφασίζει, oh, είστε ο αριθμός ένα, ανήκετε εδώ. 146 00:06:15,340 --> 00:06:16,970 Ω, τι μια καλή τύχη. 147 00:06:16,970 --> 00:06:17,740 >> Είσαι το νούμερο δύο. 148 00:06:17,740 --> 00:06:19,030 Μπορείτε, επίσης, ανήκουν εδώ. 149 00:06:19,030 --> 00:06:21,010 Νούμερο τρία, ακόμα καλύτερα, ανήκετε εδώ. 150 00:06:21,010 --> 00:06:25,210 Μόλις φτάσει στο τέλος της pseudocode λίστα, ανά είδος εισαγωγής του 151 00:06:25,210 --> 00:06:28,010 ότι περπατούσαμε μέσα προφορικά τελευταία φορά, το κάνει. 152 00:06:28,010 --> 00:06:32,790 Αλλά το είδος επιλογής, αντίθετα, συνεχίσαμε να κάνουμε τι; 153 00:06:32,790 --> 00:06:35,260 >> Συνεχίζαμε στη λίστα ξανά και ξανά και ξανά. 154 00:06:35,260 --> 00:06:39,160 Επειδή το βασικό διορατικότητα υπήρχε μόνο Αφού κοίταξε όλη τη διαδρομή προς το 155 00:06:39,160 --> 00:06:42,500 τέλος της λίστας μπορείτε να είστε σίγουροι ότι το στοιχείο που επιλέξατε ήταν 156 00:06:42,500 --> 00:06:45,560 πράγματι η στιγμή μικρότερο στοιχείο. 157 00:06:45,560 --> 00:06:48,920 Έτσι, αυτά τα διαφορετικά ψυχική end μοντέλα up δώσουν κάποια πολύ του πραγματικού κόσμου 158 00:06:48,920 --> 00:06:53,130 διαφορές για εμάς, καθώς αυτά τα θεωρητική ασυμπτωτική διαφορές. 159 00:06:53,130 --> 00:06:56,910 >> Έτσι απλά για να ανακεφαλαιώσουμε, λοιπόν, μεγάλη O Ν τετράγωνο, έχουμε δει μερικά τέτοια 160 00:06:56,910 --> 00:06:58,350 αλγόριθμοι μέχρι στιγμής. 161 00:06:58,350 --> 00:06:59,580 Big O Ν; 162 00:06:59,580 --> 00:07:02,870 Τι είναι ένας αλγόριθμος που θα μπορούσε να πούμε ότι είναι μεγάλη O Ν; 163 00:07:02,870 --> 00:07:06,930 Στη χειρότερη περίπτωση, χρειάζεται μια γραμμική σειρά από βήματα. 164 00:07:06,930 --> 00:07:07,810 >> OK, γραμμική αναζήτηση. 165 00:07:07,810 --> 00:07:10,470 Και στη χειρότερη περίπτωση, όπου είναι η στοιχείο που ψάχνουν για το πότε 166 00:07:10,470 --> 00:07:12,950 εφαρμογής της γραμμικής αναζήτησης; 167 00:07:12,950 --> 00:07:14,680 >> OK, στη χειρότερη περίπτωση, δεν είναι καν εκεί. 168 00:07:14,680 --> 00:07:17,000 Ή στη δεύτερη χειρότερη περίπτωση, είναι όλο το δρόμο στο τέλος, το οποίο είναι 169 00:07:17,000 --> 00:07:18,880 συν ή πλην ενός σταδίου διαφορά. 170 00:07:18,880 --> 00:07:21,180 Έτσι, στο τέλος της ημέρας, μπορούμε να πούμε ότι είναι γραμμική. 171 00:07:21,180 --> 00:07:23,910 Big O Ν θα είναι γραμμική αναζήτηση, γιατί στη χειρότερη περίπτωση, η 172 00:07:23,910 --> 00:07:26,610 στοιχείο που δεν είναι ακόμα εκεί ή είναι όλο το δρόμο στο τέλος. 173 00:07:26,610 --> 00:07:29,370 >> Λοιπόν, μεγάλη O της καταγραφής των n. 174 00:07:29,370 --> 00:07:32,760 Εμείς δεν μιλάμε με μεγάλη λεπτομέρεια σχετικά με αυτό, αλλά έχουμε δει αυτό πριν. 175 00:07:32,760 --> 00:07:36,840 Τι τρέχει στο λεγόμενο λογαριθμική χρόνο, στη χειρότερη περίπτωση; 176 00:07:36,840 --> 00:07:38,500 >> Ναι, έτσι δυαδική αναζήτηση. 177 00:07:38,500 --> 00:07:42,930 Και δυαδική αναζήτηση στη χειρότερη περίπτωση θα μπορούσε να έχει το στοιχείο κάπου στο 178 00:07:42,930 --> 00:07:45,640 η μέση, ή κάπου στο εσωτερικό της συστοιχίας. 179 00:07:45,640 --> 00:07:48,040 Αλλά μπορείτε να βρείτε μόνο τη στιγμή που θα διαιρεί τον κατάλογο στο μισό, σε 180 00:07:48,040 --> 00:07:48,940 μισό, στο μισό, στο μισό. 181 00:07:48,940 --> 00:07:50,200 Και τότε ιδού, είναι εκεί. 182 00:07:50,200 --> 00:07:52,500 Ή πάλι, στη χειρότερη περίπτωση, δεν είναι καν εκεί. 183 00:07:52,500 --> 00:07:56,770 Αλλά δεν ξέρετε ότι δεν υπάρχει μέχρι να φτάσει το είδος της που διαρκούν 184 00:07:56,770 --> 00:08:00,470 κάτω τα περισσότερα στοιχεία από την μείωση κατά το ήμισυ και η μείωση κατά το ήμισυ και η μείωση κατά το ήμισυ. 185 00:08:00,470 --> 00:08:01,400 >> Big O 1. 186 00:08:01,400 --> 00:08:03,540 Έτσι, θα μπορούσαμε μεγάλη O 2, μεγάλη O 3. 187 00:08:03,540 --> 00:08:06,260 Οποτεδήποτε θέλετε απλά ένα σταθερό αριθμό, έχουμε ακριβώς το είδος του απλά απλοποίηση 188 00:08:06,260 --> 00:08:07,280 ότι τόσο μεγάλη O 1. 189 00:08:07,280 --> 00:08:10,440 Ακόμα κι αν ρεαλιστικά, παίρνει 2 ή ακόμα και 100 μέτρα, αν είναι ένα 190 00:08:10,440 --> 00:08:13,680 σταθερό αριθμό βημάτων, απλά λέμε μεγάλα O 1. 191 00:08:13,680 --> 00:08:15,930 Τι είναι ένας αλγόριθμος που είναι σε μεγάλες O 1; 192 00:08:15,930 --> 00:08:18,350 >> ΚΟΙΝΟ: Η εύρεση του μήκους μιας μεταβλητής. 193 00:08:18,350 --> 00:08:21,090 >> DAVID MALAN: Ψάχνοντας το μήκος μιας μεταβλητής; 194 00:08:21,090 --> 00:08:23,870 >> ΚΟΙΝΟ: Όχι, το μήκος αν είναι ήδη ταξινομημένα. 195 00:08:23,870 --> 00:08:24,160 >> DAVID MALAN: Good. 196 00:08:24,160 --> 00:08:27,850 Εντάξει, βρίσκοντας έτσι το μήκος του κάτι Εάν το μήκος αυτού του κάτι, όπως 197 00:08:27,850 --> 00:08:30,020 ένας πίνακας, αποθηκεύεται σε κάποια μεταβλητή. 198 00:08:30,020 --> 00:08:33,380 Επειδή μπορείτε να διαβάσετε ακριβώς την μεταβλητή, ή να εκτυπώσετε τη μεταβλητή, ή 199 00:08:33,380 --> 00:08:34,960 απλά μεταβείτε γενικά τη μεταβλητή. 200 00:08:34,960 --> 00:08:37,299 Και voila, που παίρνει σταθερό χρόνο. 201 00:08:37,299 --> 00:08:38,909 >> Αντίθετα, σκεφτείτε ότι πίσω σε μηδέν. 202 00:08:38,909 --> 00:08:42,460 Σκεφτείτε πίσω στην πρώτη εβδομάδα του C, καλώντας απλά printf και εκτύπωση 203 00:08:42,460 --> 00:08:46,240 κάτι στην οθόνη είναι αναμφισβήτητα σταθερό χρόνο, επειδή παίρνει μόνο 204 00:08:46,240 --> 00:08:50,880 κάποιο αριθμό κύκλων CPU για να δείξει ότι το κείμενο στην οθόνη. 205 00:08:50,880 --> 00:08:52,720 Ή περιμένετε - έτσι δεν είναι; 206 00:08:52,720 --> 00:08:56,430 Πώς αλλιώς θα μπορούσαμε να το μοντέλο του απόδοση της printf; 207 00:08:56,430 --> 00:09:00,420 Θα μπορούσε κάποιος ήθελε να διαφωνήσει, ότι ίσως δεν είναι πραγματικά σταθερό χρόνο; 208 00:09:00,420 --> 00:09:03,600 Με ποια λογική μπορεί να printf τρέχει χρόνο, εκτύπωση πραγματικά μια χορδή στο 209 00:09:03,600 --> 00:09:05,580 η οθόνη, είναι κάτι πλην σταθερή. 210 00:09:05,580 --> 00:09:07,860 >> ΚΟΙΝΟ: [δεν ακούγεται]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID MALAN: Ναι. 212 00:09:08,230 --> 00:09:09,300 Γι 'αυτό εξαρτάται από την προοπτική μας. 213 00:09:09,300 --> 00:09:13,390 Αν θέλουμε πραγματικά να σκεφτούμε με τη συμβολή printf ως το string, και 214 00:09:13,390 --> 00:09:16,380 Συνεπώς μετράμε το μέγεθος του εν λόγω εισόδου από το μήκος του - οπότε ας την ονομάσουμε 215 00:09:16,380 --> 00:09:17,780 ότι το μήκος n, καθώς και - 216 00:09:17,780 --> 00:09:21,990 αναμφισβήτητα, printf είναι το ίδιο μεγάλη O Ν επειδή πρόκειται να σας πάρει n βήματα 217 00:09:21,990 --> 00:09:24,750 να εκτυπώσετε κάθε ένα από αυτά τα Ν χαρακτήρες, το πιο πιθανό. 218 00:09:24,750 --> 00:09:27,730 Τουλάχιστον στο βαθμό που υποθέτουμε ότι ίσως χρησιμοποιώντας ένα for loop 219 00:09:27,730 --> 00:09:28,560 κάτω από το καπό. 220 00:09:28,560 --> 00:09:30,860 >> Αλλά θα πρέπει να δούμε ότι κώδικα για να καταλάβετε καλύτερα. 221 00:09:30,860 --> 00:09:33,650 Και πράγματι, μόλις αρχίσετε εσείς αναλύοντας τις δικές τους αλγορίθμους σας, θα 222 00:09:33,650 --> 00:09:34,900 κυριολεκτικά να κάνουν ακριβώς αυτό. 223 00:09:34,900 --> 00:09:37,765 Ταξινόμηση του βολβού του ματιού κωδικό σας και σκεφτείτε περίπου - Εντάξει, έχω αυτό το βρόχο 224 00:09:37,765 --> 00:09:41,870 εδώ ή έχω ένθετα βρόχους εδώ, ότι πρόκειται να κάνουμε πράγματα n n φορές, 225 00:09:41,870 --> 00:09:46,050 και μπορείτε να ταξινομήσετε του λόγου το δρόμο σας μέσω του κωδικού, ακόμα κι αν είναι 226 00:09:46,050 --> 00:09:47,980 ψευδοκώδικα και όχι πραγματικό κώδικα. 227 00:09:47,980 --> 00:09:49,730 >> Έτσι τι γίνεται με ωμέγα n τετράγωνο; 228 00:09:49,730 --> 00:09:53,582 Τι ήταν ένας αλγόριθμος που στην καλύτερη περίπτωση, ακόμα πήρε n τετράγωνο βήματα; 229 00:09:53,582 --> 00:09:54,014 Ναι; 230 00:09:54,014 --> 00:09:54,880 >> ΚΟΙΝΟ: [δεν ακούγεται]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID MALAN: Μέχρι είδος επιλογής. 232 00:09:55,900 --> 00:09:59,150 Επειδή σε αυτό το πρόβλημα να μειωθούν πραγματικά το γεγονός ότι και πάλι, δεν ξέρω 233 00:09:59,150 --> 00:10:02,600 Έχω βρεθεί την τρέχουσα μικρότερο μέχρι Έχω ελέγξει όλες τις καταριέται στοιχεία. 234 00:10:02,600 --> 00:10:08,050 Έτσι, ωμέγα, ας πούμε, n, μόλις ήρθε με ένα. 235 00:10:08,050 --> 00:10:09,300 Ταξινόμηση με εισαγωγή. 236 00:10:09,300 --> 00:10:12,370 Εάν η λίστα συμβαίνει να διευθετηθεί ήδη, στην καλύτερη περίπτωση απλά πρέπει 237 00:10:12,370 --> 00:10:15,090 να κάνει ένα πέρασμα μέσα από αυτό, σημείο στο οποίο είμαστε σίγουροι. 238 00:10:15,090 --> 00:10:17,890 Και τότε αυτό θα μπορούσε να ειπωθεί να είναι γραμμική, αυτό είναι σίγουρο. 239 00:10:17,890 --> 00:10:20,570 >> Τι γίνεται με ωμέγα 1; 240 00:10:20,570 --> 00:10:23,790 Ποια είναι, στην καλύτερη περίπτωση, θα μπορούσε να λάβει ένα σταθερό αριθμό βημάτων; 241 00:10:23,790 --> 00:10:27,220 Έτσι γραμμική αναζήτηση, αν μπορείτε απλά να πάρετε τυχεροί και το στοιχείο που ψάχνετε 242 00:10:27,220 --> 00:10:31,000 είναι ακριβώς στην αρχή της λίστας, αν αυτό είναι που ξεκινάτε σας 243 00:10:31,000 --> 00:10:33,070 γραμμική διάσχιση του εν λόγω καταλόγου. 244 00:10:33,070 --> 00:10:35,180 >> Και αυτό ισχύει για ένα σειρά από πράγματα. 245 00:10:35,180 --> 00:10:37,660 Για παράδειγμα, ακόμη δυαδικό αναζήτησης είναι ωμέγα 1. 246 00:10:37,660 --> 00:10:40,310 Γιατί ό, τι αν έχετε πραγματικά καταριέται τυχεροί και σκαμπίλι-χωματίδα στη μέση της 247 00:10:40,310 --> 00:10:42,950 σειρά σας είναι ο αριθμός ψάχνετε; 248 00:10:42,950 --> 00:10:45,730 Έτσι, μπορείτε να πάρετε τυχεροί εκεί, καθώς και. 249 00:10:45,730 --> 00:10:49,190 >> Αυτό και μόνο, τέλος, ωμέγα n log n. 250 00:10:49,190 --> 00:10:52,573 Έτσι, n log n, δεν το κάναμε πραγματικά μιλάμε για ακόμα, αλλά - 251 00:10:52,573 --> 00:10:53,300 >> ΚΟΙΝΟ: Συγχώνευση είδους; 252 00:10:53,300 --> 00:10:53,960 >> DAVID MALAN: Συγχώνευση είδους. 253 00:10:53,960 --> 00:10:56,920 Αυτή ήταν η δραματική στιγμή του περασμένου χρόνου, όπου προτείναμε, και δείξαμε 254 00:10:56,920 --> 00:10:58,600 οπτικώς, ότι υπάρχουν αλγόριθμοι. 255 00:10:58,600 --> 00:11:02,470 Και να συγχωνεύσει το είδος ακριβώς ένα τέτοιο αλγόριθμο που είναι ουσιαστικά πιο γρήγορα 256 00:11:02,470 --> 00:11:03,450 από ό, τι μερικά από αυτά τα άλλα παιδιά. 257 00:11:03,450 --> 00:11:07,800 Στην πραγματικότητα, συγχώνευση βραχυκύκλωμα όχι μόνο στην καλύτερη περίπτωση n n log, στη χειρότερη 258 00:11:07,800 --> 00:11:09,460 περίπτωση n n log. 259 00:11:09,460 --> 00:11:14,540 Και όταν έχεις αυτή σύμπτωση Omega και η μεγάλη O είναι το ίδιο πράγμα; 260 00:11:14,540 --> 00:11:17,310 Μπορούμε να περιγράψουμε ότι στην πραγματικότητα και τι είναι ονομάζεται θήτα, αν και είναι μια 261 00:11:17,310 --> 00:11:18,220 λίγο λιγότερο συχνές. 262 00:11:18,220 --> 00:11:21,730 Αλλά αυτό σημαίνει ότι μόνο τα δύο όρια, στην περίπτωση αυτή, είναι τα ίδια. 263 00:11:21,730 --> 00:11:25,770 >> Έτσι συγχώνευση ταξινόμησης, τι αυτό πραγματικά βράζει κάτω για να για μας; 264 00:11:25,770 --> 00:11:27,000 Λοιπόν, υπενθυμίζουν το κίνητρο. 265 00:11:27,000 --> 00:11:30,340 Επιτρέψτε μου να σηκώσει μια άλλη κίνηση που δεν είχαμε να δούμε την τελευταία φορά. 266 00:11:30,340 --> 00:11:33,390 Αυτό και μόνο, ίδια ιδέα, αλλά είναι λίγο μεγαλύτερο. 267 00:11:33,390 --> 00:11:36,160 Και Πάω να πάει μπροστά και να επισημάνω Πρώτα - έχουμε το είδος εισαγωγής στη 268 00:11:36,160 --> 00:11:39,410 στην επάνω αριστερή γωνία, τότε το είδος επιλογής, Ταξινόμηση φούσκα, ένα ζευγάρι των άλλων ειδών - 269 00:11:39,410 --> 00:11:42,670 κέλυφος και γρήγορη - ότι δεν έχουμε μιλήσει περίπου, και σωρού και η συγχώνευση ταξινόμησης. 270 00:11:42,670 --> 00:11:47,090 >> Έτσι, τουλάχιστον να προσπαθήσουμε να εστιάσει τα μάτια σας οι τρεις πρώτες στην αριστερή και στη συνέχεια 271 00:11:47,090 --> 00:11:49,120 συγχώνευση είδους, όταν κάνω κλικ Αυτό το πράσινο βέλος. 272 00:11:49,120 --> 00:11:51,900 Αλλά θα αφήσουμε όλοι τους τρέχουν, απλά για να σας δώσει μια αίσθηση της ποικιλίας των 273 00:11:51,900 --> 00:11:53,980 αλγόριθμους που υπάρχουν στον κόσμο. 274 00:11:53,980 --> 00:11:56,180 Πάω να αφήσουμε αυτή την επιχείρηση για λίγα δευτερόλεπτα. 275 00:11:56,180 --> 00:11:59,640 Και αν μπορείτε να εστιάσετε τα μάτια σας - να πάρει μια αλγόριθμο, να επικεντρωθούν σε αυτό για μόλις 276 00:11:59,640 --> 00:12:02,970 δευτερόλεπτα - θα αρχίσετε να βλέπετε την μοτίβο που είναι εφαρμογή. 277 00:12:02,970 --> 00:12:04,530 >> Συγχώνευση του είδους, ανακοίνωση, γίνεται. 278 00:12:04,530 --> 00:12:06,430 Ταξινόμηση Heap, γρήγορη ταξινόμηση, κέλυφος - 279 00:12:06,430 --> 00:12:09,480 έτσι φαίνεται να παρουσιάζει τα τρία χειρότερες αλγόριθμοι την περασμένη εβδομάδα. 280 00:12:09,480 --> 00:12:12,960 Αλλά αυτό είναι καλό που είμαστε εδώ σήμερα για να εξετάσουμε το είδος συγχώνευσης, η οποία είναι μία από τις 281 00:12:12,960 --> 00:12:16,500 οι ευκολότερες, είναι να δούμε, ακόμα και αν και κατά πάσα πιθανότητα θα λυγίσει το μυαλό σας 282 00:12:16,500 --> 00:12:17,490 λίγο. 283 00:12:17,490 --> 00:12:21,130 Εδώ μπορούμε να δούμε πόσο Ταξινόμηση επιλογής χάλια. 284 00:12:21,130 --> 00:12:24,600 >> Αλλά από την άλλη πλευρά, είναι πολύ εύκολο να εφαρμοστούν. 285 00:12:24,600 --> 00:12:28,160 Και ίσως για Set P 3, αυτό είναι ένα από τα αλγόριθμοι που επέλεξαν να εφαρμόσουν τη 286 00:12:28,160 --> 00:12:28,960 για τη βασική έκδοση. 287 00:12:28,960 --> 00:12:30,970 Απόλυτα υγιής, απολύτως σωστό. 288 00:12:30,970 --> 00:12:35,210 >> Αλλά και πάλι, καθώς το n παίρνει μεγάλες, αν επιλέξουν να εφαρμόσουν ένα πιο γρήγορο αλγόριθμο 289 00:12:35,210 --> 00:12:39,020 όπως συγχώνευση ταξινόμησης, οι πιθανότητες είναι μεγαλύτερες και μεγαλύτερες εισροές, ο κώδικας είναι απλά 290 00:12:39,020 --> 00:12:39,800 πρόκειται να τρέξει πιο γρήγορα. 291 00:12:39,800 --> 00:12:41,090 Η ιστοσελίδα σας πρόκειται να λειτουργήσει καλύτερα. 292 00:12:41,090 --> 00:12:42,650 Οι χρήστες σας πρόκειται να είναι πιο ευτυχισμένοι. 293 00:12:42,650 --> 00:12:45,280 Και έτσι υπάρχουν αυτά τα αποτελέσματα του δίνουν στην πραγματικότητα 294 00:12:45,280 --> 00:12:47,350 μας κάποια βαθύτερη σκέψη. 295 00:12:47,350 --> 00:12:49,990 >> Έτσι, ας ρίξουμε μια ματιά στο τι συγχώνευση sort είναι πραγματικά όλα τα σχετικά. 296 00:12:49,990 --> 00:12:52,992 Το δροσερό πράγμα είναι ότι η συγχώνευση ταξινόμησης είναι μόνο αυτό. 297 00:12:52,992 --> 00:12:56,300 Αυτό είναι, και πάλι, αυτό που έχουμε ονομάσει ψευδοκώδικα, ψευδοκώδικα ον 298 00:12:56,300 --> 00:12:57,720 Αγγλικά-όπως σύνταξη. 299 00:12:57,720 --> 00:12:59,890 Και η απλότητα είναι είδος συναρπαστικό. 300 00:12:59,890 --> 00:13:02,840 >> Έτσι, στην είσοδο των n στοιχείων - έτσι ώστε να απλά σημαίνει, εδώ είναι μια σειρά. 301 00:13:02,840 --> 00:13:04,000 Είναι πήρε n πράγματα σε αυτό. 302 00:13:04,000 --> 00:13:05,370 Αυτό είναι το μόνο που λέμε εκεί. 303 00:13:05,370 --> 00:13:07,560 >> Εάν n είναι μικρότερη από 2, επιστρέφει. 304 00:13:07,560 --> 00:13:08,640 Έτσι, αυτό είναι μόνο η οριακή περίπτωση. 305 00:13:08,640 --> 00:13:12,580 Εάν n είναι μικρότερη από 2, τότε προφανώς είναι 1 ή 0, στην οποία περίπτωση το πράγμα 306 00:13:12,580 --> 00:13:14,780 είναι ήδη ταξινομημένο ή ανύπαρκτη, έτσι απλά να επιστρέψει. 307 00:13:14,780 --> 00:13:15,900 Δεν υπάρχει τίποτα να κάνουμε. 308 00:13:15,900 --> 00:13:18,360 Έτσι, αυτό είναι μια απλή υπόθεση να κόβω μακριά. 309 00:13:18,360 --> 00:13:20,110 >> Αλλιώς, έχουμε τρία βήματα. 310 00:13:20,110 --> 00:13:23,650 Ταξινομήσετε το αριστερό μισό των στοιχείων, το είδος το δεξί μισό των στοιχείων, 311 00:13:23,650 --> 00:13:26,650 και να συγχωνεύσει στη συνέχεια τα ταξινομημένα μισά. 312 00:13:26,650 --> 00:13:29,400 Αυτό που είναι ενδιαφέρον εδώ είναι ότι Είμαι το είδος του στοιχήματος, έτσι δεν είναι; 313 00:13:29,400 --> 00:13:32,300 Υπάρχει το είδος της ένα κυκλικό ορισμό σε αυτού του αλγορίθμου. 314 00:13:32,300 --> 00:13:35,986 Με ποια έννοια είναι αυτή του αλγορίθμου ορισμό εγκύκλιο; 315 00:13:35,986 --> 00:13:37,850 >> ΚΟΙΝΟ: [δεν ακούγεται]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID MALAN: Ναι, ο αλγόριθμος διαλογή μου, δύο βήματα είναι "είδος 317 00:13:41,670 --> 00:13:44,640 κάτι. "Και έτσι που θέτει η ερώτημα, λοιπόν, τι θα πάω να χρησιμοποιήσει 318 00:13:44,640 --> 00:13:46,460 για να ταξινομήσετε το αριστερό μισό και το δεξί μισό; 319 00:13:46,460 --> 00:13:49,600 Και η ομορφιά εδώ είναι ότι ακόμη και αν και πάλι, αυτό είναι το μυαλό κάμψης 320 00:13:49,600 --> 00:13:54,030 μέρος δυνητικά, μπορείτε να χρησιμοποιήσετε το ίδιο αλγόριθμο για να ταξινομήσετε το αριστερό μισό. 321 00:13:54,030 --> 00:13:54,700 >> Αλλά περιμένετε ένα λεπτό. 322 00:13:54,700 --> 00:13:57,070 Όταν λένε να ταξινομήσετε αριστερό μισό, ποιες είναι οι δύο 323 00:13:57,070 --> 00:13:58,240 μέτρα πρόκειται να είναι το επόμενο βήμα; 324 00:13:58,240 --> 00:14:00,550 Θα λύσει το αριστερό μισό του αριστερό ήμισυ και το δικαίωμα 325 00:14:00,550 --> 00:14:01,420 το ήμισυ της αριστερό μισό. 326 00:14:01,420 --> 00:14:04,430 Γαμώτο, πώς μπορώ να ταξινομήσω τις δύο αυτές μισά ή τέταρτα, τώρα; 327 00:14:04,430 --> 00:14:05,260 >> Αλλά αυτό είναι εντάξει. 328 00:14:05,260 --> 00:14:07,830 Έχουμε μια διαλογή αλγόριθμο εδώ. 329 00:14:07,830 --> 00:14:10,660 Και ακόμα κι αν μπορείτε να ανησυχείτε για πρώτη φορά αυτό είναι το είδος ενός άπειρου 330 00:14:10,660 --> 00:14:12,780 βρόχου, είναι ένας κύκλος που ποτέ δεν είναι πρόκειται να τελειώσει - πρόκειται να 331 00:14:12,780 --> 00:14:15,770 τέλος μια φορά τι συμβαίνει; 332 00:14:15,770 --> 00:14:16,970 Μόλις η είναι μικρότερη από 2. 333 00:14:16,970 --> 00:14:19,180 Ποια είναι τελικά πρόκειται να συμβεί, γιατί αν κρατήσει μείωση κατά το ήμισυ και 334 00:14:19,180 --> 00:14:23,020 μείωση κατά το ήμισυ στη μείωση κατά το ήμισυ τα μισά, σίγουρα τελικά θα πάμε στο τέλος 335 00:14:23,020 --> 00:14:25,350 με μόνο 1 ή 0 στοιχεία. 336 00:14:25,350 --> 00:14:28,500 Σε ποιο σημείο, ο αλγόριθμος αυτός λέει τελειώσατε. 337 00:14:28,500 --> 00:14:31,020 >> Έτσι, η πραγματική μαγεία σε αυτό αλγόριθμος φαίνεται να είναι σε 338 00:14:31,020 --> 00:14:33,470 ότι το τελικό στάδιο, συγχώνευση. 339 00:14:33,470 --> 00:14:37,190 Αυτή η απλή ιδέα απλά τη συγχώνευση δύο τα πράγματα, αυτό είναι που τελικά θα 340 00:14:37,190 --> 00:14:40,920 για να μας επιτρέψει να λύσουμε μια σειρά από, ας πούμε, οκτώ στοιχεία. 341 00:14:40,920 --> 00:14:44,410 Έτσι έχω οκτώ μπάλες άγχος μέχρι εδώ, οκτώ κομμάτια χαρτί, και ένα 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 την οποία έχω να κρατήσει. 344 00:14:46,140 --> 00:14:46,960 >> [Γέλια] 345 00:14:46,960 --> 00:14:48,970 >> DAVID MALAN: Αν θα μπορούσαμε να πάρουμε οκτώ εθελοντές, και ας δούμε αν μπορούμε να 346 00:14:48,970 --> 00:14:51,430 παίξετε αυτό έξω, έτσι. 347 00:14:51,430 --> 00:14:52,500 Πω πω, εντάξει. 348 00:14:52,500 --> 00:14:53,565 Η επιστήμη υπολογιστών είναι να πάρει τη διασκέδαση. 349 00:14:53,565 --> 00:14:54,320 Εντάξει. 350 00:14:54,320 --> 00:14:57,770 Πώς, λοιπόν, για εσάς τους τρεις, μεγαλύτερο χέρι μέχρι εκεί. 351 00:14:57,770 --> 00:14:58,580 Τέσσερις στο πίσω μέρος. 352 00:14:58,580 --> 00:15:02,220 Και σχετικά με το πώς θα κάνετε τρεις σε αυτή τη σειρά; 353 00:15:02,220 --> 00:15:03,390 Και τέσσερα στο μέτωπο. 354 00:15:03,390 --> 00:15:04,920 Έτσι, μπορείτε οκτώ, έλα πάνω. 355 00:15:04,920 --> 00:15:12,060 >> [Γέλια] 356 00:15:12,060 --> 00:15:13,450 >> DAVID MALAN: Είμαι πραγματικά δεν είναι σίγουρος τι είναι. 357 00:15:13,450 --> 00:15:14,810 Είναι οι μπάλες άγχος; 358 00:15:14,810 --> 00:15:16,510 Οι λάμπες γραφείου; 359 00:15:16,510 --> 00:15:18,650 Το υλικό; 360 00:15:18,650 --> 00:15:19,680 Το διαδίκτυο; 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Έτσι, έλα επάνω. 363 00:15:21,310 --> 00:15:22,310 Ποιος θα ήθελε - 364 00:15:22,310 --> 00:15:23,570 εφεύρουν. 365 00:15:23,570 --> 00:15:24,240 Ας δούμε. 366 00:15:24,240 --> 00:15:26,460 Και αυτό σας βάζει στην θέση - 367 00:15:26,460 --> 00:15:27,940 είστε σε θέση ένα. 368 00:15:27,940 --> 00:15:28,670 Ωχ, περιμένετε ένα λεπτό. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - Α, ωραία. 370 00:15:30,760 --> 00:15:31,310 Εντάξει, είμαστε καλά. 371 00:15:31,310 --> 00:15:35,130 Εντάξει, έτσι ώστε όλοι να έχουν ένα κάθισμα, αλλά όχι για το γυαλί Google. 372 00:15:35,130 --> 00:15:36,475 Επιτρέψτε μου να περιμένω στην ουρά αυτά τα επάνω. 373 00:15:36,475 --> 00:15:37,115 Ποιο είναι το όνομά σου; 374 00:15:37,115 --> 00:15:37,440 >> MICHELLE: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID MALAN: Michelle; 376 00:15:38,090 --> 00:15:42,000 Εντάξει, μπορείτε να πάρετε για να μοιάσει ο Έλληνας, αν αυτό είναι εντάξει. 377 00:15:42,000 --> 00:15:44,625 Λοιπόν, να κάνω εγώ, υποθέτω, για μια στιγμή. 378 00:15:44,625 --> 00:15:45,875 Εντάξει, σε κατάσταση αναμονής. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Έχουμε προσπαθήσει να καταλήξει σε μια περίπτωση χρήσης για το Google Glass, και 381 00:15:50,950 --> 00:15:53,750 σκέφτηκα ότι θα ήταν διασκεδαστικό απλά για να κάνουμε αυτό, όταν οι άνθρωποι είναι στη σκηνή. 382 00:15:53,750 --> 00:15:57,120 Εμείς θα καταγράψει τον κόσμο από την πλευρά τους. 383 00:15:57,120 --> 00:15:58,410 Εντάξει. 384 00:15:58,410 --> 00:15:59,830 Δεν είναι ίσως ό, τι Google προορίζεται. 385 00:15:59,830 --> 00:16:02,260 Εντάξει, αν δεν σας πειράζει φορώντας Αυτό για τα επόμενα αδέξιο λεπτά, 386 00:16:02,260 --> 00:16:03,150 Αυτό θα ήταν υπέροχο. 387 00:16:03,150 --> 00:16:08,620 >> Εντάξει, έτσι έχουμε εδώ μια σειρά από στοιχεία, και ότι η διάταξη, σύμφωνα με την 388 00:16:08,620 --> 00:16:11,480 κομμάτια χαρτιού σε αυτά τα παιδιά » τα χέρια, αυτή τη στιγμή χωρίς διαλογή. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Ω, αυτό είναι τόσο περίεργο. 390 00:16:12,050 --> 00:16:12,810 >> DAVID MALAN: Είναι λίγο πολύ τυχαία. 391 00:16:12,810 --> 00:16:15,760 Και ακριβώς σε μια στιγμή, θα πάμε να προσπαθήσουμε για την εφαρμογή της συγχώνευσης είδος κοινού 392 00:16:15,760 --> 00:16:17,950 και να δείτε όπου η βασική αντίληψη είναι. 393 00:16:17,950 --> 00:16:21,970 Και το κόλπο εδώ με το είδος συγχώνευσης είναι κάτι που δεν έχουν αναλάβει ακόμα. 394 00:16:21,970 --> 00:16:24,030 Χρειαζόμαστε πραγματικά κάποια επιπλέον χώρο. 395 00:16:24,030 --> 00:16:26,650 Έτσι τι πρόκειται να είναι ιδιαίτερα ενδιαφέρον σχετικά με αυτό είναι ότι αυτά 396 00:16:26,650 --> 00:16:29,270 παιδιά πρόκειται να κινηθεί γύρω από ένα μικρό bit, επειδή είμαι πρόκειται να υποθέσουμε ότι 397 00:16:29,270 --> 00:16:31,880 υπάρχει μια επιπλέον σειρά του χώρου, ας πούμε, ακριβώς πίσω τους. 398 00:16:31,880 --> 00:16:34,570 >> Έτσι, αν είστε πίσω από την καρέκλα τους, Αυτή είναι η δευτερεύουσα συστοιχία. 399 00:16:34,570 --> 00:16:36,960 Αν είσαι καθισμένος εδώ, αυτό είναι η κύρια συστοιχία. 400 00:16:36,960 --> 00:16:40,170 Αλλά αυτό είναι ένας πόρος που έχουμε Δεν μόχλευση μέχρι στιγμής με φούσκα 401 00:16:40,170 --> 00:16:42,040 ταξινόμησης, με το είδος επιλογής, με την ταξινόμηση με εισαγωγή. 402 00:16:42,040 --> 00:16:44,600 Θυμηθείτε την περασμένη εβδομάδα, όλοι μόνο είδος ανακατεύονται στη θέση του. 403 00:16:44,600 --> 00:16:46,840 Δεν χρησιμοποιήσετε οποιαδήποτε πρόσθετη μνήμη. 404 00:16:46,840 --> 00:16:49,310 Κάναμε δωμάτιο για άτομα με μετακίνηση ανθρώπων γύρω. 405 00:16:49,310 --> 00:16:50,580 >> Έτσι, αυτό είναι μια βασική αντίληψη, πάρα πολύ. 406 00:16:50,580 --> 00:16:53,410 Υπάρχει αυτό το εμπόριο-off, εν γένει επιστήμη των υπολογιστών, των πόρων. 407 00:16:53,410 --> 00:16:55,800 Αν θέλετε να επιταχύνει κάτι όπως το χρόνο, θα πάμε να 408 00:16:55,800 --> 00:16:56,900 πρέπει να πληρώσει ένα τίμημα. 409 00:16:56,900 --> 00:17:00,750 Και μία από αυτές τις τιμές είναι πολύ συχνά διαστήματος, η ποσότητα της μνήμης ή σκληρό 410 00:17:00,750 --> 00:17:01,700 χώρου στο δίσκο που χρησιμοποιείτε. 411 00:17:01,700 --> 00:17:03,640 Ή, ειλικρινά, το ποσό του χρόνου προγραμματιστή. 412 00:17:03,640 --> 00:17:06,700 Πόσο χρόνο σας παίρνει, το ανθρώπινο, να εφαρμόσουν στην πράξη λίγο περισσότερο 413 00:17:06,700 --> 00:17:07,829 περίπλοκο αλγόριθμο. 414 00:17:07,829 --> 00:17:09,760 Αλλά για σήμερα, το εμπόριο-off είναι ο χρόνος και χώρος. 415 00:17:09,760 --> 00:17:11,930 >> Έτσι, αν εσείς θα μπορούσε απλά να κρατήσει ψηλά σας αριθμών, ώστε να μπορούμε να δούμε ότι είστε 416 00:17:11,930 --> 00:17:15,839 πράγματι ταιριάζουν 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Εξαιρετικό. 418 00:17:16,599 --> 00:17:19,520 Έτσι, Πάω να προσπαθήσουμε να ενορχηστρώσει τα πράγματα, αν εσείς μπορείτε απλά να 419 00:17:19,520 --> 00:17:21,800 ακολουθήσουν το παράδειγμά μου εδώ. 420 00:17:21,800 --> 00:17:26,650 >> Είμαι, λοιπόν, πρόκειται για την εφαρμογή, κατ 'αρχάς, η πρώτο βήμα της ψευδοκώδικα, η οποία είναι 421 00:17:26,650 --> 00:17:29,440 στην είσοδο των n στοιχείων, αν το n είναι λιγότερο από 2, στη συνέχεια επιστρέφουν. 422 00:17:29,440 --> 00:17:31,370 Προφανώς, αυτό δεν εφαρμόζονται, έτσι ώστε να προχωρήσουμε. 423 00:17:31,370 --> 00:17:33,340 Έτσι ταξινομήσετε το αριστερό μισό των στοιχείων. 424 00:17:33,340 --> 00:17:36,220 Έτσι, αυτό σημαίνει ότι Πάω να επικεντρωθεί μου προσοχή για μια στιγμή σε αυτά 425 00:17:36,220 --> 00:17:37,310 τέσσερις άντρες εδώ. 426 00:17:37,310 --> 00:17:39,774 Εντάξει, τι μπορώ να κάνω το επόμενο; 427 00:17:39,774 --> 00:17:40,570 >> ΚΟΙΝΟ: Ταξινομήστε το αριστερό μισό. 428 00:17:40,570 --> 00:17:42,780 >> DAVID MALAN: Μέχρι τώρα έχω να ταξινομήσετε το αριστερό μισό από αυτά τα παιδιά. 429 00:17:42,780 --> 00:17:45,580 Επειδή και πάλι, ας υποθέσουμε για τον εαυτό του Στόχος είναι να ταξινομήσετε το αριστερό μισό. 430 00:17:45,580 --> 00:17:46,440 Πώς το κάνεις αυτό; 431 00:17:46,440 --> 00:17:49,140 Απλά ακολουθήστε τις οδηγίες, ακόμα και αν το κάνουμε και πάλι. 432 00:17:49,140 --> 00:17:50,160 Έτσι ταξινομήσετε το αριστερό μισό. 433 00:17:50,160 --> 00:17:52,030 Τώρα είμαι διαλογή αυτά τα δύο παιδιά. 434 00:17:52,030 --> 00:17:53,563 Τι θα επακολουθήσει; 435 00:17:53,563 --> 00:17:54,510 >> ΚΟΙΝΟ: Ταξινομήστε το αριστερό μισό. 436 00:17:54,510 --> 00:17:55,460 >> DAVID MALAN: Ταξινομήστε το αριστερό μισό. 437 00:17:55,460 --> 00:18:00,680 Μέχρι τώρα αυτά, αυτή η θέση εδώ, είναι μια λίστα μεγέθους 1. 438 00:18:00,680 --> 00:18:01,365 Και τι είναι το όνομά σας και πάλι; 439 00:18:01,365 --> 00:18:02,390 >> PRINCESS DAISY: Πριγκίπισσα Μαργαρίτα. 440 00:18:02,390 --> 00:18:03,690 >> DAVID MALAN: Princess Daisy είναι εδώ. 441 00:18:03,690 --> 00:18:07,470 Και έτσι αυτή είναι ήδη ταξινομημένα, γιατί η λίστα έχει μέγεθος 1. 442 00:18:07,470 --> 00:18:09,490 Τι μπορώ να κάνω το επόμενο; 443 00:18:09,490 --> 00:18:13,680 OK, επιστροφή, γιατί ο κατάλογος είναι μεγέθους 1, η οποία είναι μικρότερη από 2. 444 00:18:13,680 --> 00:18:14,320 Τότε ποιο είναι το επόμενο βήμα; 445 00:18:14,320 --> 00:18:17,490 Και τώρα θα πρέπει να το είδος της υπαναχωρήσει στο μυαλό σας. 446 00:18:17,490 --> 00:18:19,340 >> Ταξινομήσετε το δεξί μισό, το οποίο είναι - 447 00:18:19,340 --> 00:18:19,570 ποιο είναι το όνομά σου; 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID MALAN: Linda. 450 00:18:20,980 --> 00:18:23,210 Και έτσι αυτό που κάνουμε τώρα που έχουμε μια λίστα με μέγεθος 1; 451 00:18:23,210 --> 00:18:24,440 >> Κοινό: Return. 452 00:18:24,440 --> 00:18:24,760 >> DAVID MALAN: Προσεκτική. 453 00:18:24,760 --> 00:18:29,540 Επιστρέφουμε πρώτη, και τώρα η τρίτη βήμα - και αν το είδος αυτό απεικονίζουν με 454 00:18:29,540 --> 00:18:33,490 αγκαλιάζει τις δύο έδρες που τώρα, τώρα Πρέπει να συγχωνεύσει αυτά τα δύο στοιχεία. 455 00:18:33,490 --> 00:18:35,530 Μέχρι τώρα, δυστυχώς, τα στοιχεία είναι εκτός λειτουργίας. 456 00:18:35,530 --> 00:18:39,920 Αλλά αυτό είναι όπου η διαδικασία συγχώνευσης αρχίζει να παίρνει συναρπαστικό. 457 00:18:39,920 --> 00:18:42,410 >> Έτσι, αν εσείς θα μπορούσε να σταθεί για λίγο μια στιγμή, Πάω να χρειάζεται, σε 458 00:18:42,410 --> 00:18:44,170 στιγμή, στο βήμα πίσω από την καρέκλα σας. 459 00:18:44,170 --> 00:18:46,480 Και αν Linda, γιατί το 2 είναι μικρότερο από 4, γιατί δεν 460 00:18:46,480 --> 00:18:48,130 θα έρθει γύρω από πρώτα; 461 00:18:48,130 --> 00:18:48,690 Μείνε εκεί. 462 00:18:48,690 --> 00:18:50,520 Έτσι, Linda, θα έρθει γύρω από πρώτα. 463 00:18:50,520 --> 00:18:53,820 >> Τώρα, στην πραγματικότητα, αν είναι απλώς μια σειρά θα μπορούσαμε να προχωρήσουμε της ακριβώς σε πραγματικό χρόνο 464 00:18:53,820 --> 00:18:55,360 από αυτήν την καρέκλα σε αυτό το σημείο. 465 00:18:55,360 --> 00:18:57,770 Έτσι, φανταστείτε ότι πήρε κάποια σταθερή αριθμό των βημάτων 1. 466 00:18:57,770 --> 00:18:58,480 Και τώρα - 467 00:18:58,480 --> 00:19:01,490 αλλά πρέπει να σας βάλει σε η πρώτη θέση εδώ. 468 00:19:01,490 --> 00:19:03,930 >> Και τώρα, αν θα μπορούσε να έρθει γύρω, καθώς επίσης, θα πάμε να 469 00:19:03,930 --> 00:19:06,300 είναι σε θέση δύο. 470 00:19:06,300 --> 00:19:09,120 Και ακόμα κι αν αυτό το αισθάνεται σαν να είναι λαμβάνοντας μια στιγμή, τι είναι ωραίο είναι τώρα 471 00:19:09,120 --> 00:19:14,710 ότι το αριστερό μισό του αριστερό μισό είναι τώρα ταξινομημένο. 472 00:19:14,710 --> 00:19:18,010 Λοιπόν, τι ήταν το επόμενο βήμα, αν τώρα rewind περαιτέρω στην ιστορία; 473 00:19:18,010 --> 00:19:18,980 >> ΚΟΙΝΟ: Δεξί μισό. 474 00:19:18,980 --> 00:19:19,900 >> DAVID MALAN: Ταξινομήστε το δεξί μισό. 475 00:19:19,900 --> 00:19:21,320 Έτσι, εσείς έχετε να το κάνετε αυτό, όπως καλά. 476 00:19:21,320 --> 00:19:23,510 Έτσι, αν μπορούσε να σταθεί για μια στιγμή; 477 00:19:23,510 --> 00:19:25,192 Και ποιο είναι το όνομά σου; 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID MALAN: Jess. 480 00:19:25,870 --> 00:19:29,720 ΕΝΤΑΞΕΙ, έτσι Jess είναι τώρα η αριστερά το ήμισυ της δεξί μισό. 481 00:19:29,720 --> 00:19:31,400 Και έτσι αυτή είναι μια λίστα με μέγεθος 1. 482 00:19:31,400 --> 00:19:32,380 Έχει προφανώς ταξινόμηση. 483 00:19:32,380 --> 00:19:33,070 Και το όνομά σας και πάλι; 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID MALAN: Michelle είναι προφανώς μια λίστα με μέγεθος 1. 486 00:19:35,340 --> 00:19:36,050 Έχει ήδη ταξινομημένα. 487 00:19:36,050 --> 00:19:38,690 Έτσι τώρα η μαγεία συμβαίνει, η διαδικασία συγχώνευσης. 488 00:19:38,690 --> 00:19:39,790 Έτσι, ο οποίος πρόκειται να έρθει πρώτος; 489 00:19:39,790 --> 00:19:41,560 Προφανώς Michelle. 490 00:19:41,560 --> 00:19:43,280 Έτσι, αν μπορούσε να έρθει από πίσω. 491 00:19:43,280 --> 00:19:47,090 Ο χώρος που έχουμε στη διάθεσή μας γι 'αυτήν τώρα Είναι ακριβώς πίσω από αυτήν την καρέκλα εδώ. 492 00:19:47,090 --> 00:19:51,580 Και τώρα, αν θα μπορούσε να έρθει πίσω, καθώς, έχουμε τώρα, να είναι σαφής, δύο 493 00:19:51,580 --> 00:19:53,810 μισά, κάθε μεγέθους 2 - 494 00:19:53,810 --> 00:19:57,090 και μόνο για το καλό απεικόνιση του, αν θα μπορούσε να κάνει λίγο χώρο - 495 00:19:57,090 --> 00:19:59,780 ένα άφησε μισό εδώ, ένα δεξιό μισό εδώ. 496 00:19:59,780 --> 00:20:01,160 >> Rewind περαιτέρω στην ιστορία. 497 00:20:01,160 --> 00:20:02,270 Ποια βήμα είναι το επόμενο βήμα; 498 00:20:02,270 --> 00:20:03,030 >> Κοινό: Συγχώνευση. 499 00:20:03,030 --> 00:20:04,160 >> DAVID MALAN: Έτσι τώρα έχουμε να συγχωνευθούν. 500 00:20:04,160 --> 00:20:07,490 Έτσι, OK, έτσι και τώρα, ευτυχώς, μόλις ελευθερωθεί τέσσερις καρέκλες. 501 00:20:07,490 --> 00:20:11,480 Έτσι έχουμε χρησιμοποιήσει διπλάσια μνήμη, αλλά μπορούμε να δώσουμε flip-flopping μεταξύ 502 00:20:11,480 --> 00:20:12,330 οι δύο συστοιχίες. 503 00:20:12,330 --> 00:20:14,190 Έτσι, ο αριθμός των οποίων είναι να έρθει πρώτος; 504 00:20:14,190 --> 00:20:14,850 Έτσι, Michelle, προφανώς. 505 00:20:14,850 --> 00:20:16,680 Έτσι, έρχονται γύρω και να τη θέση σας εδώ. 506 00:20:16,680 --> 00:20:19,120 Και τότε ο αριθμός 2 είναι προφανώς επόμενη, έτσι ώστε να έρθει εδώ. 507 00:20:19,120 --> 00:20:21,520 Number 4, αριθμός 6. 508 00:20:21,520 --> 00:20:23,390 Και πάλι, ακόμα κι αν υπάρχει μια λίγο περπάτημα που εμπλέκονται, 509 00:20:23,390 --> 00:20:26,010 Πραγματικά, αυτές θα μπορούσε να συμβεί αμέσως, μετακινώντας ένα - 510 00:20:26,010 --> 00:20:26,880 Εντάξει, καλά έπαιξε. 511 00:20:26,880 --> 00:20:28,350 >> [Γέλια] 512 00:20:28,350 --> 00:20:29,680 >> DAVID MALAN: Και τώρα είμαστε σε αρκετά καλή κατάσταση. 513 00:20:29,680 --> 00:20:34,910 Το αριστερό ήμισυ του συνόλου εισόδου έχει πλέον ταξινομημένο. 514 00:20:34,910 --> 00:20:37,370 Εντάξει, έτσι ώστε αυτά τα παιδιά είχαν το πλεονέκτημα της μου - 515 00:20:37,370 --> 00:20:40,340 πώς να καταλήγουν όλα τα κορίτσια για την αριστερά και όλα τα αγόρια στα δεξιά; 516 00:20:40,340 --> 00:20:42,450 >> Εντάξει, παιδιά »στραφούμε τώρα. 517 00:20:42,450 --> 00:20:44,680 Γι 'αυτό και δεν θα σας καθοδηγήσει αυτά τα βήματα. 518 00:20:44,680 --> 00:20:46,550 Θα δούμε αν μπορούμε να εφαρμόσετε ξανά το ίδιο ψευδοκώδικα. 519 00:20:46,550 --> 00:20:50,050 Αν θέλετε να προχωρήσετε και να στέκονται όρθιοι, και εσείς, επιτρέψτε μου να σας δώσω το μικρόφωνο. 520 00:20:50,050 --> 00:20:52,990 Δείτε εάν δεν μπορείτε να επαναλάβει ό, τι που μόλις κάναμε εδώ για το 521 00:20:52,990 --> 00:20:53,880 άλλο άκρο της λίστας. 522 00:20:53,880 --> 00:20:59,530 Ποιος πρέπει να μιλήσει πρώτος, με βάση τον αλγόριθμο; 523 00:20:59,530 --> 00:21:03,210 Έτσι εξηγήσει τι κάνετε πριν κάνετε οποιεσδήποτε κινήσεις του ποδιού. 524 00:21:03,210 --> 00:21:05,930 >> ΟΜΙΛΗΤΗΣ 1: Εντάξει, έτσι ώστε από το Είμαι το αριστερό μισό της 525 00:21:05,930 --> 00:21:07,790 αριστερό μισό, επιστρέφω. 526 00:21:07,790 --> 00:21:08,730 Σωστά; 527 00:21:08,730 --> 00:21:09,250 >> DAVID MALAN: Good. 528 00:21:09,250 --> 00:21:10,350 >> ΟΜΙΛΗΤΗΣ 1: Και τότε - 529 00:21:10,350 --> 00:21:11,800 >> DAVID MALAN: Ποιος κάνει το μικρόφωνο πηγαίνετε στο επόμενο βήμα; 530 00:21:11,800 --> 00:21:12,920 >> ΟΜΙΛΗΤΗΣ 1: Επόμενη αριθμό. 531 00:21:12,920 --> 00:21:14,720 >> ΟΜΙΛΗΤΗΣ 2: Έτσι είμαι το δεξί μισό από το αριστερό μισό του 532 00:21:14,720 --> 00:21:17,830 αριστερό μισό, και θα επιστρέψω. 533 00:21:17,830 --> 00:21:18,050 >> DAVID MALAN: Good. 534 00:21:18,050 --> 00:21:18,550 Επιστρέφετε. 535 00:21:18,550 --> 00:21:21,855 Και τώρα τι είναι το επόμενο για εσάς τους δύο; 536 00:21:21,855 --> 00:21:23,740 >> ΟΜΙΛΗΤΗΣ 2: Θέλουμε να δούμε ποιος είναι μικρότερο. 537 00:21:23,740 --> 00:21:24,200 >> DAVID MALAN: Ακριβώς. 538 00:21:24,200 --> 00:21:24,940 Θέλουμε να συγχωνευθούν. 539 00:21:24,940 --> 00:21:27,590 Ο χώρος που πρόκειται να χρησιμοποιήσετε για τη συγχώνευση σας σε, έστω κι αν είναι 540 00:21:27,590 --> 00:21:30,250 προφανώς ταξινομούνται ήδη, θα πάμε να ακολουθούν τον ίδιο αλγόριθμο. 541 00:21:30,250 --> 00:21:31,560 Έτσι, ο οποίος πηγαίνει στην πλάτη πρώτα; 542 00:21:31,560 --> 00:21:35,720 Έτσι, 3, και, στη συνέχεια 7. 543 00:21:35,720 --> 00:21:38,570 Και τώρα το μικρόφωνο πηγαίνει σε αυτά τα παιδιά, εντάξει; 544 00:21:38,570 --> 00:21:43,590 >> ΟΜΙΛΗΤΗΣ 3: Έτσι είμαι το δεξί μισό της αριστερό ήμισυ, και το η μου είναι μικρότερη από ό, τι 545 00:21:43,590 --> 00:21:45,048 1, οπότε είμαι απλώς πρόκειται να περάσει - 546 00:21:45,048 --> 00:21:46,380 >> DAVID MALAN: Good. 547 00:21:46,380 --> 00:21:49,450 >> ΟΜΙΛΗΤΗΣ 4: Είμαι το δεξί μισό της δεξί ήμισυ του δικαιώματος μισό, και είμαι 548 00:21:49,450 --> 00:21:51,740 Επίσης, ένα άτομο, έτσι είμαι πρόκειται να επιστρέψει. 549 00:21:51,740 --> 00:21:52,990 Έτσι τώρα έχουμε τη συγχώνευση. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> ΟΜΙΛΗΤΗΣ 3: Οπότε πάμε πίσω. 552 00:21:56,150 --> 00:21:57,160 >> DAVID MALAN: Έτσι, πηγαίνετε στο πίσω μέρος. 553 00:21:57,160 --> 00:21:59,200 Έτσι, 5 πηγαίνει πρώτα, στη συνέχεια, 8. 554 00:21:59,200 --> 00:22:01,240 Και τώρα το κοινό, το οποίο είναι το βήμα που έχουμε τώρα rewind 555 00:22:01,240 --> 00:22:02,200 πίσω στο μυαλό μας; 556 00:22:02,200 --> 00:22:02,940 >> Κοινό: Συγχώνευση. 557 00:22:02,940 --> 00:22:07,270 >> DAVID MALAN: Συγχώνευση αριστερό μισό και δεξιά το μισό του αρχικού αριστερό μισό. 558 00:22:07,270 --> 00:22:08,840 Έτσι τώρα - 559 00:22:08,840 --> 00:22:10,520 και μόνο για να γίνει αυτό σαφές, κάνει ένα μικρό κομμάτι του χώρου 560 00:22:10,520 --> 00:22:11,690 μεταξύ των δυο σας παιδιά. 561 00:22:11,690 --> 00:22:13,800 Έτσι, τώρα που είναι οι δύο λίστες, αριστερά και δεξιά. 562 00:22:13,800 --> 00:22:18,320 Επομένως, πώς μπορούμε πλέον να συγχωνεύονται σας παιδιά σε η πρώτη σειρά των καθισμάτων και πάλι; 563 00:22:18,320 --> 00:22:19,600 >> 3 πηγαίνει πρώτα. 564 00:22:19,600 --> 00:22:20,850 Στη συνέχεια, 5, προφανώς. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Στη συνέχεια, 7, 8 και τώρα. 567 00:22:27,330 --> 00:22:28,710 Εντάξει, και τώρα είμαστε; 568 00:22:28,710 --> 00:22:29,650 >> ΚΟΙΝΟ: Δεν έχει γίνει. 569 00:22:29,650 --> 00:22:32,440 >> DAVID MALAN: Δεν γίνεται, γιατί Προφανώς, υπάρχει ένα βήμα που απομένει. 570 00:22:32,440 --> 00:22:35,720 Αλλά και πάλι, ο λόγος που είμαι με τη χρήση αυτή φρασεολογία, όπως «rewind στο μυαλό σας," 571 00:22:35,720 --> 00:22:37,160 Είναι επειδή αυτό είναι πραγματικά τι συμβαίνει. 572 00:22:37,160 --> 00:22:39,610 Θα πάμε μέσα από όλα αυτά τα βήματα, αλλά είμαστε είδος σταματώντας για μια 573 00:22:39,610 --> 00:22:42,480 στιγμή, καταδύσεις βαθύτερα στην αλγόριθμο, σταματώντας για μια στιγμή, 574 00:22:42,480 --> 00:22:45,840 καταδύσεις βαθύτερα τον αλγόριθμο, και τώρα πρέπει να ταξινομήσετε του rewind σε μας 575 00:22:45,840 --> 00:22:49,430 μυαλό και θα ανατρέψει όλα αυτά τα στρώματα ότι έχουμε το είδος της τίθεται σε αναμονή. 576 00:22:49,430 --> 00:22:51,790 >> Έτσι τώρα έχουμε δύο λίστες του μεγέθους 4. 577 00:22:51,790 --> 00:22:54,790 Αν εσείς θα μπορούσε να σταθεί για μια τελευταία φορά και να κάνει λίγο χώρο εδώ για να 578 00:22:54,790 --> 00:22:57,230 να καταστήσει σαφές ότι αυτό είναι το αριστερό το μισό του αρχικού, το 579 00:22:57,230 --> 00:22:58,620 δεξί μισό του αρχικού. 580 00:22:58,620 --> 00:23:01,060 Ποιος είναι ο πρώτος αριθμός που πρέπει να τραβήξει στο πίσω μέρος; 581 00:23:01,060 --> 00:23:01,870 Michelle, φυσικά. 582 00:23:01,870 --> 00:23:03,230 >> Έτσι βάλαμε Michelle εδώ. 583 00:23:03,230 --> 00:23:05,080 Και ποιος έχει τον αριθμό 2; 584 00:23:05,080 --> 00:23:06,440 Number 2 έρχεται στην πλάτη, καθώς και. 585 00:23:06,440 --> 00:23:07,800 Αριθμός 3; 586 00:23:07,800 --> 00:23:08,510 Εξαιρετικό. 587 00:23:08,510 --> 00:23:16,570 Number 4, τον αριθμό 5, τον αριθμό 6, αριθμό 7, και τον αριθμό 8. 588 00:23:16,570 --> 00:23:18,850 >> Εντάξει, έτσι ένιωσα σαν μια παρτίδα βημάτων, αυτό είναι σίγουρο. 589 00:23:18,850 --> 00:23:22,390 Αλλά τώρα ας δούμε αν δεν μπορούμε να επιβεβαιώσουμε είδος διαισθητικά ότι αυτό 590 00:23:22,390 --> 00:23:26,190 αλγόριθμος ουσιαστικά, ιδίως όσον n παίρνει πραγματικά μεγάλη, όπως έχουμε δει 591 00:23:26,190 --> 00:23:29,170 με τα κινούμενα σχέδια, είναι ριζικά πιο γρήγορα. 592 00:23:29,170 --> 00:23:33,400 Γι 'αυτό και υποστηρίζουν αυτόν τον αλγόριθμο, στη χειρότερη περίπτωση, ακόμα και στην καλύτερη περίπτωση, 593 00:23:33,400 --> 00:23:36,160 είναι μεγάλη O Ν φορές log n. 594 00:23:36,160 --> 00:23:39,160 Δηλαδή, υπάρχει κάποια πτυχή αυτής της αλγόριθμο που λαμβάνει n βήματα, αλλά 595 00:23:39,160 --> 00:23:43,110 υπάρχει και μια άλλη πτυχή κάπου στο ότι η επανάληψη, η looping, ότι 596 00:23:43,110 --> 00:23:44,410 λαμβάνει log n βήματα. 597 00:23:44,410 --> 00:23:49,154 Μπορούμε να βάλει το δάχτυλό μας για το τι αυτές δύο αριθμούς αναφέρεστε; 598 00:23:49,154 --> 00:23:51,320 Λοιπόν, όπου - 599 00:23:51,320 --> 00:23:54,160 Πώς Ξεκίνησε το μικρόφωνο πάτε; 600 00:23:54,160 --> 00:23:58,660 >> ΟΜΙΛΗΤΗΣ 1: Θα μπορούσε η log n είναι σπάσιμο μας σε δύο - 601 00:23:58,660 --> 00:23:59,630 διαιρώντας με δύο, κατ 'ουσίαν. 602 00:23:59,630 --> 00:24:00,120 >> DAVID MALAN: Ακριβώς. 603 00:24:00,120 --> 00:24:03,000 Κάθε φορά που βλέπουμε σε κάθε αλγόριθμο έτσι τώρα, έχει υπάρξει αυτό το μοτίβο της 604 00:24:03,000 --> 00:24:04,200 διαίρεση, διαίρεση, διαίρεση. 605 00:24:04,200 --> 00:24:05,700 Και είναι συνήθως μειώνεται σε κάτι που είναι 606 00:24:05,700 --> 00:24:07,100 λογαριθμική, ημερολόγιο βάσης 2. 607 00:24:07,100 --> 00:24:10,180 Αλλά θα μπορούσε πραγματικά να είναι οτιδήποτε, αλλά συνδεθείτε βάσης 2. 608 00:24:10,180 --> 00:24:11,330 >> Τώρα τι γίνεται με το n; 609 00:24:11,330 --> 00:24:14,550 Βλέπω ότι έχουμε το είδος της που διαιρείται παιδιά - διαιρείται σας, διαιρείται, 610 00:24:14,550 --> 00:24:15,910 διαιρείται σας, διαιρείται. 611 00:24:15,910 --> 00:24:18,760 Πού το τέλος προέρχονται από; 612 00:24:18,760 --> 00:24:19,810 >> Έτσι είναι η συγχώνευση. 613 00:24:19,810 --> 00:24:20,610 Επειδή το σκέφτομαι. 614 00:24:20,610 --> 00:24:25,420 Όταν συγχωνεύονται οκτώ άτομα μαζί, σύμφωνα με την οποία τα μισά από αυτά είναι ένα σύνολο τεσσάρων 615 00:24:25,420 --> 00:24:27,770 και το άλλο μισό είναι ένα άλλο σύνολο τεσσάρων, πώς θα πάτε 616 00:24:27,770 --> 00:24:28,820 για να κάνει τη συγχώνευση; 617 00:24:28,820 --> 00:24:30,830 Λοιπόν, εσείς το έκανε αρκετά διαισθητικά. 618 00:24:30,830 --> 00:24:34,140 >> Αλλά αν αντί να το έκανε λίγο πιο μεθοδικά, μπορεί να έχω επισημάνει σε 619 00:24:34,140 --> 00:24:38,090 το αριστερό πρόσωπο πρώτα με το αριστερό μου Αντίθετα, τόνισε στο αριστερό πρόσωπο 620 00:24:38,090 --> 00:24:42,080 του εν λόγω μισό με το δεξί μου χέρι, και ακριβώς στη συνέχεια περπάτησαν μέσα από την 621 00:24:42,080 --> 00:24:46,990 λίστα, δείχνοντας το μικρότερο στοιχείο κάθε φορά, κινείται το δάχτυλό μου πάνω και 622 00:24:46,990 --> 00:24:48,970 πάνω, όπως απαιτείται σε όλη τη λίστα. 623 00:24:48,970 --> 00:24:51,890 Αλλά τι είναι το κλειδί για αυτό συγχώνευση διαδικασία είναι Είμαι σύγκριση αυτών των ζευγών 624 00:24:51,890 --> 00:24:53,460 των στοιχείων. 625 00:24:53,460 --> 00:24:57,270 Από το δεξί μισό και από την αριστερή εξάμηνο, είμαι αφού ποτέ δεν οπισθοχωρούν. 626 00:24:57,270 --> 00:25:00,570 >> Έτσι, η ίδια η συγχώνευση λαμβάνει όχι περισσότερο από n βήματα. 627 00:25:00,570 --> 00:25:03,250 Και πόσες φορές έκανε έχω να το κάνουμε αυτό τη συγχώνευση; 628 00:25:03,250 --> 00:25:07,150 Καλά, όχι περισσότερο από n, και εμείς απλά είδε ότι με την συγχώνευση. 629 00:25:07,150 --> 00:25:13,120 Και έτσι, αν κάνεις κάτι που παίρνει log n βήματα n φορές, ή το αντίστροφο, 630 00:25:13,120 --> 00:25:15,210 πρόκειται να μας δώσει n log n φορές. 631 00:25:15,210 --> 00:25:16,310 >> Και γιατί είναι αυτό το καλύτερο; 632 00:25:16,310 --> 00:25:19,600 Λοιπόν, αν γνωρίζουμε ήδη ότι το ημερολόγιο n είναι καλύτερη από n - έτσι δεν είναι; 633 00:25:19,600 --> 00:25:22,590 Είδαμε σε δυαδική αναζήτηση, τον τηλεφωνικό κατάλογο παράδειγμα, log n ήταν σίγουρα 634 00:25:22,590 --> 00:25:23,760 καλύτερη από τη γραμμική. 635 00:25:23,760 --> 00:25:28,420 Έτσι, αυτό σημαίνει ότι n log n φορές είναι σίγουρα καλύτερα από ό, τι n φορές ένα άλλο 636 00:25:28,420 --> 00:25:30,390 n, AKA n τετράγωνο. 637 00:25:30,390 --> 00:25:32,400 Και αυτό είναι που τελικά αισθάνονται. 638 00:25:32,400 --> 00:25:34,928 >> Έτσι, μεγάλο χειροκρότημα, αν θα μπορούσαμε, για αυτά τα παιδιά. 639 00:25:34,928 --> 00:25:38,920 >> [Χειροκρότημα] 640 00:25:38,920 --> 00:25:41,550 >> DAVID MALAN: Και τα δώρα χωρίστρα σας - μπορεί να κρατήσει τους αριθμούς, 641 00:25:41,550 --> 00:25:44,010 εάν θα θέλατε. 642 00:25:44,010 --> 00:25:45,620 Και δώρο χωρίστρα σας, ως συνήθως. 643 00:25:45,620 --> 00:25:47,290 Ω, και εμείς θα σας στείλουμε το υλικό, Michelle. 644 00:25:47,290 --> 00:25:48,343 Σας ευχαριστώ. 645 00:25:48,343 --> 00:25:49,250 Εντάξει. 646 00:25:49,250 --> 00:25:50,400 Βοηθήστε τον εαυτό σας σε μια μπάλα για το άγχος. 647 00:25:50,400 --> 00:25:54,110 >> Και επιτρέψτε μου να σηκώσει, εν τω μεταξύ, φίλος μας Rob Bowden να προσφέρει 648 00:25:54,110 --> 00:25:59,520 κάπως διαφορετική άποψη για το θέμα αυτό, δεδομένου ότι μπορείτε να σκεφτείτε αυτές τις 649 00:25:59,520 --> 00:26:01,280 βήματα που συμβαίνουν σε μια κάπως διαφορετικό τρόπο. 650 00:26:01,280 --> 00:26:04,750 Στην πραγματικότητα, το set-up για το τι Rob είναι περίπου για να μας δείξει υποθέτει ότι έχουμε 651 00:26:04,750 --> 00:26:09,030 έχει ήδη γίνει η διαίρεση της μεγάλη λίστα σε οκτώ μικρούς καταλόγους, 652 00:26:09,030 --> 00:26:10,570 κάθε μεγέθους 1. 653 00:26:10,570 --> 00:26:13,350 >> Έτσι, αλλάζουμε το pseudocode ένα λίγο μόνο για να ταξινομήσετε του πάρει το 654 00:26:13,350 --> 00:26:15,320 βασική ιδέα για το πώς η συγχώνευση έργων. 655 00:26:15,320 --> 00:26:17,600 Αλλά ο χρόνος εκτέλεσης του τι είναι έτοιμος να κάνει είναι ακόμα 656 00:26:17,600 --> 00:26:19,110 πρόκειται να είναι το ίδιο. 657 00:26:19,110 --> 00:26:23,540 Και πάλι, το set-up εδώ είναι ότι αυτός είναι ξεκίνησε με οκτώ καταλόγους του μεγέθους 1. 658 00:26:23,540 --> 00:26:27,730 Έτσι, έχετε χάσει το μέρος όπου αυτός είναι πραγματικά κάνει το log n, n log, log n 659 00:26:27,730 --> 00:26:31,205 διαίρεση της εισόδου. 660 00:26:31,205 --> 00:26:32,120 >> [PLAYBACK VIDEO] 661 00:26:32,120 --> 00:26:33,615 >> -Γι 'αυτό για ένα βήμα. 662 00:26:33,615 --> 00:26:38,270 Για το βήμα δύο, κατ 'επανάληψη συγχώνευση ζεύγη των καταλόγων. 663 00:26:38,270 --> 00:26:39,210 >> DAVID MALAN: Χμ. 664 00:26:39,210 --> 00:26:41,270 Μόνο ήχος έρχεται από τον υπολογιστή μου. 665 00:26:41,270 --> 00:26:42,520 Ας δοκιμάσουμε ξανά. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Απλά επιλέξτε αυθαίρετα η οποία - τώρα έχουμε τέσσερις λίστες. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Μάθετε πριν. 670 00:26:52,120 --> 00:26:53,040 >> DAVID MALAN: Εκεί πάμε. 671 00:26:53,040 --> 00:27:00,510 >> -Συγχώνευση 108 και 15, καταλήγουμε με τον κατάλογο 15, 108. 672 00:27:00,510 --> 00:27:07,170 Συγχωνευόμενες 50 και 4, μπορούμε καταλήξετε με 4, 50. 673 00:27:07,170 --> 00:27:12,990 Συγχώνευση 8 και 42, θα καταλήξετε με 8, 42. 674 00:27:12,990 --> 00:27:19,970 Και τη συγχώνευση 23 και 16 ετών, καταλήγουν με 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Τώρα, όλες τις λίστες μας έχουν μέγεθος 2. 676 00:27:23,270 --> 00:27:26,690 Παρατηρήστε ότι κάθε μία από τις τέσσερις λίστες είναι ταξινομημένο. 677 00:27:26,690 --> 00:27:29,450 Έτσι, μπορούμε να αρχίσουμε τη συγχώνευση ζεύγη των καταλόγων και πάλι. 678 00:27:29,450 --> 00:27:38,420 Συγχωνευόμενες 15 και 108 και 4, και 50, έχουμε πρώτα να πάρετε το 4, τότε το 15, τότε 679 00:27:38,420 --> 00:27:41,500 το 50, τότε το 108. 680 00:27:41,500 --> 00:27:50,610 Συγχώνευση 8, 42 και 16, 23, πρέπει πρώτα να το 8, τότε το 16, τότε το 23, 681 00:27:50,610 --> 00:27:52,700 τότε το 42. 682 00:27:52,700 --> 00:27:57,600 >> Έτσι τώρα έχουμε μόλις δύο λίστες του μεγέθους 4, καθένα από τα οποία είναι ταξινομημένο. 683 00:27:57,600 --> 00:28:01,170 Έτσι τώρα έχουμε ενώσει τις δύο λίστες. 684 00:28:01,170 --> 00:28:11,835 Πρώτον, παίρνουμε το 4, τότε παίρνουμε το 8, τότε θα πάρει το 15, τότε 16, τότε 685 00:28:11,835 --> 00:28:19,456 23, στη συνέχεια 42, και στη συνέχεια 50, τότε 108. 686 00:28:19,456 --> 00:28:19,872 >> [PLAYBACK VIDEO END] 687 00:28:19,872 --> 00:28:23,430 >> DAVID MALAN: Και πάλι, ανακοίνωση, ποτέ δεν άγγιξε μια δεδομένη κύπελλο περισσότερες από μία φορά 688 00:28:23,430 --> 00:28:24,860 μετά προχωρεί πέρα ​​από αυτό. 689 00:28:24,860 --> 00:28:26,200 Έτσι, ο ίδιος ποτέ δεν επαναλαμβάνεται. 690 00:28:26,200 --> 00:28:29,850 Έτσι, αυτός είναι πάντα σε κίνηση προς την πλευρά της, και εκεί είναι που πήραμε n μας. 691 00:28:29,850 --> 00:28:33,290 >> Γιατί να μην επιτρέψτε μου να σηκώσει ένα animation που είδαμε νωρίτερα, αλλά αυτή τη φορά 692 00:28:33,290 --> 00:28:35,110 εστιάζοντας μόνο σε είδος συγχώνευσης. 693 00:28:35,110 --> 00:28:38,030 Επιτρέψτε μου να προχωρήσει και ζουμ σε αυτόν εδώ. 694 00:28:38,030 --> 00:28:42,530 Καταρχάς, επιτρέψτε μου να επιλέξει ένα τυχαίο εισόδου, μεγεθύνει αυτό, και μπορείτε να ταξινομήσετε των δείτε 695 00:28:42,530 --> 00:28:46,600 ό, τι θεωρούσαμε δεδομένο, νωρίτερα, συγχώνευση είδους είναι πραγματικά κάνει. 696 00:28:46,600 --> 00:28:50,330 >> Έτσι παρατηρήσετε ότι μπορείτε να πάρετε αυτά τα μισά ή αυτά τα τέταρτα ή όγδοα αυτά του 697 00:28:50,330 --> 00:28:53,140 πρόβλημα ότι ξαφνικά αρχίζουν να παίρνουν καλή κατάσταση. 698 00:28:53,140 --> 00:28:57,070 Και τελικά, θα δείτε στο το τέλος που μπαμ, 699 00:28:57,070 --> 00:28:58,860 τα πάντα συγχωνεύονται. 700 00:28:58,860 --> 00:29:01,690 >> Έτσι, αυτά είναι μόνο τρία διαφορετικά παίρνει την ίδια ιδέα. 701 00:29:01,690 --> 00:29:05,980 Αλλά η βασική αντίληψη, ακριβώς όπως χάσμα και να κατακτήσει στην πρώτη κατηγορία, 702 00:29:05,980 --> 00:29:10,640 ήταν ότι αποφασίσαμε με κάποιο τρόπο να διαιρέσει το πρόβλημα σε κάτι μεγάλο, σε 703 00:29:10,640 --> 00:29:14,760 κάτι το είδος των ίδιων κατά το πνεύμα, αλλά και μικρότερα και μικρότερα 704 00:29:14,760 --> 00:29:15,660 και μικρότερα. 705 00:29:15,660 --> 00:29:18,420 >> Τώρα, άλλον ένα τρόπο για να ταξινομήσετε του πιστεύουν για αυτά, ακόμα κι αν δεν είναι 706 00:29:18,420 --> 00:29:20,520 πρόκειται να σας δώσω την ίδια διαισθητική κατανόηση, είναι 707 00:29:20,520 --> 00:29:21,640 το ακόλουθο animation. 708 00:29:21,640 --> 00:29:25,400 Έτσι, αυτό είναι ένα κάποιο βίντεο μαζί που σχετίζεται διαφορετικές 709 00:29:25,400 --> 00:29:29,970 ήχους με τις διάφορες λειτουργίες για ταξινόμηση με εισαγωγή, για το είδος συγχώνευσης, και 710 00:29:29,970 --> 00:29:31,150 για ένα ζευγάρι των άλλων. 711 00:29:31,150 --> 00:29:32,330 Έτσι, σε μια στιγμή, Πάω να χτυπήσει Play. 712 00:29:32,330 --> 00:29:33,600 Πρόκειται για ένα λεπτό καιρό. 713 00:29:33,600 --> 00:29:37,410 Και ακόμα κι αν μπορείτε ακόμα να δείτε το μοτίβα συμβαίνει, αυτή τη φορά μπορείτε να 714 00:29:37,410 --> 00:29:41,420 επίσης να ακούσετε πώς αυτοί οι αλγόριθμοι εκτελεί διαφορετικά και με 715 00:29:41,420 --> 00:29:43,950 κάπως διαφορετικά πρότυπα. 716 00:29:43,950 --> 00:29:45,830 >> Αυτό είναι το είδος εισαγωγής. 717 00:29:45,830 --> 00:29:50,400 >> [ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 718 00:29:50,400 --> 00:29:52,400 >> DAVID MALAN: Είναι και πάλι προσπαθεί για να εισάγετε κάθε στοιχείο 719 00:29:52,400 --> 00:29:52,900 στην οποία ανήκει. 720 00:29:52,900 --> 00:29:54,628 Αυτό είναι το είδος φούσκα. 721 00:29:54,628 --> 00:30:10,097 >> [ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 722 00:30:10,097 --> 00:30:13,630 >> DAVID MALAN: Και μπορείτε να ταξινομήσετε του αίσθηση Πώς σχετικά λίγη δουλειά να κάνει 723 00:30:13,630 --> 00:30:15,834 σε κάθε βήμα. 724 00:30:15,834 --> 00:30:20,470 Αυτό είναι ό, τι μονοτονία ακούγεται. 725 00:30:20,470 --> 00:30:21,472 >> [ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 726 00:30:21,472 --> 00:30:25,222 >> DAVID MALAN: Αυτό είναι το είδος επιλογής, όπου επιλέγουμε το στοιχείο που θέλουμε από 727 00:30:25,222 --> 00:30:28,845 περνάει ξανά και ξανά και ξανά και βάζοντας στην αρχή. 728 00:30:28,845 --> 00:30:37,674 >> [ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 729 00:30:37,674 --> 00:30:43,970 >> DAVID MALAN: Αυτό είναι το είδος συγχώνευσης, η οποία μπορείτε πραγματικά να αρχίσετε να αισθάνεστε. 730 00:30:43,970 --> 00:30:51,810 >> [ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 731 00:30:51,810 --> 00:30:54,770 >> [Γέλια] 732 00:30:54,770 --> 00:30:58,395 >> DAVID MALAN: Κάτι που ονομάζεται gnome ταξινόμησης, το οποίο δεν έχουμε κοίταξε. 733 00:30:58,395 --> 00:31:13,630 >> [ΤΟΝΟΙ ΠΑΙΖΟΝΤΑΣ] 734 00:31:13,630 --> 00:31:17,910 >> DAVID MALAN: Επιτρέψτε μου λοιπόν να δούμε, τώρα, αποσπούν την προσοχή, όπως ελπίζουμε είναι από το 735 00:31:17,910 --> 00:31:21,110 μουσική, αν μπορώ να γλιστρήσει λίγο κομμάτι των μαθηματικών εδώ. 736 00:31:21,110 --> 00:31:24,850 Έτσι, υπάρχει ένας τέταρτος τρόπος που μπορούμε σκεφτείτε τι σημαίνει αυτές 737 00:31:24,850 --> 00:31:29,210 λειτουργίες να είναι ταχύτερη από ό, τι αυτοί που έχουμε δει μέχρι σήμερα. 738 00:31:29,210 --> 00:31:32,470 Και αν είστε έρχονται στο γήπεδο από την ένα υπόβαθρο στα μαθηματικά, θα 739 00:31:32,470 --> 00:31:36,030 πραγματικά γνωρίζουν ίσως ήδη ότι θα να χαστούκι έναν όρο για αυτήν την τεχνική - 740 00:31:36,030 --> 00:31:40,400 δηλαδή αναδρομή, μια συνάρτηση που αυτοαποκαλείται με κάποιο τρόπο. 741 00:31:40,400 --> 00:31:44,780 >> Και πάλι, υπενθυμίζουν ότι το είδος συγχώνευσης pseudocode ήταν επαναληπτικό με την έννοια 742 00:31:44,780 --> 00:31:48,460 ότι ένα από τα βήματα της συγχώνευσης είδους ήταν να καλέσει είδος - 743 00:31:48,460 --> 00:31:49,740 δηλαδή, η ίδια. 744 00:31:49,740 --> 00:31:52,480 Αλλά ευτυχώς, γιατί διατηρήσαμε καλώντας το είδος, ή να συγχωνευθούν είδος, 745 00:31:52,480 --> 00:31:55,880 Συγκεκριμένα, για ένα όλο και μικρότερο και μικρότερη λίστα, που τελικά 746 00:31:55,880 --> 00:32:00,005 έφθασε στο απόγειό της χάρη σε αυτό θα καλέσουμε μία βασική περίπτωση, το hard-coded περίπτωση που 747 00:32:00,005 --> 00:32:04,270 είπε πως αν η λίστα είναι μικρή, μικρότερη από 2 Στην περίπτωση αυτή, μόλις επιστρέψει αμέσως. 748 00:32:04,270 --> 00:32:07,550 Αν δεν είχαμε αυτό το ειδική περίπτωση, η αλγόριθμος ποτέ δεν θα ανακάμπτουν, 749 00:32:07,550 --> 00:32:11,010 και πράγματι θα μπει σε μια άπειρο βρόχο πραγματικά για πάντα. 750 00:32:11,010 --> 00:32:14,330 >> Αλλά ας υποθέσουμε ότι θέλαμε να θέσει τώρα ορισμένοι αριθμοί σε αυτό, και πάλι, με τη χρήση Ν 751 00:32:14,330 --> 00:32:15,660 όπως το μέγεθος της εισόδου. 752 00:32:15,660 --> 00:32:18,680 Και ήθελα να σας ρωτήσω, τι είναι ο συνολικός χρόνος που εμπλέκονται στην 753 00:32:18,680 --> 00:32:19,800 τρέχει είδος συγχώνευσης; 754 00:32:19,800 --> 00:32:22,960 Ή, γενικότερα, τι είναι το κόστος του στο χρόνο; 755 00:32:22,960 --> 00:32:24,730 >> Λοιπόν, είναι αρκετά εύκολο να μετρηθεί αυτό. 756 00:32:24,730 --> 00:32:29,010 Εάν n είναι μικρότερη από 2, ο χρόνος που εμπλέκονται στη διαλογή n στοιχεία, 757 00:32:29,010 --> 00:32:30,480 όπου το η είναι 2, το η είναι 0. 758 00:32:30,480 --> 00:32:31,410 Επειδή ακριβώς επιστρέψει. 759 00:32:31,410 --> 00:32:32,510 Δεν υπάρχει δουλειά να γίνει. 760 00:32:32,510 --> 00:32:35,660 Τώρα, αναμφισβήτητα, ίσως είναι ένα βήμα ή δύο βήματα για να υπολογίσει το ποσό των 761 00:32:35,660 --> 00:32:38,420 εργασία, αλλά είναι αρκετά κοντά στο 0 που Είμαι ακριβώς πρόκειται να πω καμιά εργασία δεν 762 00:32:38,420 --> 00:32:40,940 απαιτείται αν ο κατάλογος είναι τόσο μικρή να πληκτικός. 763 00:32:40,940 --> 00:32:42,580 >> Αλλά αυτή η περίπτωση είναι ενδιαφέρουσα. 764 00:32:42,580 --> 00:32:47,320 Η αναδρομική περίπτωση ήταν ο κλάδος της ψευδοκώδικα που είπε άλλο, το είδος 765 00:32:47,320 --> 00:32:52,000 το αριστερό μισό, να ταξινομήσετε το δικαίωμα μισό, να συγχωνεύσει τα δύο μισά. 766 00:32:52,000 --> 00:32:55,530 Τώρα γιατί το κάνει αυτό έκφραση εκπροσωπεί το εν λόγω δαπάνη; 767 00:32:55,530 --> 00:32:58,690 Λοιπόν, Τ n σημαίνει ότι μόνο η χρόνο για να ταξινομήσετε n στοιχεία. 768 00:32:58,690 --> 00:33:03,070 Και στη συνέχεια στη δεξιά πλευρά του ίσον εκεί, το Τ n διαιρείται 769 00:33:03,070 --> 00:33:06,600 κατά 2 αναφέρεται στο κόστος του τι; 770 00:33:06,600 --> 00:33:07,570 Διαλογή το αριστερό μισό. 771 00:33:07,570 --> 00:33:10,990 Το άλλο Τ του n διαιρείται με 2 είναι προφανώς αναφερόμενος στο κόστος 772 00:33:10,990 --> 00:33:12,390 ταξινομήσετε το δεξί μισό. 773 00:33:12,390 --> 00:33:14,590 >> Και τότε ο n plus; 774 00:33:14,590 --> 00:33:15,420 Είναι η συγχώνευση. 775 00:33:15,420 --> 00:33:19,120 Διότι, αν έχετε δύο λίστες, μία από τις n το μέγεθος πάνω από 2 και ενός άλλου μεγέθους n 776 00:33:19,120 --> 00:33:22,580 πάνω από 2, θα πρέπει ουσιαστικά να αγγίξει καθένα από αυτά τα στοιχεία, όπως ακριβώς και Rob 777 00:33:22,580 --> 00:33:24,990 άγγιξε κάθε ένα από τα κύπελλα, και μόλις όπως έχουμε επισημάνει σε κάθε ένα από τα 778 00:33:24,990 --> 00:33:26,310 εθελοντές στη σκηνή. 779 00:33:26,310 --> 00:33:28,790 Έτσι, n είναι το βάρος της συγχώνευσης. 780 00:33:28,790 --> 00:33:31,780 >> Τώρα, δυστυχώς, αυτός ο τύπος Είναι επίσης το ίδιο αναδρομικό. 781 00:33:31,780 --> 00:33:36,390 Έτσι, εάν έθεσε το ερώτημα, αν ο n είναι, ας πούμε, 16, αν υπάρχει 16 άτομα επί σκηνής 782 00:33:36,390 --> 00:33:40,670 ή 16 κύπελλα στο βίντεο, πόσες συνολικά βήματα που χρειάζεται για να τις ταξινομήσετε 783 00:33:40,670 --> 00:33:41,550 με το είδος συγχώνευσης; 784 00:33:41,550 --> 00:33:45,790 Είναι πραγματικά δεν είναι μια προφανής απάντηση, γιατί τώρα θα πρέπει να ταξινομήσετε του 785 00:33:45,790 --> 00:33:48,500 αναδρομικά απαντήσουμε σε αυτό τον τύπο. 786 00:33:48,500 --> 00:33:51,190 >> Αλλά αυτό είναι εντάξει, γιατί επιτρέψτε μου να προτείνω ότι κάνουμε το εξής. 787 00:33:51,190 --> 00:33:56,670 Ο χρόνος που απαιτούνται για να ταξινομήσετε 16 άτομα ή 16 κύπελλα πρόκειται να εκπροσωπηθεί 788 00:33:56,670 --> 00:33:58,020 γενικώς σαν Τ 16. 789 00:33:58,020 --> 00:34:01,400 Αλλά αυτό ισοδυναμεί, σύμφωνα με μας προηγούμενο τύπο, 2 φορές το ποσό 790 00:34:01,400 --> 00:34:04,780 του χρόνου που χρειάζεται για να ταξινομήσετε 8 φλιτζάνια συν 16. 791 00:34:04,780 --> 00:34:08,590 Και πάλι, συν 16 είναι η ώρα για τη συγχώνευση, και οι δύο χρόνους Τ των 8 είναι η 792 00:34:08,590 --> 00:34:10,790 χρόνο για να ταξινομήσετε το αριστερό και το δεξί μισό μισό. 793 00:34:10,790 --> 00:34:11,989 >> Αλλά και πάλι, αυτό δεν είναι αρκετό. 794 00:34:11,989 --> 00:34:13,210 Πρέπει να βουτήξει στα βαθιά. 795 00:34:13,210 --> 00:34:16,409 Αυτό σημαίνει ότι πρέπει να απαντήσει η ερώτημα, ποια είναι η T 8; 796 00:34:16,409 --> 00:34:19,610 Καλά T από 8 απέχει μόλις 2 φορές T 4 συν 8. 797 00:34:19,610 --> 00:34:20,520 Λοιπόν, ποια είναι η T 4; 798 00:34:20,520 --> 00:34:23,780 T 4 είναι μόλις 2 φορές T από 2 συν 4. 799 00:34:23,780 --> 00:34:25,489 Λοιπόν, τι είναι Τ 2; 800 00:34:25,489 --> 00:34:29,030 T 2 είναι μόλις 2 φορές T 1 συν 2. 801 00:34:29,030 --> 00:34:31,940 >> Και πάλι, είμαστε το είδος του να πάρει κολλημένοι σε αυτό τον κύκλο. 802 00:34:31,940 --> 00:34:34,790 Αλλά είναι έτοιμος να χτυπήσει ότι λεγόμενη βασική περίπτωση. 803 00:34:34,790 --> 00:34:37,310 Γιατί ό, τι είναι Τ 1, δεν διεκδικούμε; 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Μέχρι τώρα επιτέλους, μπορούμε να εργαστούμε προς τα πίσω. 806 00:34:39,730 --> 00:34:44,290 >> Αν T 1 είναι 0, μπορώ τώρα να πάει πίσω μέχρι ένα γραμμή σε αυτόν τον άνθρωπο εδώ και μπορώ να 807 00:34:44,290 --> 00:34:46,330 plug in για 0 ​​T 1. 808 00:34:46,330 --> 00:34:51,770 Έτσι, αυτό σημαίνει ότι ισούται με 2 φορές το μηδέν, αλλιώς γνωστή ως μηδέν, συν 2. 809 00:34:51,770 --> 00:34:53,739 Και έτσι ώστε όλη η έκφραση είναι 2. 810 00:34:53,739 --> 00:34:58,740 >> Τώρα, αν θα πάρει το Τ 2, του οποίου η απάντηση είναι 2, συνδέστε το στη μεσαία γραμμή, T 811 00:34:58,740 --> 00:35:02,740 4, αυτό μου δίνει 2 φορές 2 συν 4, έτσι 8. 812 00:35:02,740 --> 00:35:07,080 Αν ήμουν στη συνέχεια, συνδέστε σε 8 με το προηγούμενο γραμμή, αυτό μου δίνει 2 φορές 8, 16. 813 00:35:07,080 --> 00:35:12,470 Και αν συνεχίσουμε τότε ότι με την 24, προσθέτοντας στο 16, θα έχουμε επιτέλους μια 814 00:35:12,470 --> 00:35:13,820 αξία 64. 815 00:35:13,820 --> 00:35:18,480 >> Τώρα που και αυτή η ίδια είδους μιλάει τίποτα στη σημειογραφία n, η 816 00:35:18,480 --> 00:35:20,700 O μεγάλος, τα ωμέγα που έχουμε μιλήσει. 817 00:35:20,700 --> 00:35:24,890 Αλλά αποδεικνύεται ότι το 64 είναι πράγματι 16, το μέγεθος της εισόδου, 818 00:35:24,890 --> 00:35:27,110 συνδεθείτε βάσης 2 από 16. 819 00:35:27,110 --> 00:35:30,200 Και αν αυτό είναι λίγο άγνωστη, απλά σκεφτείτε πίσω, και θα επανέλθω 820 00:35:30,200 --> 00:35:30,700 να σας τελικά. 821 00:35:30,700 --> 00:35:33,775 Αν αυτή είναι η log βάσης 2, είναι σαν 2 έθεσε στο τι σας δίνει 16; 822 00:35:33,775 --> 00:35:36,380 Ω, αυτό είναι 4, οπότε είναι 16 φορές 4. 823 00:35:36,380 --> 00:35:39,380 >> Και πάλι, δεν είναι μια μεγάλη υπόθεση, αν αυτό Είναι το είδος του ένα θολό μνήμης τώρα. 824 00:35:39,380 --> 00:35:43,720 Αλλά για τώρα, να αναλάβει την πίστη ότι το 16 log 16 είναι 64. 825 00:35:43,720 --> 00:35:46,590 Και έτσι, πράγματι, με αυτή την απλή λογική ελέγχει, έχουμε επιβεβαιώσει - 826 00:35:46,590 --> 00:35:48,250 αλλά δεν αποδείχθηκε επισήμως - 827 00:35:48,250 --> 00:35:52,800 ότι ο χρόνος εκτέλεσης της συγχώνευσης ταξινόμησης είναι πράγματι n log n. 828 00:35:52,800 --> 00:35:53,790 >> Έτσι, δεν είναι κακό. 829 00:35:53,790 --> 00:35:57,260 Είναι σίγουρα καλύτερα από ό, τι η αλγόριθμοι που έχουμε δει μέχρι στιγμής, και 830 00:35:57,260 --> 00:36:00,710 αυτό συμβαίνει γιατί έχουμε μόχλευση, ένα, μια τεχνική που ονομάζεται αναδρομή. 831 00:36:00,710 --> 00:36:03,880 Αλλά το πιο ενδιαφέρον από αυτό, ότι έννοια της διαίρεσης και την κατάκτηση. 832 00:36:03,880 --> 00:36:07,460 Και πάλι, πραγματικά εβδομάδα 0 πράγματα που ακόμη και τώρα είναι και πάλι στο ένα 833 00:36:07,460 --> 00:36:08,740 πιο συναρπαστικό τρόπο. 834 00:36:08,740 --> 00:36:11,750 >> Τώρα, ένα διασκεδαστικό λίγο άσκηση, αν έχετε ποτέ δεν κάνει αυτό - και ίσως 835 00:36:11,750 --> 00:36:14,660 δεν θα έχει, επειδή το είδος της κανονικής οι άνθρωποι δεν σκέφτονται να το κάνουν αυτό. 836 00:36:14,660 --> 00:36:20,650 Αλλά αν πάω στο google.com και αν Θέλω να μάθω κάτι για 837 00:36:20,650 --> 00:36:22,356 αναδρομή, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Γέλια] 840 00:36:29,058 --> 00:36:32,030 [Περισσότερο γέλιο] 841 00:36:32,030 --> 00:36:33,385 DAVID MALAN: κακόγουστο αστείο εξαπλώνεται σιγά-σιγά. 842 00:36:33,385 --> 00:36:34,450 [Γέλια] 843 00:36:34,450 --> 00:36:36,970 DAVID MALAN: Ακριβώς σε περίπτωση, είναι εκεί. 844 00:36:36,970 --> 00:36:38,710 Εγώ δεν σημάνει λάθος, και υπάρχει το αστείο. 845 00:36:38,710 --> 00:36:40,810 Εντάξει. 846 00:36:40,810 --> 00:36:42,950 Εξηγήστε στο λαό δίπλα σας, αν δεν έχει αρκετά κλικ ακριβώς ακόμα. 847 00:36:42,950 --> 00:36:47,650 Αλλά αναδρομή, γενικότερα, αναφέρεται με τη μέθοδο της μιας συνάρτησης καλώντας 848 00:36:47,650 --> 00:36:51,430 μόνη της, ή, γενικότερα, τη διαίρεση πρόβλημα σε κάτι που μπορεί να είναι 849 00:36:51,430 --> 00:36:56,220 λυθεί αποσπασματικά με την επίλυση πανομοιότυπα προβλήματα εκπροσώπου. 850 00:36:56,220 --> 00:36:58,400 >> Γρανάζια αλλαγή Λοιπόν, ας για μια στιγμή. 851 00:36:58,400 --> 00:37:00,840 Θα ήθελα να ολοκληρώσω με ορισμένες δραματικές στιγμές, οπότε ας αρχίσουμε να ορίσετε 852 00:37:00,840 --> 00:37:05,870 το στάδιο, για αρκετά λεπτά, σε μια πολύ απλή ιδέα - 853 00:37:05,870 --> 00:37:07,620 ότι από την εναλλαγή δύο στοιχείων, έτσι δεν είναι; 854 00:37:07,620 --> 00:37:10,040 Όλοι αυτοί οι αλγόριθμοι που έχουμε πάει μιλάμε για τα τελευταία δύο 855 00:37:10,040 --> 00:37:12,420 διαλέξεις περιλαμβάνουν κάποια είδος swapping. 856 00:37:12,420 --> 00:37:14,630 Σήμερα έγινε ορατό από αυτούς να πάρει πάνω από τις καρέκλες τους και 857 00:37:14,630 --> 00:37:18,570 περπάτημα γύρω, αλλά και στον κώδικα, θα θέλαμε μόλις λάβει ένα στοιχείο από μια συστοιχία 858 00:37:18,570 --> 00:37:20,370 και το γδούπο σε ένα άλλο. 859 00:37:20,370 --> 00:37:21,880 >> Επομένως, πώς θα πάει για να κάνει αυτό; 860 00:37:21,880 --> 00:37:24,850 Λοιπόν, επιτρέψτε μου να πάει μπροστά και να γράφουν ένα γρήγορο πρόγραμμα εδώ. 861 00:37:24,850 --> 00:37:31,600 Πάω να πάει μπροστά και να κάνουμε αυτό ως εξής. 862 00:37:31,600 --> 00:37:33,910 Ας το ονομάσουμε αυτό - 863 00:37:33,910 --> 00:37:38,070 τι θέλουμε να καλέσετε αυτό; 864 00:37:38,070 --> 00:37:38,650 >> Στην πραγματικότητα, όχι. 865 00:37:38,650 --> 00:37:39,420 Επιτρέψτε μου προς τα πίσω. 866 00:37:39,420 --> 00:37:41,220 Δεν θέλω να το κάνω αυτό Cliffhanger ακόμα. 867 00:37:41,220 --> 00:37:42,270 Θα χαλάσουμε τη διασκέδαση. 868 00:37:42,270 --> 00:37:43,600 Ας το κάνουμε αντ 'αυτού. 869 00:37:43,600 --> 00:37:47,430 >> Ας υποθέσουμε ότι θέλω να γράψω ένα μικρό του προγράμματος και ότι αγκαλιάζει τώρα αυτό 870 00:37:47,430 --> 00:37:48,700 ιδέα της αναδρομής. 871 00:37:48,700 --> 00:37:50,370 Ι το είδος του πήρε μπροστά από τον εαυτό μου εκεί. 872 00:37:50,370 --> 00:37:51,420 Πάω να κάνετε τα εξής. 873 00:37:51,420 --> 00:38:00,220 >> Πρώτον, μια γρήγορη περιλαμβάνουν τυποποιημένων io.h, καθώς και περιλαμβάνουν από cs50.h. 874 00:38:00,220 --> 00:38:03,200 Και τότε Πάω να πάει μπροστά και να κηρύξει άκυρη int main 875 00:38:03,200 --> 00:38:04,360 κατά τον συνήθη τρόπο. 876 00:38:04,360 --> 00:38:07,920 Συνειδητοποίησα ότι έχω misnamed το αρχείο, έτσι ώστε επιτρέψτε μου να προσθέσω μόνο μια επέκταση. c εδώ τόσο 877 00:38:07,920 --> 00:38:09,510 ότι μπορούμε να το υπολογίσουν σωστά. 878 00:38:09,510 --> 00:38:10,970 Ξεκινήστε αυτή τη λειτουργία. 879 00:38:10,970 --> 00:38:13,290 >> Και η λειτουργία θέλω να γράψω, αρκετά απλά, είναι αυτό που ζητά η 880 00:38:13,290 --> 00:38:16,210 χρήστη για έναν αριθμό και στη συνέχεια προσθέτει μέχρι όλοι οι αριθμοί που μεταξύ 881 00:38:16,210 --> 00:38:19,920 τον αριθμό και, ας πούμε, 0. 882 00:38:19,920 --> 00:38:22,510 Έτσι, η πρώτη Πάω να προχωρήσει και να κηρύξει int n. 883 00:38:22,510 --> 00:38:24,760 Τότε μπορώ να αντιγράψω κάποια κώδικα που έχουμε χρησιμοποιήσει για λίγο. 884 00:38:24,760 --> 00:38:26,660 Αν κάτι είναι αληθές. 885 00:38:26,660 --> 00:38:28,000 Θα επανέλθω στο θέμα αυτό σε μια στιγμή. 886 00:38:28,000 --> 00:38:29,010 >> Τι θέλω να κάνω; 887 00:38:29,010 --> 00:38:33,460 Θέλω να πω printf θετική ακέραιος παρακαλώ. 888 00:38:33,460 --> 00:38:36,130 Και τότε Πάω να λένε n παίρνει πάρει int. 889 00:38:36,130 --> 00:38:38,800 Έτσι και πάλι, κάποιος κώδικας στερεότυπο που έχουμε χρησιμοποιήσει στο παρελθόν. 890 00:38:38,800 --> 00:38:40,810 Και Πάω να το κάνετε αυτό ενώ η η είναι μικρότερη από 1. 891 00:38:40,810 --> 00:38:44,120 Έτσι, αυτό θα εξασφαλίσει ότι ο χρήστης μου δίνει ένα θετικό ακέραιο. 892 00:38:44,120 --> 00:38:45,490 >> Και τώρα είμαι πρόκειται να κάνει το εξής. 893 00:38:45,490 --> 00:38:51,020 Θέλω να προσθέσει επάνω όλους τους αριθμούς μεταξύ 1 και και το η ή 0 και το η, 894 00:38:51,020 --> 00:38:52,570 ισοδύναμα, για να πάρει το συνολικό ποσό. 895 00:38:52,570 --> 00:38:55,100 Έτσι, το μεγάλο σύμβολο σίγμα ότι ίσως θυμάστε. 896 00:38:55,100 --> 00:38:59,050 Έτσι, Πάω να το κάνουμε αυτό από την πρώτη κλήση μια λειτουργία που ονομάζεται σίγμα, 897 00:38:59,050 --> 00:39:06,030 περνώντας στο n, και στη συνέχεια θα πάω να λένε printf, η απάντηση είναι εκεί. 898 00:39:06,030 --> 00:39:08,180 >> Έτσι, με λίγα λόγια, να πάρω και int από το χρήστη. 899 00:39:08,180 --> 00:39:09,280 Θα εξασφαλίσει ότι είναι θετικό. 900 00:39:09,280 --> 00:39:12,700 Δηλώνω μια μεταβλητή που ονομάζεται απάντηση int τύπου και αποθηκεύστε σε αυτό η επιστροφή 901 00:39:12,700 --> 00:39:15,610 αξία της σίγμα, περνώντας n ως είσοδο. 902 00:39:15,610 --> 00:39:17,060 Και τότε θα εκτυπώσετε την απάντηση. 903 00:39:17,060 --> 00:39:19,550 >> Δυστυχώς, ακόμη και αν σίγμα ακούγεται σαν κάτι που μπορεί να είναι σε 904 00:39:19,550 --> 00:39:24,040 το αρχείο math.h, δήλωση, στην πραγματικότητα δεν είναι. 905 00:39:24,040 --> 00:39:24,690 Έτσι, αυτό είναι εντάξει. 906 00:39:24,690 --> 00:39:26,170 Μπορώ να εφαρμόσει τον εαυτό μου αυτό. 907 00:39:26,170 --> 00:39:29,160 Πάω να εφαρμόσουν μια λειτουργία που ονομάζεται σίγμα, και πρόκειται να λάβει ένα 908 00:39:29,160 --> 00:39:29,900 παράμετρος - 909 00:39:29,900 --> 00:39:32,100 ας το ονομάσουμε m, απλά γι 'αυτό είναι διαφορετικό. 910 00:39:32,100 --> 00:39:35,910 Και στη συνέχεια, μέχρι εδώ, θα πάω να πω, Λοιπόν, αν το m είναι μικρότερο από 1 - αυτό είναι ένα 911 00:39:35,910 --> 00:39:38,180 πολύ πληκτικός πρόγραμμα. 912 00:39:38,180 --> 00:39:41,700 Έτσι, Πάω να προχωρήσει και επιστρέψει αμέσως 0. 913 00:39:41,700 --> 00:39:45,920 Απλώς δεν έχει νόημα να προσθέσουμε όλα οι αριθμοί μεταξύ 1 και m, εάν m 914 00:39:45,920 --> 00:39:48,470 είναι η ίδια μηδέν ή αρνητική. 915 00:39:48,470 --> 00:39:50,900 >> Και τότε Πάω να πάει μπροστά και να το κάνουμε αυτό πολύ επαναληπτικά. 916 00:39:50,900 --> 00:39:53,090 Πάω να κάνω αυτό το είδος της παλιάς σχολής, και θα πάω να προχωρήσει 917 00:39:53,090 --> 00:39:57,150 και να πω ότι είμαι πρόκειται να δηλώνει ένα ποσό να είναι 0. 918 00:39:57,150 --> 00:39:59,630 Στη συνέχεια, Πάω να έχουν βρόχο for της int - 919 00:39:59,630 --> 00:40:02,820 και επιτρέψτε μου να το κάνει να ταιριάζει με μας Κώδικα Διαχείρισης του Δικτύου, έτσι ώστε να έχετε ένα αντίγραφο 920 00:40:02,820 --> 00:40:07,500 στο σπίτι. int i παίρνει 1 μέχρι και σε Ι είναι μικρότερο ή ίσο με m. 921 00:40:07,500 --> 00:40:09,430 i plus plus. 922 00:40:09,430 --> 00:40:11,430 Και τότε μέσα από αυτό για loop - 923 00:40:11,430 --> 00:40:12,440 είμαστε σχεδόν εκεί - 924 00:40:12,440 --> 00:40:15,810 άθροισμα παίρνει ποσού συν 1. 925 00:40:15,810 --> 00:40:17,670 Και τότε Πάω να επιστρέψει το ποσό. 926 00:40:17,670 --> 00:40:19,420 >> Έτσι έκανα αυτό γρήγορα, ομολογουμένως αρκετά. 927 00:40:19,420 --> 00:40:22,775 Αλλά και πάλι, η κύρια λειτουργία είναι αρκετά απλή, με βάση τον κωδικό έχουμε 928 00:40:22,775 --> 00:40:23,190 γραμμένο μέχρι στιγμής. 929 00:40:23,190 --> 00:40:25,610 Χρησιμοποιεί το διπλό βρόχο για να πάρει ένα θετικό int από το χρήστη. 930 00:40:25,610 --> 00:40:29,870 Περνώ στη συνέχεια ότι int σε μια νέα λειτουργία ονομάζεται σίγμα, αποκαλώντας, και πάλι, n. 931 00:40:29,870 --> 00:40:33,100 Και να φυλάξω την τιμή επιστροφής, η απάντηση από το μαύρο κουτί του παρόντος 932 00:40:33,100 --> 00:40:35,460 γνωστή ως σίγμα, σε μια μεταβλητή ονομάζεται απάντηση. 933 00:40:35,460 --> 00:40:36,580 Τότε να το εκτυπώσετε. 934 00:40:36,580 --> 00:40:39,090 >> Αν συνεχίσουμε τώρα την ιστορία, πώς είναι σίγμα εφαρμοστεί; 935 00:40:39,090 --> 00:40:40,840 Προτείνω να εφαρμόσει ως εξής. 936 00:40:40,840 --> 00:40:43,560 Πρώτον, ένα μικρό κομμάτι του ελέγχου σφαλμάτων για να βεβαιωθείτε ότι ο χρήστης δεν είναι 937 00:40:43,560 --> 00:40:46,480 ρύπανση με μένα και περνώντας κάποια αρνητικά ή τιμή 0. 938 00:40:46,480 --> 00:40:49,710 Στη συνέχεια, δηλώνω μια μεταβλητή που ονομάζεται Συνοψίζοντας και να το θέσει σε 0. 939 00:40:49,710 --> 00:40:55,910 >> Και τώρα αρχίζουν να κινούνται από το i ισούται 1 σε όλη τη διαδρομή μέχρι και m, 940 00:40:55,910 --> 00:41:00,130 γιατί θέλω να περιλαμβάνει όλα τα αριθμούς από το ένα μέχρι m, χωρίς αποκλεισμούς. 941 00:41:00,130 --> 00:41:04,350 Και μέσα από αυτό για το βρόχο, εγώ απλά κάνω ποσό που παίρνει ό, τι είναι τώρα, συν το 942 00:41:04,350 --> 00:41:08,900 τιμή του i. 943 00:41:08,900 --> 00:41:10,370 Πλέον η τιμή του i. 944 00:41:10,370 --> 00:41:14,090 >> Παρεμπιπτόντως, αν έχετε δεν δει αυτό πριν, υπάρχει κάποια συντακτική ζάχαρη 945 00:41:14,090 --> 00:41:14,870 για αυτή τη γραμμή. 946 00:41:14,870 --> 00:41:21,120 Μπορώ να ξαναγράψουμε αυτό ως συν i ισούται με, μόνο για να σώσει τον εαυτό μου μερικές πληκτρολογήσεις 947 00:41:21,120 --> 00:41:22,570 και να κοιτάξουμε λίγο πιο δροσερές. 948 00:41:22,570 --> 00:41:23,140 Αλλά αυτό είναι όλο. 949 00:41:23,140 --> 00:41:24,660 Είναι λειτουργικά το ίδιο πράγμα. 950 00:41:24,660 --> 00:41:26,710 >> Δυστυχώς, αυτός ο κώδικας του δεν πρόκειται να συγκεντρώνουν ακόμα. 951 00:41:26,710 --> 00:41:31,600 Αν τρέξω να sigma 0, πώς am Ι που πηγαίνει να πάρει φώναξε; 952 00:41:31,600 --> 00:41:33,473 Τι είναι αυτό που πηγαίνει να μην αρέσει; 953 00:41:33,473 --> 00:41:35,740 >> ΚΟΙΝΟ: [δεν ακούγεται]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID MALAN: Ναι, δεν είχα δηλώσει η λειτουργία επάνω στην κορυφή, έτσι δεν είναι; 955 00:41:37,800 --> 00:41:40,590 C είναι ηλίθια, υπό την έννοια ότι μόνο κάνει ό, τι σας πει να κάνετε, και εσείς 956 00:41:40,590 --> 00:41:41,880 πρέπει να το κάνουμε με αυτή τη σειρά. 957 00:41:41,880 --> 00:41:45,910 Και έτσι, αν πατήσω το enter εδώ, Πάω να πάρετε μια προειδοποίηση σχετικά με σίγμα σιωπηρή 958 00:41:45,910 --> 00:41:46,860 δήλωση. 959 00:41:46,860 --> 00:41:48,120 >> Ω, δεν είναι πρόβλημα. 960 00:41:48,120 --> 00:41:50,370 Μπορώ να πάω μέχρι την κορυφή, και μπορώ πω, εντάξει, περιμένετε ένα λεπτό. 961 00:41:50,370 --> 00:41:54,240 Sigma είναι μια συνάρτηση που επιστρέφει μια int και αναμένει μια 962 00:41:54,240 --> 00:41:56,620 int ως είσοδο, ερωτηματικό. 963 00:41:56,620 --> 00:41:59,550 Ή θα μπορούσε να θέσει την όλη λειτουργία πάνω από την κύρια, αλλά σε γενικές γραμμές, θα ήθελα να 964 00:41:59,550 --> 00:42:02,260 συνιστά ενάντια σε αυτό, γιατί είναι ωραίο να έχουμε πάντα το κύριο στην κορυφή, έτσι 965 00:42:02,260 --> 00:42:06,310 Μπορείτε να μπείτε μέσα και να γνωρίζει τι είναι πρόγραμμα κάνει με την ανάγνωση κύριο πρώτα. 966 00:42:06,310 --> 00:42:07,930 >> Έτσι, τώρα επιτρέψτε μου να καθαρίσετε την οθόνη. 967 00:42:07,930 --> 00:42:09,330 Remake σίγμα 0. 968 00:42:09,330 --> 00:42:10,340 Όλα φαίνεται να ελέγξετε έξω. 969 00:42:10,340 --> 00:42:11,970 Επιτρέψτε μου να τρέξει sigma 0. 970 00:42:11,970 --> 00:42:12,770 Θετική μεταξύ. 971 00:42:12,770 --> 00:42:15,580 Θα του δώσω τον αριθμό 3 να το κρατήσετε απλό. 972 00:42:15,580 --> 00:42:18,710 Έτσι, αυτό θα πρέπει να μου δώσει 3 συν 2 συν 1, έτσι ώστε 6. 973 00:42:18,710 --> 00:42:20,750 Enter, και μάλιστα παίρνω 6. 974 00:42:20,750 --> 00:42:21,820 >> Μπορώ να κάνω κάτι μεγαλύτερο - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Ακριβώς όπως μια εφαπτομένη, Πάω να κάνω κάτι γελοίο σαν ένα πραγματικά μεγάλο 977 00:42:27,690 --> 00:42:30,375 αριθμό, Ω, που πραγματικά εργάστηκαν out - 978 00:42:30,375 --> 00:42:31,600 eh, δεν νομίζω ότι αυτό είναι σωστό. 979 00:42:31,600 --> 00:42:32,810 Ας δούμε. 980 00:42:32,810 --> 00:42:34,060 Ας πραγματικά με αυτό το χάλι. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> Αυτό είναι ένα πρόβλημα. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Τι συμβαίνει; 985 00:42:44,970 --> 00:42:46,050 Ο κώδικας δεν είναι και τόσο άσχημα. 986 00:42:46,050 --> 00:42:48,470 Είναι ακόμα γραμμική. 987 00:42:48,470 --> 00:42:50,810 Σφύριγμα είναι ένα καλό αποτέλεσμα, όμως. 988 00:42:50,810 --> 00:42:52,060 Τι συμβαίνει; 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Δεν είμαι σίγουρος αν το άκουσα. 991 00:42:55,620 --> 00:42:57,620 Έτσι αποδεικνύεται - και Αυτό είναι ως ένα μέρος. 992 00:42:57,620 --> 00:42:59,400 Αυτό δεν είναι βασικές για τη ιδέα της αναδρομής. 993 00:42:59,400 --> 00:43:02,480 Αποδεικνύεται, γιατί προσπαθώ να αντιπροσωπεύουν ένα τόσο μεγάλο αριθμό, οι περισσότεροι 994 00:43:02,480 --> 00:43:06,980 πιθανότερο είναι να παρερμηνευθεί από C ως ένα μη θετικό αριθμό, 995 00:43:06,980 --> 00:43:09,980 αλλά αρνητικός αριθμός. 996 00:43:09,980 --> 00:43:12,690 >> Δεν έχουμε μιλήσει γι 'αυτό, αλλά Αποδεικνύεται ότι υπάρχουν αρνητικοί αριθμοί 997 00:43:12,690 --> 00:43:14,210 στον κόσμο στην προσθήκη με θετικούς αριθμούς. 998 00:43:14,210 --> 00:43:16,290 Και τα μέσα με τα οποία μπορείτε να αντιπροσωπεύουν έναν αρνητικό αριθμό 999 00:43:16,290 --> 00:43:19,530 ουσιαστικά είναι, μπορείτε να χρησιμοποιήσετε ένα ειδικό κομμάτι για να δείξει 1000 00:43:19,530 --> 00:43:20,400 θετικών έναντι των αρνητικών. 1001 00:43:20,400 --> 00:43:22,950 Είναι λίγο πιο περίπλοκη από αυτό, αλλά αυτή είναι η βασική ιδέα. 1002 00:43:22,950 --> 00:43:26,740 >> Έτσι, δυστυχώς, αν C είναι συγχέοντας ένα από εκείνα τα κομμάτια που πραγματικά σημαίνει, 1003 00:43:26,740 --> 00:43:30,790 Ω, αυτό είναι ένας αρνητικός αριθμός, βρόχος μου εδώ, για παράδειγμα, είναι στην πραγματικότητα ποτέ δεν 1004 00:43:30,790 --> 00:43:31,740 πρόκειται να τερματίσει. 1005 00:43:31,740 --> 00:43:33,850 Έτσι, αν ήμουν εκτύπωση πραγματικά κάτι ξανά και ξανά, εμείς θα 1006 00:43:33,850 --> 00:43:34,650 δείτε ένα σωρό. 1007 00:43:34,650 --> 00:43:36,220 Αλλά και πάλι, αυτό είναι πέρα ​​από το σημείο. 1008 00:43:36,220 --> 00:43:38,590 Αυτό είναι πραγματικά ακριβώς ένα είδος διανοητική περιέργεια ότι θα έρθει 1009 00:43:38,590 --> 00:43:39,550 πίσω για να τελικά. 1010 00:43:39,550 --> 00:43:43,400 Αλλά για τώρα, αυτό είναι μια σωστή εφαρμογή αν υποθέσουμε ότι η 1011 00:43:43,400 --> 00:43:45,970 χρήστης θα παρέχει ints που χωρούν μέσα σε ints. 1012 00:43:45,970 --> 00:43:49,370 >> Αλλά εγώ ισχυρίζονται ότι ο κώδικας αυτός, ειλικρινά, θα μπορούσε να γίνει πολύ πιο απλά. 1013 00:43:49,370 --> 00:43:54,060 Αν ο στόχος είναι στο χέρι για να λάβει μια σειρά όπως το m και να προσθέσετε μέχρι όλα τα 1014 00:43:54,060 --> 00:43:59,510 αριθμούς μεταξύ αυτής και 1, ή αντιστρόφως μεταξύ 1 και, αξιώνω 1015 00:43:59,510 --> 00:44:03,380 που μπορώ να δανειστώ αυτή την ιδέα που συγχωνεύονται Ταξινόμηση είχε, η οποία έπαιρνε ένα πρόβλημα 1016 00:44:03,380 --> 00:44:05,660 αυτού του μεγέθους και διαιρώντας το σε κάτι μικρότερο. 1017 00:44:05,660 --> 00:44:09,875 Ίσως δεν είναι το μισό, αλλά μικρότερο, αλλά αντιπροσωπευτικά το ίδιο. 1018 00:44:09,875 --> 00:44:12,130 Ίδια ιδέα, αλλά ένα μικρότερο πρόβλημα. 1019 00:44:12,130 --> 00:44:15,470 >> Έτσι είμαι πραγματικά - επιτρέψτε μου να αποθηκεύσετε αυτό το αρχείο με διαφορετικό αριθμό έκδοσης. 1020 00:44:15,470 --> 00:44:17,670 Θα το ονομάσουμε έκδοση 1 αντί για 0. 1021 00:44:17,670 --> 00:44:20,790 Και εγώ ισχυρίζομαι ότι μπορώ πραγματικά να Νέα υλοποίηση αυτή σε αυτό το είδος της 1022 00:44:20,790 --> 00:44:22,160 μυαλό κάμψης τρόπο. 1023 00:44:22,160 --> 00:44:23,710 >> Πάω να αφήσετε ένα μέρος μόνο του. 1024 00:44:23,710 --> 00:44:27,710 Πάω να πω αν το m είναι λιγότερο από ή ακόμα και ίσο με 0 - 1025 00:44:27,710 --> 00:44:29,280 Είμαι ακριβώς πρόκειται να είναι λίγο πιο πρωκτού αυτή τη φορά 1026 00:44:29,280 --> 00:44:30,520 με τον έλεγχο λάθος μου - 1027 00:44:30,520 --> 00:44:33,190 Πάω να πάει μπροστά και να επιστρέψει 0. 1028 00:44:33,190 --> 00:44:34,490 Αυτό είναι αυθαίρετος. 1029 00:44:34,490 --> 00:44:37,500 Είμαι απλά να αποφασίσει αν ο χρήστης μου δίνει έναν αρνητικό αριθμό, είμαι 1030 00:44:37,500 --> 00:44:41,490 επιστρέφει 0, και θα πρέπει να έχουν διαβάσει η τεκμηρίωση πιο στενά. 1031 00:44:41,490 --> 00:44:42,170 >> Αλλιώς - 1032 00:44:42,170 --> 00:44:44,070 παρατηρήσετε τι Πάω να κάνουμε. 1033 00:44:44,070 --> 00:44:49,260 Αλλιώς εγώ είμαι πρόκειται να επιστρέψει m συν - 1034 00:44:49,260 --> 00:44:51,010 τι είναι σίγμα του m; 1035 00:44:51,010 --> 00:44:56,710 Λοιπόν, ΣΙΓΜΑ m συν m μείον 1, m συν πλην 2, συν m μείον 3. 1036 00:44:56,710 --> 00:44:58,030 Δεν θέλω να γράψω όλα αυτά έξω. 1037 00:44:58,030 --> 00:44:59,120 Γιατί δεν μπορώ απλά punt; 1038 00:44:59,120 --> 00:45:05,080 Αναδρομικά ονομάζω τον εαυτό μου με ένα ελαφρώς μικρότερο πρόβλημα, ερωτηματικό, 1039 00:45:05,080 --> 00:45:06,840 και να το ονομάσουμε την ημέρα; 1040 00:45:06,840 --> 00:45:07,040 >> Σωστά; 1041 00:45:07,040 --> 00:45:10,980 Τώρα, εδώ, πάρα πολύ, ίσως να αισθάνονται ή να ανησυχείτε ότι αυτό είναι ένα άπειρο βρόχο ότι είμαι 1042 00:45:10,980 --> 00:45:15,450 προκαλώντας, σύμφωνα με την οποία είμαι εφαρμογής σίγμα καλώντας σίγμα. 1043 00:45:15,450 --> 00:45:20,342 Αλλά αυτό είναι απολύτως εντάξει, γιατί σκέφτηκε μπροστά ένα πρόσθετο το οποίο γραμμές; 1044 00:45:20,342 --> 00:45:22,600 >> ΚΟΙΝΟ: [δεν ακούγεται]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID MALAN: 23 έως 26, οι οποίες είναι αν η κατάστασή μου. 1046 00:45:25,430 --> 00:45:28,390 Γιατί ό, τι είναι καλό για το αφαίρεση εδώ, γιατί έχω κρατήσει 1047 00:45:28,390 --> 00:45:31,180 παράδοση σίγμα μικρότερα προβλήματα, μικρότερα προβλήματα, μικρότερα - δεν είναι 1048 00:45:31,180 --> 00:45:31,870 το μισό μέγεθος. 1049 00:45:31,870 --> 00:45:34,380 Είναι μόνο ένα μικρό βήμα μικρότερο, αλλά αυτό είναι εντάξει. 1050 00:45:34,380 --> 00:45:38,050 Διότι τελικά, θα λειτουργήσει δρόμο μας μέχρι 1 ή 0. 1051 00:45:38,050 --> 00:45:41,630 Και από τη στιγμή που χτύπησε 0, Sigma δεν είναι πρόκειται να αυτοαποκαλείται πια. 1052 00:45:41,630 --> 00:45:43,590 Είναι πρόκειται να επιστρέψει αμέσως 0. 1053 00:45:43,590 --> 00:45:47,960 >> Έτσι, το αποτέλεσμα, αν το είδος του ανέμου αυτό στο μυαλό σας, είναι να προσθέσετε m συν 1054 00:45:47,960 --> 00:45:52,740 m μείον 1, συν πλην 2 m, συν m μείον 3, καθώς και τελεία, τελεία, τελεία, m μείον 1055 00:45:52,740 --> 00:45:57,820 m, τελικά, δίνοντας σας 0, και η αποτέλεσμα είναι τελικά να προσθέσετε όλα 1056 00:45:57,820 --> 00:45:59,070 αυτά τα πράγματα μαζί. 1057 00:45:59,070 --> 00:46:02,380 Έτσι, δεν έχουμε, με αναδρομή, λυθεί το πρόβλημα που 1058 00:46:02,380 --> 00:46:03,470 δεν θα μπορούσε να λύσει πριν. 1059 00:46:03,470 --> 00:46:06,840 Πράγματι, 0 εκδοχή αυτή, και κάθε πρόβλημα μέχρι σήμερα, έχει επιλύσιμο 1060 00:46:06,840 --> 00:46:09,980 με τη χρήση μόνο για βρόχους ή ενώ βρόχους ή παρόμοια κατασκευάσματα. 1061 00:46:09,980 --> 00:46:13,150 >> Αλλά αναδρομή, τολμώ να πω, μας δίνει ένας διαφορετικός τρόπος σκέψης σχετικά με 1062 00:46:13,150 --> 00:46:17,010 προβλήματα, οπότε αν μπορούμε να πάρουμε μια πρόβλημα, χωρίζουν από κάτι 1063 00:46:17,010 --> 00:46:22,340 κάπως μεγάλο σε κάτι κάπως μικρότερα, εγώ ισχυρίζομαι ότι μπορούμε να το λύσουμε 1064 00:46:22,340 --> 00:46:26,040 ίσως λίγο πιο κομψά άποψη του σχεδιασμού, με λιγότερο κώδικα, 1065 00:46:26,040 --> 00:46:30,980 και ίσως ακόμη και να λύσει τα προβλήματα που θα είναι πιο δύσκολο, καθώς θα τελικά 1066 00:46:30,980 --> 00:46:33,280 Βλέπετε, την επίλυση καθαρά επαναληπτικό. 1067 00:46:33,280 --> 00:46:35,980 >> Αλλά η δραματική στιγμή που έκανα θέλουν να μας αφήσουν σε αυτό ήταν. 1068 00:46:35,980 --> 00:46:40,720 Επιτρέψτε μου να προχωρήσει και να ανοίξει δημιουργήσει ένα αρχείο από - 1069 00:46:40,720 --> 00:46:44,300 Στην πραγματικότητα, επιτρέψτε μου να πάω και το κάνετε αυτό πολύ γρήγορα. 1070 00:46:44,300 --> 00:46:46,875 Επιτρέψτε μου να πάμε μπροστά και να προτείνει η ακόλουθη. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Μεταξύ κωδικός σήμερα είναι αυτό το αρχείο εδώ. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 Αυτός εδώ, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Έτσι, αυτό είναι μια ηλίθια μικρό πρόγραμμα που I χτυπημένη ότι οι απαιτήσεις να κάνουν 1076 00:47:06,260 --> 00:47:06,940 η ακόλουθη. 1077 00:47:06,940 --> 00:47:10,140 Σε γενικές γραμμές, δηλώνει για πρώτη φορά ένα int ονομάζεται x και εκχωρεί 1078 00:47:10,140 --> 00:47:11,100 η τιμή του 1. 1079 00:47:11,100 --> 00:47:13,520 Στη συνέχεια, δηλώνει ένα int y και εκχωρεί την τιμή 2. 1080 00:47:13,520 --> 00:47:15,310 Στη συνέχεια εκτυπώνει τι x και y είναι. 1081 00:47:15,310 --> 00:47:17,781 Στη συνέχεια, λέει, εναλλαγή, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Στη συνέχεια, ισχυρίζεται ότι είναι καλώντας μια συνάρτηση ονομάζεται swap, περνώντας x και 1083 00:47:21,670 --> 00:47:24,290 y, η ιδέα της οποίας είναι ότι ελπίζουμε x και y θα επανέλθει 1084 00:47:24,290 --> 00:47:25,620 διαφορετικά, το αντίθετο. 1085 00:47:25,620 --> 00:47:27,110 Στη συνέχεια, ισχυρίζονται αντάλλαξαν! 1086 00:47:27,110 --> 00:47:28,420 με ένα θαυμαστικό. 1087 00:47:28,420 --> 00:47:30,190 Στη συνέχεια εκτυπώνει x και y. 1088 00:47:30,190 --> 00:47:33,480 >> Αλλά αποδεικνύεται ότι αυτή η πολύ απλή επίδειξη κάτω 1089 00:47:33,480 --> 00:47:35,570 εδώ είναι πραγματικά λάθη. 1090 00:47:35,570 --> 00:47:38,870 Ακόμα κι αν είμαι με την οποία μια προσωρινή μεταβλητή και προσωρινά, βάζοντας ένα σε 1091 00:47:38,870 --> 00:47:42,010 αυτό, τότε είμαι ανακατανομή μια τιμή η της β - 1092 00:47:42,010 --> 00:47:45,080 η οποία αισθάνεται λογικό, γιατί έχω αποθηκεύσει ένα αντίγραφο της στο temp. 1093 00:47:45,080 --> 00:47:48,410 Τότε μπορώ να ενημερώσω το b για ίση Όποια και αν ήταν στο temp. 1094 00:47:48,410 --> 00:47:51,610 Αυτό το είδος του παιχνιδιού κελύφους κινείται ένα σε b και Β σε ένα χρησιμοποιώντας αυτό 1095 00:47:51,610 --> 00:47:54,360 μεσαία-man όνομα temp αισθάνεται απολύτως λογικό. 1096 00:47:54,360 --> 00:47:57,270 >> Αλλά εγώ ισχυρίζομαι ότι όταν τρέχω κώδικα, όπως θα κάνω τώρα - 1097 00:47:57,270 --> 00:47:59,490 επιτρέψτε μου να πάω μπροστά και να το επικολλήσετε στο εδώ. 1098 00:47:59,490 --> 00:48:01,995 Θα πάρω αυτό το noswap.c. 1099 00:48:01,995 --> 00:48:05,630 Και όπως υποδηλώνει το όνομα, αυτό δεν είναι πρόκειται να είναι ένα σωστό πρόγραμμα. 1100 00:48:05,630 --> 00:48:09,460 Κάντε noswap. / Όχι swap. 1101 00:48:09,460 --> 00:48:12,110 x είναι 1, y είναι 2, swapping, ανταλλαχθούν. 1102 00:48:12,110 --> 00:48:14,220 το χ είναι 1, το Υ είναι 2. 1103 00:48:14,220 --> 00:48:16,920 Αυτό είναι εντελώς λάθος, ακόμα και αν και αυτό φαίνεται απόλυτα 1104 00:48:16,920 --> 00:48:17,730 λογικό για μένα. 1105 00:48:17,730 --> 00:48:21,330 Και υπάρχει ένας λόγος, αλλά δεν είμαστε πρόκειται να αποκαλύψει το λόγο ακριβώς ακόμα. 1106 00:48:21,330 --> 00:48:24,610 >> Προς το παρόν το δεύτερο δραματική στιγμή που ήθελα να σας αφήσω με είναι αυτό, ένα 1107 00:48:24,610 --> 00:48:27,120 αναγγελία του είδους για τους κωδικούς κουπόνι. 1108 00:48:27,120 --> 00:48:31,590 Η καινοτομία μας με τελευταίες μέρες του τρέχοντος έτους προκάλεσε ένα μη ευκαταφρόνητο αριθμό 1109 00:48:31,590 --> 00:48:33,830 ερωτήσεων, η οποία ήταν δεν είναι πρόθεσή μας. 1110 00:48:33,830 --> 00:48:36,590 Η πρόθεση αυτών των κουπόνι κώδικες, σύμφωνα με την οποία αν το κάνετε μέρος του προβλήματος 1111 00:48:36,590 --> 00:48:39,850 που από νωρίς, με αποτέλεσμα να πάρει μια επιπλέον ημέρα, ήταν πραγματικά να σας βοηθήσει να βοηθήσει παιδιά 1112 00:48:39,850 --> 00:48:42,420 τον εαυτό σας ξεκινήσει νωρίς, το είδος της με την παροχή κινήτρων για εσάς. 1113 00:48:42,420 --> 00:48:44,880 Μας βοηθά να διανείμει το φορτίο σε ώρες γραφείου καλύτερα, έτσι ώστε 1114 00:48:44,880 --> 00:48:45,740 Είναι είδος της win-win. 1115 00:48:45,740 --> 00:48:48,860 >> Δυστυχώς, νομίζω ότι τις οδηγίες μου δεν έχουν, μέχρι σήμερα, πολύ σαφής, έτσι ώστε 1116 00:48:48,860 --> 00:48:52,230 Πήγα πίσω αυτό το Σαββατοκύριακο και να ενημερώνονται το spec σε μεγαλύτερες, πιο τολμηρή κείμενο 1117 00:48:52,230 --> 00:48:53,600 εξηγήσει σφαίρες σαν αυτές. 1118 00:48:53,600 --> 00:48:56,900 Και απλά για να το πω πιο κοινό, με προεπιλογή, προβλήματα οφείλονται Πέμπτη 1119 00:48:56,900 --> 00:48:58,400 το μεσημέρι, σύμφωνα με το αναλυτικό πρόγραμμα. 1120 00:48:58,400 --> 00:49:02,030 Αν ξεκινήσετε νωρίς, τερματίζοντας μέρος του το πρόβλημα που μέχρι την Τετάρτη στις 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, το μέρος που σχετίζεται με ένα κουπόνι κώδικα, η ιδέα είναι ότι μπορείτε να επεκτείνετε 1122 00:49:05,170 --> 00:49:07,710 προθεσμία σας για το P που μέχρι την Παρασκευή. 1123 00:49:07,710 --> 00:49:10,890 Δηλαδή, δάγκωσε ένα μικρό μέρος του P που σε σχέση με ό, τι συνήθως είναι η 1124 00:49:10,890 --> 00:49:13,200 μεγαλύτερο πρόβλημα, και να αγοράσετε τον εαυτό σας μια επιπλέον ημέρα. 1125 00:49:13,200 --> 00:49:15,190 Και πάλι, σας παίρνει να σκεφτόμαστε το σύνολο πρόβλημα, σας παίρνει να 1126 00:49:15,190 --> 00:49:16,380 ώρες γραφείου νωρίτερα. 1127 00:49:16,380 --> 00:49:20,670 Αλλά το πρόβλημα κωδικό κουπονιού είναι ακόμα απαιτείται, ακόμα κι αν δεν την υποβάλει. 1128 00:49:20,670 --> 00:49:23,340 >> Αλλά πιο συναρπαστικά είναι αυτό. 1129 00:49:23,340 --> 00:49:26,520 (Θεατρικός μονόλογος) Και εκείνοι οι λαοί αφήνοντας νωρίς είναι θα το μετανιώσετε. 1130 00:49:26,520 --> 00:49:28,620 Δεδομένου ότι οι λαοί στο μπαλκόνι. 1131 00:49:28,620 --> 00:49:32,510 Ζητώ συγγνώμη εκ των προτέρων για τους λαούς για το μπαλκόνι για λόγους που θα 1132 00:49:32,510 --> 00:49:33,920 σαφές ακριβώς σε μια στιγμή. 1133 00:49:33,920 --> 00:49:37,050 >> Έτσι, είμαστε τυχεροί να έχουμε ένα από τα Πρώην υποτρόφων διδασκαλίας CS50 το κεφάλι σε 1134 00:49:37,050 --> 00:49:39,302 μια εταιρεία που ονομάζεται dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Έχουν πολύ γενναιόδωρα δώρισε κωδικό κουπονιού εδώ γι 'αυτό το πολύ χώρο, 1136 00:49:45,500 --> 00:49:48,180 η οποία είναι πάνω από το συνήθως 2 gigabytes. 1137 00:49:48,180 --> 00:49:51,740 Έτσι, αυτό που νόμιζα ότι θα κάνουμε σε αυτό τελευταία σημείωση είναι να κάνετε ένα κομμάτι από ένα giveaway, 1138 00:49:51,740 --> 00:49:55,380 σύμφωνα με την οποία σε μια στιγμή, θα αποκαλύψει ο νικητής και ποιος έχει ένα κουπόνι 1139 00:49:55,380 --> 00:49:57,980 κώδικα που τότε μπορείτε να πάτε για να τους ιστοσελίδα, πληκτρολογήστε, και voila, έχετε ένα 1140 00:49:57,980 --> 00:50:01,370 πάρα πολύ περισσότερο χώρο για το Dropbox σας συσκευή και για τα προσωπικά σας αρχεία. 1141 00:50:01,370 --> 00:50:05,690 >> Και πρώτα, που θα ήθελαν να συμμετάσχουν σε αυτό το σχέδιο; 1142 00:50:05,690 --> 00:50:09,630 Εντάξει, τώρα που το καθιστά ακόμη πιο διασκεδαστικό. 1143 00:50:09,630 --> 00:50:14,010 Το πρόσωπο που λαμβάνει αυτό το 25-gigabyte κωδικό κουπονιού - που είναι πολύ 1144 00:50:14,010 --> 00:50:16,150 πιο συναρπαστικό από τα τέλη του μέρες τώρα, ίσως - 1145 00:50:16,150 --> 00:50:20,620 είναι αυτός που κάθεται στην κορυφή ενός μαξιλάρι του καθίσματος κάτω από την οποία υπάρχει 1146 00:50:20,620 --> 00:50:21,620 ότι κωδικό κουπονιού. 1147 00:50:21,620 --> 00:50:23,480 Μπορείτε τώρα να δείτε κάτω μαξιλάρι του καθίσματος σας. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [PLAYBACK VIDEO] 1150 00:50:29,680 --> 00:50:31,620 >> Ένα, δύο, τρία. 1151 00:50:31,620 --> 00:50:35,015 >> [Ουρλιάζει] 1152 00:50:35,015 --> 00:50:35,985 >> -Μπορείτε να πάρετε ένα αυτοκίνητο! 1153 00:50:35,985 --> 00:50:36,670 Μπορείτε να πάρετε ένα αυτοκίνητο! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID MALAN: Θα δούμε σας την Τετάρτη. 1155 00:50:37,970 --> 00:50:38,904 >> -Μπορείτε να πάρετε ένα αυτοκίνητο! 1156 00:50:38,904 --> 00:50:39,371 Μπορείτε να πάρετε ένα αυτοκίνητο! 1157 00:50:39,371 --> 00:50:40,305 Μπορείτε να πάρετε ένα αυτοκίνητο! 1158 00:50:40,305 --> 00:50:41,706 Μπορείτε να πάρετε ένα αυτοκίνητο! 1159 00:50:41,706 --> 00:50:43,107 Μπορείτε να πάρετε ένα αυτοκίνητο! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID MALAN: λαοί Μπαλκόνι, έρχονται εδώ κάτω προς τα εμπρός, 1161 00:50:45,530 --> 00:50:46,866 όπου έχουμε extras. 1162 00:50:46,866 --> 00:50:50,282 >> -Ο καθένας παίρνει ένα αυτοκίνητο! 1163 00:50:50,282 --> 00:50:52,234 Ο καθένας παίρνει ένα αυτοκίνητο! 1164 00:50:52,234 --> 00:50:52,722 >> [PLAYBACK VIDEO END] 1165 00:50:52,722 --> 00:50:54,590 >> Αφηγητής: Στο επόμενο CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> ΟΜΙΛΗΤΗΣ 5: Θεέ μου Θεέ Θεέ Θεέ Θεέ μου θεέ μου θεέ μου θεέ μου θεέ μου θεέ μου - 1167 00:51:00,374 --> 00:51:02,106 >> [ΘΕΑΤΡΙΚΑ UKELELE]