1
00:00:00,000 --> 00:00:03,332
>> [Παίζει μουσική]

2
00:00:03,332 --> 00:00:06,490
>> ANDI PENG: Καλώς ήρθατε στην εβδομάδα 3 του τμήματος.

3
00:00:06,490 --> 00:00:09,550
Ευχαριστώ, παιδιά, για τα οποία προέρχονται όλα
σε αυτή την πρώτη ώρα έναρξης σήμερα.

4
00:00:09,550 --> 00:00:11,466
Έχουμε ένα ωραίο, μικρό
οικεία ομάδα σήμερα.

5
00:00:11,466 --> 00:00:14,570
Έτσι, ελπίζουμε ότι θα φτάσουμε
φινίρισμα, ίσως, από νωρίς,

6
00:00:14,570 --> 00:00:15,780
λίγο νωρίς σήμερα.

7
00:00:15,780 --> 00:00:22,057
Έτσι γρήγορα, μόλις μερικά
Ανακοινώσεις για τη σημερινή ημερήσια διάταξη.

8
00:00:22,057 --> 00:00:23,890
Πριν αρχίσουμε, είμαστε
Θα πήγαινε πάνω

9
00:00:23,890 --> 00:00:28,910
μερικές σύντομες οργανωτικών ζητημάτων, το chipset
ερωτήσεις, debrief, τέτοια πράγματα.

10
00:00:28,910 --> 00:00:30,250
Και τότε θα μπείτε στα βαθιά.

11
00:00:30,250 --> 00:00:34,710
Θα χρησιμοποιήσουμε ένα πρόγραμμα εντοπισμού σφαλμάτων που ονομάζεται GDB να
ξεκινήστε την απομυθοποίηση μας κώδικα, ο οποίος David

12
00:00:34,710 --> 00:00:36,550
εξήγησε σε ομιλία την άλλη μέρα.

13
00:00:36,550 --> 00:00:39,420
Θα πάω πάνω από τα τέσσερα είδη του είδους.

14
00:00:39,420 --> 00:00:42,310
Θα πάμε πάνω τους αρκετά γρήγορα
δεδομένου ότι είναι αρκετά εντατική.

15
00:00:42,310 --> 00:00:45,710
Αλλά ξέρετε ότι όλες οι διαφάνειες και
πηγαίος κώδικας είναι πάντα σε απευθείας σύνδεση.

16
00:00:45,710 --> 00:00:50,810
Έτσι αισθάνονται ελεύθεροι, στο διάβασμα σας, για να
πάει πίσω και να ρίξετε μια ματιά σε αυτό.

17
00:00:50,810 --> 00:00:53,930
>> Θα περάσει
ασυμπτωτική σημειογραφία, η οποία

18
00:00:53,930 --> 00:00:55,944
είναι μόνο ένα φανταχτερό τρόπο
του λέγοντας «runtimes,"

19
00:00:55,944 --> 00:00:58,360
όπου έχουμε τη μεγάλη O, η οποία
David εξήγησε στην ομιλία.

20
00:00:58,360 --> 00:01:01,550
Και έχουμε επίσης Omega, η οποία
είναι το κατώτερο όριο χρόνου εκτέλεσης.

21
00:01:01,550 --> 00:01:06,450
Και θα μιλήσουμε λίγο περισσότερο
σε βάθος σχετικά με το πώς αυτές οι εργασίες.

22
00:01:06,450 --> 00:01:10,160
Και τέλος, θα πάμε πάνω από δυαδική αναζήτηση,
επειδή πολλοί από εσάς που έχετε ήδη

23
00:01:10,160 --> 00:01:15,190
Κοίταξα psets σας ίσως γνωρίζετε ότι
ότι είναι μια ερώτηση που είναι στο PSET σας.

24
00:01:15,190 --> 00:01:17,470
Έτσι όλοι θα είναι ευχαριστημένοι
ότι έχουμε καλύψει αυτό σήμερα.

25
00:01:17,470 --> 00:01:20,610
>> Και τέλος, ανά σας
τμήμα σχολίων, εγώ πραγματικά

26
00:01:20,610 --> 00:01:23,000
αριστερά περίπου 15 λεπτά σε
το τέλος να φύγουμε πάνω

27
00:01:23,000 --> 00:01:27,730
logistics της pset3, οποιεσδήποτε ερωτήσεις,
ίσως ένα κομμάτι της καθοδήγησης, αν θέλετε,

28
00:01:27,730 --> 00:01:28,990
πριν αρχίσουμε τον προγραμματισμό.

29
00:01:28,990 --> 00:01:30,890
Οπότε ας προσπαθήσουμε να ξεπεράσουμε
το υλικό αρκετά γρήγορα.

30
00:01:30,890 --> 00:01:33,880
Και τότε μπορούμε να περάσουν λίγο χρόνο
λαμβάνοντας περισσότερες ερωτήσεις για τον PSET.

31
00:01:33,880 --> 00:01:35,230
ΕΝΤΆΞΕΙ.

32
00:01:35,230 --> 00:01:39,570
>> Γρήγορα, έτσι ώστε μόλις λίγα
ανακοινώσεις πριν αρχίσουμε σήμερα.

33
00:01:39,570 --> 00:01:45,410
Πρώτον, καλώς να κάνει
μέσω δύο psets σας.

34
00:01:45,410 --> 00:01:49,432
Έριξα μια ματιά ναι, ας your--
πάρετε ένα χειροκρότημα για εκείνο το ένα.

35
00:01:49,432 --> 00:01:51,140
Στην πραγματικότητα, ήμουν πραγματικά,
πραγματικά εντυπωσιασμένος.

36
00:01:51,140 --> 00:01:55,800
Θα βαθμολογούνται την πρώτη το chipset για σας παιδιά
την περασμένη εβδομάδα και εσείς έκανε απίστευτο.

37
00:01:55,800 --> 00:01:58,290
>> Στυλ ήταν στο σημείο
εκτός από ορισμένες παρατηρήσεις.

38
00:01:58,290 --> 00:02:00,660
Βεβαιωθείτε ότι είστε πάντα
σχολιάζοντας τον κωδικό σας.

39
00:02:00,660 --> 00:02:03,040
Αλλά psets σας ήταν στο σημείο.

40
00:02:03,040 --> 00:02:05,549
Και να τον διατηρήσουμε.

41
00:02:05,549 --> 00:02:08,090
Και αυτό είναι καλό για το γκρέιντερ να
δείτε ότι εσείς βάζετε

42
00:02:08,090 --> 00:02:10,704
σε τόση προσπάθεια στο στυλ σας
και το σχεδιασμό σας τον κωδικό σας

43
00:02:10,704 --> 00:02:12,120
ότι θα θέλαμε να δούμε.

44
00:02:12,120 --> 00:02:16,450
Έτσι είμαι περνώντας κατά μήκος ευγνωμοσύνη μου
για το υπόλοιπο της ΤΒ.

45
00:02:16,450 --> 00:02:19,210
>> Ωστόσο, υπάρχουν
μερικές ερωτήσεις debrief

46
00:02:19,210 --> 00:02:22,010
Θέλω μόνο να πάει πέρα ​​από αυτό
θα κάνουν τη ζωή μου τόσο

47
00:02:22,010 --> 00:02:24,900
και πολλά από τα άλλα
ΕΥ «ζει λίγο πιο εύκολη.

48
00:02:24,900 --> 00:02:28,220
Πρώτον, έχω παρατηρήσει αυτό
παρελθόν week-- πόσοι από εσάς

49
00:02:28,220 --> 00:02:32,301
έχουν τρέξει σε check50
κωδικό σας, πριν να υποβάλετε;

50
00:02:32,301 --> 00:02:32,800
ΕΝΤΆΞΕΙ.

51
00:02:32,800 --> 00:02:36,690
Έτσι, ο καθένας θα πρέπει να κάνει check50,
because-- μια secret-- στην πραγματικότητα

52
00:02:36,690 --> 00:02:41,540
check50 τρέξει ως μέρος της ορθότητας μας
σενάρια για δοκιμή τον κωδικό σας.

53
00:02:41,540 --> 00:02:45,480
Έτσι, αν κωδικό σας αποτυγχάνει
check50, κατά πάσα πιθανότητα,

54
00:02:45,480 --> 00:02:47,570
πρόκειται πιθανώς να
αποτυγχάνουν έλεγχο μας.

55
00:02:47,570 --> 00:02:49,320
Μερικές φορές εσείς
έχει τις σωστές απαντήσεις.

56
00:02:49,320 --> 00:02:52,200
Όπως, στην άπληστοι, κάποια από
έχετε το δικαίωμα αριθμούς,

57
00:02:52,200 --> 00:02:53,960
μπορείτε απλά να εκτυπώσετε κάποια επιπλέον πράγματα.

58
00:02:53,960 --> 00:02:55,940
Και ότι επιπλέον πράγματα
αποτυγχάνει στην πραγματικότητα τον έλεγχο,

59
00:02:55,940 --> 00:02:58,440
επειδή ο υπολογιστής δεν
πραγματικά γνωρίζουν τι ψάχνει.

60
00:02:58,440 --> 00:03:00,981
Και γι 'αυτό θα τρέξει μόνο μέσα,
δείτε ότι η παραγωγή σας δεν

61
00:03:00,981 --> 00:03:03,810
ταιριάζει με αυτό που περιμένουμε την απάντηση
να είναι και το σήμα αυτό είναι λάθος.

62
00:03:03,810 --> 00:03:06,560
>> Και ξέρω ότι συνέβη στο
ορισμένες από τις υποθέσεις σας αυτή την εβδομάδα.

63
00:03:06,560 --> 00:03:09,870
Έτσι πήγα πίσω και με το χέρι
υποβαθμισμένα κωδικό του καθενός.

64
00:03:09,870 --> 00:03:12,780
Στο μέλλον όμως,
παρακαλώ, βεβαιωθείτε

65
00:03:12,780 --> 00:03:14,570
ότι τρέχετε
ελέγχει 50 σχετικά με τον κωδικό σας.

66
00:03:14,570 --> 00:03:17,970
Επειδή είναι το είδος του πόνου για το ΕΠ
να πρέπει να πάει πίσω και με το χέρι υποβαθμίσεως

67
00:03:17,970 --> 00:03:21,197
κάθε PSET για κάθε
ενιαία, λίγο έχασε παράδειγμα.

68
00:03:21,197 --> 00:03:22,530
Γι 'αυτό και δεν είχε απογειωθεί πόντους.

69
00:03:22,530 --> 00:03:25,210
Νομίζω ότι ίσως απογειώθηκε
μία ή δύο για το σχεδιασμό.

70
00:03:25,210 --> 00:03:27,710
Στο μέλλον όμως, αν
είστε παραλείποντας check50,

71
00:03:27,710 --> 00:03:31,330
Θα ληφθούν σημεία
off για την ορθότητά τους.

72
00:03:31,330 --> 00:03:35,020
>> Επιπλέον, είναι psets
λόγω Παρασκευή το μεσημέρι.

73
00:03:35,020 --> 00:03:38,990
Νομίζω ότι υπάρχει μια επτά λεπτά
όψιμη περίοδο χάριτος που σας δίνουμε.

74
00:03:38,990 --> 00:03:42,434
Ανά ώρα του Χάρβαρντ, από όπου και αν επιτρέπεται να
είναι επτά λεπτά καθυστέρηση για τα πάντα.

75
00:03:42,434 --> 00:03:44,350
Έτσι, εδώ στο Yale, θα
τηρούν και αυτό.

76
00:03:44,350 --> 00:03:47,910
Αλλά λίγο πολύ, στις 12:07,
αν το chipset σας δεν είναι,

77
00:03:47,910 --> 00:03:49,720
πρόκειται να σημανθεί ως αργά.

78
00:03:49,720 --> 00:03:53,160
Και έτσι ενώ σημειώνεται
τόσο αργά, η TA-- είμαι

79
00:03:53,160 --> 00:03:54,870
ακόμα πρόκειται να ταξινόμησης psets σας.

80
00:03:54,870 --> 00:03:56,760
Έτσι θα δείτε ακόμα ένα βαθμό φαίνεται.

81
00:03:56,760 --> 00:03:58,820
Ωστόσο, γνωρίζουμε ότι σε
το τέλος του εξαμήνου,

82
00:03:58,820 --> 00:04:02,270
Όλα τα τέλη psets θα είναι ακριβώς
μηδενίζεται αυτόματα από τον υπολογιστή.

83
00:04:02,270 --> 00:04:04,490
>> Το κάνουμε αυτό για δύο λόγους.

84
00:04:04,490 --> 00:04:09,220
Μία, μερικές φορές παίρνουμε
συγγνώμη, σαν δικαιολογίες του κοσμήτορα,

85
00:04:09,220 --> 00:04:10,762
αργότερα ότι δεν ξέρω ακόμα.

86
00:04:10,762 --> 00:04:13,761
Έτσι θέλουμε να διασφαλίσουμε ότι είμαστε ταξινόμησης
ό, τι ακριβώς σε περίπτωση, όπως, είμαι

87
00:04:13,761 --> 00:04:15,080
Λείπει δικαιολογία ενός κοσμήτορα.

88
00:04:15,080 --> 00:04:17,000
Και δεύτερον, να έχετε κατά
μυαλό, μπορείτε ακόμα

89
00:04:17,000 --> 00:04:19,370
Ρίξτε ένα PSET ότι
έχει πλήρη σημεία πεδίο.

90
00:04:19,370 --> 00:04:21,430
Και έτσι μας αρέσει να Βαθμός
όλα psets σας μόνο

91
00:04:21,430 --> 00:04:24,730
για να βεβαιωθείτε ότι το πεδίο εφαρμογής σας
εκεί και εσείς που προσπαθούν.

92
00:04:24,730 --> 00:04:29,150
Έτσι, ακόμα κι αν είναι αργά, θα εξακολουθούν
να πάρει πίστωση για τα σημεία πεδίο, νομίζω.

93
00:04:29,150 --> 00:04:33,730
>> Έτσι ηθικό δίδαγμα της ιστορίας είναι, να κάνει
βεβαιωθείτε ότι psets σας είναι στο χρόνο.

94
00:04:33,730 --> 00:04:38,350
Και αν δεν είναι μέσα σε χρόνο,
Γνωρίζουμε ότι δεν είναι μεγάλη.

95
00:04:38,350 --> 00:04:41,678
Ναι, πριν προχωρήσω, όμως κάποιοι έχουν
οποιεσδήποτε ερωτήσεις σχετικά με το chipset ανατροφοδότηση;

96
00:04:41,678 --> 00:04:42,178
Ναι.

97
00:04:42,178 --> 00:04:43,630
>> Κοινό: Μήπως λέμε
μπορεί να πέσει ένας από τους psets;

98
00:04:43,630 --> 00:04:44,296
>> ANDI PENG: Ναι.

99
00:04:44,296 --> 00:04:47,050
Έτσι υπάρχει psets εννέα συνολικά
κατά τη διάρκεια του εξαμήνου.

100
00:04:47,050 --> 00:04:50,610
Και αν έχετε πεδίου
points-- έτσι το πεδίο εφαρμογής είναι απλά,

101
00:04:50,610 --> 00:04:53,567
λίγο πολύ, είναι εσείς που προσπαθούν το
πρόβλημα, βάζετε στο χρόνο,

102
00:04:53,567 --> 00:04:56,150
σας δείχνουν ότι έχετε
αποδεικνύεται έχετε διαβάσει το spec.

103
00:04:56,150 --> 00:04:57,191
Αυτό είναι λίγο πολύ το πεδίο εφαρμογής.

104
00:04:57,191 --> 00:04:59,370
Και αν πληρούν
σημεία πεδίο, εμείς

105
00:04:59,370 --> 00:05:03,360
μπορεί να μειωθεί το χαμηλότερο
ένα από τα πλήρη έκταση.

106
00:05:03,360 --> 00:05:06,790
Έτσι ώστε να είναι σε σας πλεονέκτημα να
να συμπληρώσουν και να δοκιμάσετε κάθε PSET.

107
00:05:06,790 --> 00:05:10,320
>> Ακόμη upload-- αν κανένα από
τους εργασία, να φορτώσετε όλα αυτά.

108
00:05:10,320 --> 00:05:13,711
Και τότε θα ελπίζω να είναι σε θέση να
να σας δώσω μερικά από αυτά τα σημεία πίσω.

109
00:05:13,711 --> 00:05:14,210
Cool.

110
00:05:14,210 --> 00:05:16,780
Οποιεσδήποτε άλλες ερωτήσεις;

111
00:05:16,780 --> 00:05:17,840
Εξαιρετική.

112
00:05:17,840 --> 00:05:21,960
>> Δεύτερον, γραφείο hours-- μερικά
γρήγορες σημειώσεις σχετικά με τις ώρες γραφείου.

113
00:05:21,960 --> 00:05:24,300
Έτσι, πρώτα, να έρθει στις αρχές της εβδομάδας.

114
00:05:24,300 --> 00:05:26,909
Κανείς δεν είναι ποτέ σε
ώρες γραφείου Δευτέρα.

115
00:05:26,909 --> 00:05:28,700
Christabel ήρθε για να
ώρες γραφείου χθες το βράδυ.

116
00:05:28,700 --> 00:05:29,691
Ναι, Christabel.

117
00:05:29,691 --> 00:05:32,190
Και τι έχουμε στο γραφείο
ώρες χθες το βράδυ, Christabel;

118
00:05:32,190 --> 00:05:33,020
>> Κοινό: Είχαμε παγωτό.

119
00:05:33,020 --> 00:05:36,160
>> ANDI PENG: Έτσι, αυτό είναι σωστό, είχαμε
παγωτό σε ώρες γραφείου χθες το βράδυ.

120
00:05:36,160 --> 00:05:39,390
Αν και δεν μπορώ να σας υποσχεθώ ότι
θα έχουμε το παγωτό σε ώρες γραφείου

121
00:05:39,390 --> 00:05:43,230
κάθε εβδομάδα, αυτό που μπορώ να σας υποσχεθώ
είναι ότι θα υπάρξει μια σημαντική

122
00:05:43,230 --> 00:05:45,380
την καλύτερη αναλογία μαθητών ΤΑ.

123
00:05:45,380 --> 00:05:47,650
Όπως legit, είναι σαν τρία προς ένα.

124
00:05:47,650 --> 00:05:50,350
Ότι, σε αντίθεση με ότι
Πέμπτη, έχετε περίπου 150

125
00:05:50,350 --> 00:05:52,830
τόνισε πραγματικά τα παιδιά και δεν το παγωτό.

126
00:05:52,830 --> 00:05:55,360
Και δεν είναι μόνο παραγωγικοί για κανέναν.

127
00:05:55,360 --> 00:05:58,730
Έτσι ηθικό δίδαγμα της ιστορίας είναι, να έρθει νωρίς
σε ώρες γραφείου και καλά πράγματα

128
00:05:58,730 --> 00:06:00,310
θα συμβεί.

129
00:06:00,310 --> 00:06:02,110
>> Επίσης, έρχονται προετοιμασμένοι να κάνουν ερωτήσεις.

130
00:06:02,110 --> 00:06:03,200
Ξέρεις?

131
00:06:03,200 --> 00:06:05,420
Ανεξάρτητα από το τι βοηθούς, που
νομίζω, έχουν πει,

132
00:06:05,420 --> 00:06:10,710
έχουμε πάρει ένα ζευγάρι φοιτητών
που έρχονται σε την Πέμπτη στις, όπως, 10:50

133
00:06:10,710 --> 00:06:15,100
που δεν έχουν διαβάσει το spec
είναι σαν να με βοηθήσει, να με βοηθήσει.

134
00:06:15,100 --> 00:06:18,200
Δυστυχώς σε αυτό το σημείο, υπάρχει
Δεν μπορούμε να κάνουμε πολλά για να σας βοηθήσουμε.

135
00:06:18,200 --> 00:06:19,590
Επομένως, σας παρακαλώ να έρθει στις αρχές της εβδομάδας.

136
00:06:19,590 --> 00:06:22,040
Ελάτε νωρίς για ώρες γραφείου.

137
00:06:22,040 --> 00:06:23,350
Ελάτε προετοιμασμένοι να κάνετε ερωτήσεις.

138
00:06:23,350 --> 00:06:25,310
Βεβαιωθείτε ότι εσείς, ως
ένας φοιτητής, είναι όπου

139
00:06:25,310 --> 00:06:27,620
θα πρέπει να είναι έτσι ώστε η
ΤΒ μπορεί να σας καθοδηγήσει κατά μήκος,

140
00:06:27,620 --> 00:06:32,850
η οποία είναι ό, τι ώρες γραφείου
θα πρέπει να παραχωρηθεί για.

141
00:06:32,850 --> 00:06:37,380
>> Δεύτερον, οπότε ξέρω καθηγητές
ήθελα να μας εκπλήσσει με τις δοκιμές.

142
00:06:37,380 --> 00:06:39,439
Είχα ένα καθηγητή εκείνες
όπως, yo, από τον τρόπο,

143
00:06:39,439 --> 00:06:41,230
να θυμάστε ότι η ενδιάμεση
έχετε την ερχόμενη Δευτέρα.

144
00:06:41,230 --> 00:06:42,855
Ναι, δεν ήξερα γι 'αυτό ενδιάμεση.

145
00:06:42,855 --> 00:06:45,630
Έτσι, Πάω να είναι ότι το ΤΑ
ώστε να υπενθυμίζει σε όλους ότι κουίζ

146
00:06:45,630 --> 00:06:47,270
0-- γιατί, ξέρετε, είμαστε CS.

147
00:06:47,270 --> 00:06:50,730
Τώρα που έχουμε κάνει συστοιχίες, μπορείτε να πάρετε
Γι 'αυτό είναι κουίζ 0, δεν κουίζ 1, ε;

148
00:06:50,730 --> 00:06:51,320
ΕΝΤΆΞΕΙ.

149
00:06:51,320 --> 00:06:52,490
Ω, πήρα μερικά γέλια σε αυτό.

150
00:06:52,490 --> 00:06:53,120
ΕΝΤΆΞΕΙ.

151
00:06:53,120 --> 00:06:59,710
>> Έτσι κουίζ 0 θα είναι 14 Οκτωβρίου, αν και
είστε στο τμήμα από Δευτέρα έως Τετάρτη

152
00:06:59,710 --> 00:07:02,920
και της 15ης Οκτωβρίου, αν είστε σε
το τμήμα Τρίτη έως Πέμπτη.

153
00:07:02,920 --> 00:07:05,630
Αυτό δεν ισχύει για
Όσοι από εσάς στο Χάρβαρντ

154
00:07:05,630 --> 00:07:10,350
who-- Νομίζω ότι θα είναι όλοι
τη λήψη κουίζ σας στην 14η.

155
00:07:10,350 --> 00:07:13,560
>> Οπότε ναι, την επόμενη εβδομάδα, εάν
Ο David, σε διάλεξη, πηγαίνει,

156
00:07:13,560 --> 00:07:15,747
ναι, έτσι γι 'αυτό
κουίζ την επόμενη εβδομάδα, όλοι σας

157
00:07:15,747 --> 00:07:17,580
Δεν θα είναι σοκαρισμένος, διότι
ήρθες στο τμήμα

158
00:07:17,580 --> 00:07:19,664
και ξέρετε ότι σας
κουίζ 0 είναι σε δύο εβδομάδες.

159
00:07:19,664 --> 00:07:21,580
Και θα έχουμε κριτική
συνεδρίες και τα πάντα.

160
00:07:21,580 --> 00:07:26,360
Έτσι, υπάρχουν ανησυχίες σχετικά με
να φοβάται για αυτό.

161
00:07:26,360 --> 00:07:29,890
Οποιεσδήποτε ερωτήσεις before-- απορίες
σε όλα τα θέματα σχετικά με την υλικοτεχνική,

162
00:07:29,890 --> 00:07:32,591
ταξινόμησης, ώρες γραφείου, τμήματα;

163
00:07:32,591 --> 00:07:33,090
Ναι.

164
00:07:33,090 --> 00:07:35,100
>> Κοινό: Έτσι το κουίζ είναι
θα είναι κατά τη διάρκεια της διάλεξης;

165
00:07:35,100 --> 00:07:35,766
>> ANDI PENG: Ναι.

166
00:07:35,766 --> 00:07:39,460
Έτσι το κουίζ, νομίζω, είναι 60
λεπτά που διαθέτω σε αυτό το χρονοθυρίδα

167
00:07:39,460 --> 00:07:42,240
ότι θα πάρει μόνο
στην αίθουσα διαλέξεων.

168
00:07:42,240 --> 00:07:44,810
Έτσι, δεν χρειάζεται να έρθουν σε
σχετικά, όπως, ένα τυχαίο 19:00.

169
00:07:44,810 --> 00:07:46,140
Είναι όλα καλά.

170
00:07:46,140 --> 00:07:47,100
Ναι.

171
00:07:47,100 --> 00:07:50,060
Cool.

172
00:07:50,060 --> 00:07:50,840
>> Εντάξει.

173
00:07:50,840 --> 00:07:54,330
Έτσι θα πάμε να
παρουσιάσω μια ιδέα για να σας

174
00:07:54,330 --> 00:08:00,760
αυτή την εβδομάδα ότι ο David έχει ήδη το είδος
των έθιξε στην ομιλία την περασμένη εβδομάδα.

175
00:08:00,760 --> 00:08:02,010
Αυτό λέγεται GDB.

176
00:08:02,010 --> 00:08:05,570
Και πόσοι από εσάς, ενώ σε
η πορεία της γραφής psets σας,

177
00:08:05,570 --> 00:08:09,981
έχουν παρατηρήσει ένα μεγάλο κουμπί που λέει
"Debug" στην κορυφή του IDE σας;

178
00:08:09,981 --> 00:08:10,480
ΕΝΤΆΞΕΙ.

179
00:08:10,480 --> 00:08:13,770
Έτσι τώρα θα πάρει πραγματικά να ξεθάψει
το μυστήριο του τι πραγματικά αυτό το κουμπί

180
00:08:13,770 --> 00:08:14,270
κάνει.

181
00:08:14,270 --> 00:08:16,790
Και σας εγγυώμαι, είναι ένα
όμορφο, όμορφο πράγμα.

182
00:08:16,790 --> 00:08:20,740
>> Έτσι, μέχρι τώρα, νομίζω
έχει υπάρξει δύο πράγματα

183
00:08:20,740 --> 00:08:23,320
οι μαθητές έχουν συνήθως
κάνει όταν τον εντοπισμό σφαλμάτων psets.

184
00:08:23,320 --> 00:08:27,635
Ένα, είτε να προσθέσετε στο
printf () - έτσι ώστε κάθε λίγες γραμμές,

185
00:08:27,635 --> 00:08:29,760
προσθέτουν στην printf () -
Ω, τι είναι αυτή η μεταβλητή;

186
00:08:29,760 --> 00:08:32,551
Ω, τι είναι αυτή η μεταβλητή now--
και κατά κάποιο τρόπο δείτε την εξέλιξη

187
00:08:32,551 --> 00:08:33,940
του κωδικού σας, καθώς τρέχει.

188
00:08:33,940 --> 00:08:37,030
Ή η δεύτερη μέθοδος είναι να κάνει παιδιά
ότι το μόνο που γράφουν το όλο θέμα

189
00:08:37,030 --> 00:08:38,610
και στη συνέχεια να πάμε σαν αυτό στο τέλος.

190
00:08:38,610 --> 00:08:39,970
Ας ελπίσουμε ότι αυτό λειτουργεί.

191
00:08:39,970 --> 00:08:44,851
Σας εγγυώμαι, GDB είναι καλύτερη
τόσο από τις μεθόδους αυτές.

192
00:08:44,851 --> 00:08:45,350
Ναι.

193
00:08:45,350 --> 00:08:46,980
Έτσι, αυτό θα είναι ο καλύτερός σας φίλος.

194
00:08:46,980 --> 00:08:51,780
Επειδή είναι ένα όμορφο πράγμα
ότι οπτικά εμφανίζει δύο

195
00:08:51,780 --> 00:08:54,850
τι κωδικός σας κάνει
σε ένα συγκεκριμένο σημείο

196
00:08:54,850 --> 00:08:57,486
καθώς και αυτό που όλοι σας
Οι μεταβλητές που μεταφέρουν,

197
00:08:57,486 --> 00:08:59,610
όπως ποιες είναι οι αξίες τους,
σε εκείνο το συγκεκριμένο σημείο.

198
00:08:59,610 --> 00:09:02,670
Και με αυτόν τον τρόπο, μπορείτε πραγματικά
ορίσετε σημεία διακοπής στον κώδικά σας.

199
00:09:02,670 --> 00:09:04,350
Μπορείτε να τρέχει μέσα από γραμμή προς γραμμή.

200
00:09:04,350 --> 00:09:07,324
Και GDB θα πρέπει απλώς για
σας, εμφανίζεται για εσάς,

201
00:09:07,324 --> 00:09:09,490
ό, τι το σύνολο των μεταβλητών σας
Οι, τι κάνουν,

202
00:09:09,490 --> 00:09:10,656
τι συμβαίνει στον κώδικα.

203
00:09:10,656 --> 00:09:13,240
Και με τέτοιο τρόπο, είναι
τόσο πολύ ευκολότερο να δείτε

204
00:09:13,240 --> 00:09:17,120
τι συμβαίνει αντί της printf-σης
ή να γράψει κάτω τις δηλώσεις σας.

205
00:09:17,120 --> 00:09:19,160
>> Έτσι θα κάνουμε ένα παράδειγμα για αυτό αργότερα.

206
00:09:19,160 --> 00:09:20,660
Έτσι, αυτό φαίνεται λίγο αφηρημένη.

207
00:09:20,660 --> 00:09:23,490
Μην ανησυχείτε, θα κάνουμε παραδείγματα.

208
00:09:23,490 --> 00:09:29,170
Και έτσι, κατ 'ουσίαν, τα τρία μεγαλύτερα,
πλέον χρησιμοποιούμενες λειτουργίες που θα χρειαστείτε στο GDB

209
00:09:29,170 --> 00:09:32,500
είναι το επόμενο, βήμα πάνω,
Βήμα και σε κουμπιά.

210
00:09:32,500 --> 00:09:34,860
Πάω να το κεφάλι πάνω
εκεί, στην πραγματικότητα, αυτή τη στιγμή.

211
00:09:34,860 --> 00:09:40,930
>> Έτσι, μπορείτε να δείτε όλα τα παιδιά που
ή θα πρέπει να κάνετε ζουμ σε ένα κομμάτι;

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
Στο πίσω μέρος, μπορείτε να δείτε αυτό;

214
00:09:44,470 --> 00:09:45,730
Θα πρέπει να μεγεθύνετε;

215
00:09:45,730 --> 00:09:46,480
Λιγάκι μόνο?

216
00:09:46,480 --> 00:09:49,390
ΟΚ κομπλε.

217
00:09:49,390 --> 00:09:50,280
Εκεί πάμε.

218
00:09:50,280 --> 00:09:50,960
ΕΝΤΆΞΕΙ.

219
00:09:50,960 --> 00:09:57,000
>> Έτσι έχω εδώ, μου
εφαρμογή για άπληστοι.

220
00:09:57,000 --> 00:10:01,430
Και ενώ πολλοί από εσάς παιδιά έγραψαν
άπληστοι σε βρόχο, ενώ form-- ότι

221
00:10:01,430 --> 00:10:04,890
είναι ένας απόλυτα αποδεκτός τρόπος για να κάνουμε
it-- έναν άλλο τρόπο για να γίνει αυτό είναι να απλά

222
00:10:04,890 --> 00:10:06,280
χωρίζουν το modulo.

223
00:10:06,280 --> 00:10:09,290
Επειδή τότε μπορείτε να έχετε σας
αξία και στη συνέχεια να έχουν υπόλοιπο σας.

224
00:10:09,290 --> 00:10:11,150
Και τότε μπορείτε απλά
προσθέστε όλα μαζί.

225
00:10:11,150 --> 00:10:13,390
Μήπως η λογική του τι κάνω
εδώ έχουν νόημα για όλους,

226
00:10:13,390 --> 00:10:14,117
πριν ξεκινήσουμε;

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
Περίπου?

229
00:10:17,980 --> 00:10:18,710
Cool.

230
00:10:18,710 --> 00:10:19,210
Εξαιρετική.

231
00:10:19,210 --> 00:10:21,290
Είναι μια αρκετά σέξι κομμάτι
του κώδικα, θα έλεγα.

232
00:10:21,290 --> 00:10:23,502
Όπως είπα, ο David, σε
διάλεξη, μετά από λίγο,

233
00:10:23,502 --> 00:10:25,960
θα αρχίσετε να βλέπετε όλες κωδικός
ως κάτι που είναι όμορφο.

234
00:10:25,960 --> 00:10:29,950
Και μερικές φορές όταν βλέπεις όμορφη
κώδικα, είναι ένα τέτοιο θαυμάσιο συναίσθημα.

235
00:10:29,950 --> 00:10:35,410
>> Έτσι όμως, ενώ αυτός ο κώδικας είναι πολύ
όμορφη, δεν λειτουργεί σωστά.

236
00:10:35,410 --> 00:10:37,750
Οπότε ας τρέξει check50 σε αυτό.

237
00:10:37,750 --> 00:10:39,440
Ελέγξτε 20-- 50 oop.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2;

240
00:10:43,720 --> 00:10:44,990
Είναι ότι pset2;

241
00:10:44,990 --> 00:10:46,870
Ναι.

242
00:10:46,870 --> 00:10:47,520
Ω, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
ΕΝΤΆΞΕΙ.

245
00:10:52,890 --> 00:10:53,900
Γι 'αυτό και τρέχει check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> Και όπως εσείς μπορείτε να δείτε εδώ,
είναι αδυναμία μερικές περιπτώσεις.

248
00:11:07,170 --> 00:11:10,165
Και για κάποιους από εσάς, στην
Φυσικά για να γίνει το πρόβλημα σετ,

249
00:11:10,165 --> 00:11:11,110
είστε όπως, αχ, γιατί δεν είναι αυτό που εργάζονται.

250
00:11:11,110 --> 00:11:13,318
Γιατί είναι αυτό που εργάζονται για ορισμένους
τιμές, αλλά όχι για τους άλλους;

251
00:11:13,318 --> 00:11:17,760
Λοιπόν, GDB θα βοηθήσει το σχήμα σας
γιατί αυτές οι είσοδοι δεν εργάζονταν.

252
00:11:17,760 --> 00:11:18,320
>> ΕΝΤΆΞΕΙ.

253
00:11:18,320 --> 00:11:21,640
Ας δούμε λοιπόν, ένα από τα
ελέγχους που απέτυχε σε check50

254
00:11:21,640 --> 00:11:24,920
ήταν η τιμή εισόδου των 0,41.

255
00:11:24,920 --> 00:11:27,830
Έτσι, η σωστή απάντηση που
θα πρέπει να πάρει είναι 4.

256
00:11:27,830 --> 00:11:33,090
Αλλά αντ 'αυτού τι είμαι εκτύπωση
είναι η 3-Ν, η οποία είναι εσφαλμένη.

257
00:11:33,090 --> 00:11:36,190
Έτσι, ας τρέξει αυτό με το χέρι, απλά
βεβαιωθείτε ότι check50 λειτουργεί.

258
00:11:36,190 --> 00:11:36,940
Ας κάνουμε ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Ωχ, έχω να κάνω άπληστοι.

261
00:11:43,340 --> 00:11:43,840
Εκεί πάμε.

262
00:11:43,840 --> 00:11:44,381
Τώρα ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> Πόσο οφείλεται;

265
00:11:47,670 --> 00:11:49,550
Ας κάνουμε 0,41.

266
00:11:49,550 --> 00:11:52,590
Και Ναι, βλέπουμε εδώ
ότι έχει την έξοδο 3

267
00:11:52,590 --> 00:11:55,160
όταν η σωστή απάντηση,
Στην πραγματικότητα, θα πρέπει να είναι 4.

268
00:11:55,160 --> 00:12:01,460
Ας εισάγετε GDB και να δούμε πώς μπορούμε
μπορούν να πάνε για τον καθορισμό αυτό το πρόβλημα.

269
00:12:01,460 --> 00:12:03,992
>> Έτσι, το πρώτο βήμα
debugging πάντα τον κωδικό σας

270
00:12:03,992 --> 00:12:05,950
είναι να ορίσετε ένα σημείο διακοπής,
ή ένα σημείο στο οποίο θα

271
00:12:05,950 --> 00:12:09,079
θέλουν τον υπολογιστή ή το
εντοπισμού σφαλμάτων για να αρχίσει κανείς να κοιτάζει.

272
00:12:09,079 --> 00:12:11,120
Έτσι, αν δεν το κάνετε πραγματικά
ξέρετε τι είναι το πρόβλημά σας,

273
00:12:11,120 --> 00:12:14,670
Συνήθως, η τυπική πράγμα που θέλουμε να
κάνετε είναι να ορίσετε breakpoint μας στο κεντρικό.

274
00:12:14,670 --> 00:12:18,520
Έτσι, αν εσείς μπορείτε να δείτε αυτό το
κόκκινο κουμπί εκεί,

275
00:12:18,520 --> 00:12:22,860
Ναι, αυτό ήταν με μια ρύθμιση
σημείου τύπου για την κύρια λειτουργία.

276
00:12:22,860 --> 00:12:24,130
Κάνω κλικ αυτό.

277
00:12:24,130 --> 00:12:26,130
>> Και τότε μπορώ να πάω μέχρι το κουμπί Debug μου.

278
00:12:26,130 --> 00:12:27,036
Χτύπησα αυτό το κουμπί.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Επιτρέψτε μου να μεγεθύνετε αν μπορώ.

281
00:12:36,555 --> 00:12:38,020
Εκεί πάμε.

282
00:12:38,020 --> 00:12:40,730
Έτσι έχουμε, εδώ, ένα πάνελ στα δεξιά.

283
00:12:40,730 --> 00:12:43,680
Λυπάμαι, παιδιά στο πίσω μέρος, που
Δεν μπορεί πραγματικά να δει πολύ καλά.

284
00:12:43,680 --> 00:12:49,090
Αλλά ουσιαστικά, όλα
Αυτό το δικαίωμα πάνελ κάνει

285
00:12:49,090 --> 00:12:53,130
παρακολουθεί με ιδιαίτερη προσοχή τόσο την επισημαίνονται
γραμμή, η οποία είναι η γραμμή του κώδικα

286
00:12:53,130 --> 00:12:56,640
ότι ο υπολογιστής λειτουργεί αυτή τη στιγμή,
καθώς και το σύνολο των μεταβλητών σας

287
00:12:56,640 --> 00:12:57,600
εδώ κάτω.

288
00:12:57,600 --> 00:13:00,487
>> Έτσι έχετε σεντ, κέρματα, n,
το σύνολο των δηλωθέντων με διαφορετικά πράγματα

289
00:13:00,487 --> 00:13:01,070
σε αυτό το σημείο.

290
00:13:01,070 --> 00:13:04,850
Μην ανησυχείτε, γιατί δεν έχουμε πραγματικότητα
τους προετοιμαστεί για τυχόν μεταβλητές ακόμα.

291
00:13:04,850 --> 00:13:07,200
Έτσι, στον υπολογιστή σας, σας
υπολογιστή απλά να δει,

292
00:13:07,200 --> 00:13:14,376
OH, 32767 ήταν η τελευταία φορά που χρησιμοποιήθηκε λειτουργία
του εν λόγω χώρου μνήμης στον υπολογιστή μου.

293
00:13:14,376 --> 00:13:16,000
Και έτσι αυτό είναι όπου είναι σήμερα σεντ.

294
00:13:16,000 --> 00:13:19,360
Αλλά όχι ότι μόλις την εκτέλεση του κώδικα,
θα πρέπει να γίνει προετοιμαστεί.

295
00:13:19,360 --> 00:13:24,110
>> Ας πάμε μέσα, σύμφωνα με την
γραμμή, τι συμβαίνει εδώ.

296
00:13:24,110 --> 00:13:25,350
ΕΝΤΆΞΕΙ.

297
00:13:25,350 --> 00:13:29,400
Έτσι, εδώ είναι οι τρεις
κουμπιά που μόλις εξήγησα.

298
00:13:29,400 --> 00:13:34,090
Έχετε το παιχνίδι, ή τη λειτουργία Run,
κουμπί, έχετε το βήμα πάνω από το κουμπί,

299
00:13:34,090 --> 00:13:36,600
και έχετε επίσης το βήμα σε κουμπί.

300
00:13:36,600 --> 00:13:41,260
Και ουσιαστικά, και οι τρεις
τους μόλις περάσουν τον κωδικό σας

301
00:13:41,260 --> 00:13:42,690
και να κάνει διαφορετικά πράγματα.

302
00:13:42,690 --> 00:13:45,680
>> Έτσι, συνήθως, όταν τον εντοπισμό σφαλμάτων,
δεν θέλουμε να χτυπήσει απλά παίζουν,

303
00:13:45,680 --> 00:13:47,930
Καθώς το παιχνίδι θα τρέξει μόνο
κωδικό σας προς το τέλος της.

304
00:13:47,930 --> 00:13:49,070
Και τότε δεν θα είναι πράγματι
ξέρετε τι το πρόβλημά σας

305
00:13:49,070 --> 00:13:51,432
είναι, εκτός εάν ορίσετε πολλαπλά σημεία διακοπής.

306
00:13:51,432 --> 00:13:53,890
Εάν ορίσετε πολλαπλά σημεία διακοπής,
Θα μόνο αυτόματα

307
00:13:53,890 --> 00:13:56,030
τρέχει από το ένα σημείο διακοπής,
στο επόμενο, στο επόμενο.

308
00:13:56,030 --> 00:13:58,030
Αλλά σε αυτή την περίπτωση έχουμε
ακριβώς αυτό, διότι εμείς

309
00:13:58,030 --> 00:13:59,970
Θέλετε να εργαστείτε με τον τρόπο μας
από πάνω προς τα κάτω προς τα κάτω.

310
00:13:59,970 --> 00:14:04,830
Έτσι θα πάμε να αγνοήσει αυτό το κουμπί
τώρα για τους σκοπούς του παρόντος προγράμματος.

311
00:14:04,830 --> 00:14:08,230
>> Έτσι το βήμα πάνω από τη λειτουργία μόνο
βήματα πάνω από κάθε γραμμή

312
00:14:08,230 --> 00:14:11,510
και σας λέει τι
ο υπολογιστής κάνει.

313
00:14:11,510 --> 00:14:14,630
Το Βήμα σε λειτουργία πηγαίνει
στην πραγματική λειτουργία

314
00:14:14,630 --> 00:14:16,000
αυτό είναι για σας γραμμή κώδικα.

315
00:14:16,000 --> 00:14:19,070
Έτσι, για παράδειγμα, όπως printf (),
ότι είναι μια λειτουργία, σωστά;

316
00:14:19,070 --> 00:14:21,980
Αν ήθελα να σωματικά βήμα
σε με την printf (),

317
00:14:21,980 --> 00:14:25,610
Θα ήθελα πραγματικά να πάμε στο κομμάτι της
κώδικας όπου printf () γράφτηκε και δείτε

318
00:14:25,610 --> 00:14:26,730
τι συμβαίνει εκεί.

319
00:14:26,730 --> 00:14:29,924
>> Αλλά συνήθως, υποθέτουμε ότι
ο κωδικός που σας δίνουμε λειτουργεί.

320
00:14:29,924 --> 00:14:31,340
Έχουμε αναλάβει την printf () λειτουργεί.

321
00:14:31,340 --> 00:14:33,170
Υποθέτουμε ότι GetInt () λειτουργεί.

322
00:14:33,170 --> 00:14:35,170
Έτσι δεν υπάρχει καμία ανάγκη να
βήμα σε αυτές τις λειτουργίες.

323
00:14:35,170 --> 00:14:37,170
Αλλά αν υπάρχει λειτουργίες
ότι εσείς οι ίδιοι γράφουν

324
00:14:37,170 --> 00:14:39,060
ότι θέλετε να ελέγξετε
τι συμβαίνει,

325
00:14:39,060 --> 00:14:41,200
θα θέλατε να εντείνουν
σε αυτή τη συνάρτηση.

326
00:14:41,200 --> 00:14:43,940
>> Έτσι τώρα είμαστε ακριβώς πρόκειται
στο βήμα πάνω από αυτό το κομμάτι του κώδικα.

327
00:14:43,940 --> 00:14:44,485
Ας δούμε λοιπόν.

328
00:14:44,485 --> 00:14:46,547
Ω, εκτύπωση, "Αχ hai, πώς
πολλές αλλαγές οφείλεται; "

329
00:14:46,547 --> 00:14:47,130
Εμείς δεν με νοιάζει.

330
00:14:47,130 --> 00:14:49,830
Γνωρίζουμε ότι λειτουργεί,
γι 'αυτό το βήμα πάνω του.

331
00:14:49,830 --> 00:14:53,290
>> Έτσι, n, η οποία είναι float μας ότι
έχουμε initialized-- ή declared--

332
00:14:53,290 --> 00:14:56,810
στην κορυφή, είμαστε τώρα
ισούται ότι για να GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Ας βήμα πέρα ​​από αυτό.

334
00:14:57,810 --> 00:14:59,580
Και βλέπουμε κατά τη
κάτω εδώ, το πρόγραμμα

335
00:14:59,580 --> 00:15:03,360
είναι να μου ζητά να εισάγετε μια τιμή.

336
00:15:03,360 --> 00:15:08,580
Ας είσοδο την τιμή που θέλουμε
να δοκιμάσει εδώ, η οποία είναι 0,41.

337
00:15:08,580 --> 00:15:09,160
Εξαιρετική.

338
00:15:09,160 --> 00:15:12,780
>> Έτσι τώρα n-- κάνετε εσείς δείτε
εδώ, στο bottom-- είναι

339
00:15:12,780 --> 00:15:15,140
stored-- γιατί
Δεν έχουν στρογγυλεμένες ακόμα, είναι

340
00:15:15,140 --> 00:15:19,540
αποθηκεύονται σε αυτό σαν γίγαντας
float που είναι 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
η οποία είναι αρκετά κοντά για να μας
σκοπούς, αυτή τη στιγμή, στο 0,41.

342
00:15:22,550 --> 00:15:26,090
Και τότε θα δούμε αργότερα, όπως
να συνεχίσει την ενίσχυση πάνω από το πρόγραμμα,

343
00:15:26,090 --> 00:15:29,850
μετά εδώ, n έχει γίνει
στρογγυλεμένες και σεντς έχει γίνει 41.

344
00:15:29,850 --> 00:15:30,350
Εξαιρετική.

345
00:15:30,350 --> 00:15:32,230
Έτσι, γνωρίζουμε ότι στρογγυλοποίηση εργασίας μας.

346
00:15:32,230 --> 00:15:34,700
Γνωρίζουμε ότι έχουμε το
σωστό αριθμό των λεπτών,

347
00:15:34,700 --> 00:15:36,990
έτσι ξέρουμε ότι αυτό είναι
δεν είναι πραγματικά το πρόβλημα.

348
00:15:36,990 --> 00:15:40,050
>> Έτσι, συνεχίζουμε την ενίσχυση
σχετικά σε αυτό το πρόγραμμα.

349
00:15:40,050 --> 00:15:40,900
Εμείς πάμε εδώ.

350
00:15:40,900 --> 00:15:46,139
Και έτσι μετά από αυτή τη γραμμή του κώδικα, που
Πρέπει να ξέρετε πόσα τρίμηνα έχουμε.

351
00:15:46,139 --> 00:15:46,680
Εμείς βήμα πάνω.

352
00:15:46,680 --> 00:15:52,040
Και βλέπετε το κάνουμε, στην πραγματικότητα, έχουν ένα
τρίμηνο επειδή έχουμε αφαιρούνται 25

353
00:15:52,040 --> 00:15:53,790
από την αρχική μας τιμή των 41.

354
00:15:53,790 --> 00:15:55,890
Και έχουμε 16 σεντ το αριστερό για μας.

355
00:15:55,890 --> 00:15:58,830
>> Μήπως όλοι καταλαβαίνουν πώς
Το πρόγραμμα ενισχύει μέσω

356
00:15:58,830 --> 00:16:02,980
και γιατί σεντ έχει γίνει πλέον 16
και γιατί, τώρα, έχει γίνει κέρματα 1;

357
00:16:02,980 --> 00:16:04,610
Είναι όλοι μετά από αυτή τη λογική;

358
00:16:04,610 --> 00:16:05,110
Cool.

359
00:16:05,110 --> 00:16:07,860
Έτσι, από το σημείο αυτό, η
εργασίας προγράμματος, έτσι δεν είναι;

360
00:16:07,860 --> 00:16:09,797
Γνωρίζουμε ότι κάνει ακριβώς
ό, τι θέλουμε να.

361
00:16:09,797 --> 00:16:11,880
Και δεν το κάναμε πραγματικότητα
πρέπει να εκτυπώσετε, ω, τι

362
00:16:11,880 --> 00:16:14,430
Είναι σεντ σε αυτό το σημείο,
τι είναι κέρματα σε αυτό το σημείο.

363
00:16:14,430 --> 00:16:17,170
>> Συνεχίζουμε να περάσει από το πρόγραμμα.

364
00:16:17,170 --> 00:16:18,100
Βήμα πάνω.

365
00:16:18,100 --> 00:16:18,620
Cool.

366
00:16:18,620 --> 00:16:19,700
Εμείς πάμε πάνω δεκάρες.

367
00:16:19,700 --> 00:16:20,200
Εξαιρετική.

368
00:16:20,200 --> 00:16:22,367
Βλέπουμε ότι έχει ληφθεί
μακριά $ 0.10 για μια δεκάρα.

369
00:16:22,367 --> 00:16:23,450
Και τώρα έχουμε δύο νομίσματα.

370
00:16:23,450 --> 00:16:25,260
Αυτό είναι σωστό.

371
00:16:25,260 --> 00:16:31,555
>> Εμείς πάμε πάνω από τις πένες και βλέπουμε
ότι έχουμε απομείνει σεντ.

372
00:16:31,555 --> 00:16:32,680
Χμμ, αυτό είναι περίεργο.

373
00:16:32,680 --> 00:16:37,540
Μέχρι εδώ στο πρόγραμμα, θα έπρεπε
να αφαιρείται πένες μου.

374
00:16:37,540 --> 00:16:39,400
Ίσως εγώ απλά δεν ήταν
κάνει αυτό το δικαίωμα γραμμή.

375
00:16:39,400 --> 00:16:42,190
Και δυστυχώς, μπορείτε να δείτε
εδώ, γιατί γνωρίζουμε

376
00:16:42,190 --> 00:16:44,360
ότι πατάμε
μέσω των γραμμών 32 και 33,

377
00:16:44,360 --> 00:16:50,560
αυτό είναι όπου το πρόγραμμά μας
εσφαλμένα είχε τρέξει μεταβλητές.

378
00:16:50,560 --> 00:16:55,136
Έτσι, μπορούμε να εξετάσουμε και να δούμε, OH,
Είμαι εδώ για την αφαίρεση σεντ,

379
00:16:55,136 --> 00:16:57,010
αλλά δεν είμαι στην πραγματικότητα
προσθέτοντας αξία νομίσματος μου.

380
00:16:57,010 --> 00:16:57,860
Είμαι προσθέτοντας σεντ.

381
00:16:57,860 --> 00:17:00,234
Και δεν θέλω να προσθέσετε
σεντ, θέλω να προσθέσω τα κέρματα.

382
00:17:00,234 --> 00:17:05,420
Έτσι, αν θέλουμε να αλλάξει αυτό με τα κέρματα,
έχουμε ένα πρόγραμμα εργασίας.

383
00:17:05,420 --> 00:17:06,730
Μπορώ να τρέξω check50.

384
00:17:06,730 --> 00:17:11,063
Μπορείτε απλά να βγείτε έξω από GDB δικαιώματος
εδώ και στη συνέχεια εκτελέστε ξανά check50.

385
00:17:11,063 --> 00:17:11,938
Θα μπορούσα να κάνω ακριβώς αυτό.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Πρέπει να κάνω άπληστοι.

388
00:17:18,480 --> 00:17:19,940
0.41.

389
00:17:19,940 --> 00:17:22,819
Και εδώ, είναι εκτύπωση
έξω η σωστή απάντηση.

390
00:17:22,819 --> 00:17:26,569
>> Έτσι, όπως μπορείτε να δείτε παιδιά, GDB
είναι ένα πραγματικά ισχυρό εργαλείο

391
00:17:26,569 --> 00:17:29,940
όταν έχουμε τόσο πολύ κώδικα
συμβαίνει και τόσες πολλές μεταβλητές

392
00:17:29,940 --> 00:17:32,510
ότι είναι δύσκολο για εμάς, ως
έναν άνθρωπο, για να παρακολουθείτε.

393
00:17:32,510 --> 00:17:35,360
Ο υπολογιστής, στον GDB
εντοπισμού σφαλμάτων, έχει τη δυνατότητα

394
00:17:35,360 --> 00:17:37,020
για να παρακολουθείτε τα πάντα.

395
00:17:37,020 --> 00:17:40,480
Ξέρω, σε Visionaire, εσείς πιθανώς
μπορεί να χτυπήσει μερικά ελαττώματα τμηματοποίησης

396
00:17:40,480 --> 00:17:43,150
γιατί έτρεχαν
έξω από τα όρια του πίνακα σας.

397
00:17:43,150 --> 00:17:46,510
Στο παράδειγμα του Καίσαρα, που είναι
ακριβώς ό, τι έχω εφαρμοστεί εδώ.

398
00:17:46,510 --> 00:17:50,060
>> Γι 'αυτό και ξέχασε να ελέγξει για
τι θα συμβεί αν

399
00:17:50,060 --> 00:17:52,510
δεν είχε δύο επιχειρήματα της γραμμής εντολών.

400
00:17:52,510 --> 00:17:53,880
Απλά δεν έθεσε στην εν λόγω ελέγχου.

401
00:17:53,880 --> 00:17:57,380
Και έτσι αν τρέχω Debug-- έθεσα
breakpoint μου εκεί.

402
00:17:57,380 --> 00:17:58,055
Τρέχω εντοπισμού σφαλμάτων.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> ΕΝΤΆΞΕΙ.

405
00:18:16,550 --> 00:18:17,050
Ναι.

406
00:18:17,050 --> 00:18:20,350
Έτσι, στην πραγματικότητα, GDB υποτίθεται
Μου είπαν εκεί

407
00:18:20,350 --> 00:18:22,300
Ήταν ένα σφάλμα κατάτμησης εκεί.

408
00:18:22,300 --> 00:18:24,883
Δεν ξέρω τι συνέβαινε
εκεί, αλλά όταν έτρεξε,

409
00:18:24,883 --> 00:18:25,590
δούλευε.

410
00:18:25,590 --> 00:18:29,410
Όταν εκτελείτε γραμμές κώδικα μέσα και
GDB θα μπορούσε να εγκαταλείψει ξαφνικά πάνω σου,

411
00:18:29,410 --> 00:18:31,540
ανεβαίνουν και να δούμε ποιο είναι το κόκκινο είναι λάθος.

412
00:18:31,540 --> 00:18:33,930
Θα σας πω, hey,
είχε ένα σφάλμα κατάτμησης,

413
00:18:33,930 --> 00:18:38,550
πράγμα που σημαίνει ότι επιχείρησε να αποκτήσει πρόσβαση
χώρου σε έναν πίνακα που δεν υπήρχε.

414
00:18:38,550 --> 00:18:39,050
Ναι.

415
00:18:39,050 --> 00:18:43,280
>> Έτσι, στο επόμενο πρόβλημα
που αυτή την εβδομάδα, εσείς

416
00:18:43,280 --> 00:18:45,600
θα έχουν κατά πάσα πιθανότητα πολύ
μεταβλητές που επιπλέουν γύρω.

417
00:18:45,600 --> 00:18:48,560
Δεν πρόκειται να είναι σίγουροι για το τι
σημαίνουν όλα αυτά σε ένα ορισμένο σημείο.

418
00:18:48,560 --> 00:18:53,560
Έτσι, GDB θα σας βοηθήσει πραγματικά στον υπολογισμό
τι είναι όλα ισούται

419
00:18:53,560 --> 00:18:55,940
και να είναι σε θέση να δουν ότι οπτικά.

420
00:18:55,940 --> 00:19:01,995
Είναι κανείς σύγχυση σχετικά με το πώς
κάποια από τα οποία δούλευε;

421
00:19:01,995 --> 00:19:02,495
Cool.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
Εντάξει.

424
00:19:10,620 --> 00:19:14,260
Έτσι, μετά από αυτό, είμαστε
πρόκειται να βουτήξει δεξιά

425
00:19:14,260 --> 00:19:17,562
σε τέσσερα διαφορετικά είναι
τύπους των ειδών για αυτή την εβδομάδα.

426
00:19:17,562 --> 00:19:19,520
Πόσοι από εσάς, πρώτο
απ 'όλα, πριν αρχίσουμε,

427
00:19:19,520 --> 00:19:23,020
έχουν διαβάσει ολόκληρο το spec για pset3;

428
00:19:23,020 --> 00:19:23,824
ΕΝΤΆΞΕΙ.

429
00:19:23,824 --> 00:19:24,740
Είμαι περήφανος για σας παιδιά.

430
00:19:24,740 --> 00:19:29,110
Αυτό είναι σαν το ήμισυ της κατηγορίας, το οποίο
είναι πολύ περισσότερο από ό, τι την τελευταία φορά.

431
00:19:29,110 --> 00:19:33,950
>> Έτσι, αυτό είναι σπουδαίο, γιατί όταν
μιλάμε για το περιεχόμενο

432
00:19:33,950 --> 00:19:36,170
σε lecture-- ή συγγνώμη,
σε section-- Μου αρέσει

433
00:19:36,170 --> 00:19:38,210
να αφορούν πολλά γι 'αυτό
πίσω σε αυτό το chipset είναι η

434
00:19:38,210 --> 00:19:40,210
και πώς θέλετε να
εφαρμόσουν ότι το chipset σας.

435
00:19:40,210 --> 00:19:42,400
Έτσι, αν έρθει με
διαβάστε το spec, αυτό θα

436
00:19:42,400 --> 00:19:45,510
είναι πολύ πιο εύκολο για σας να καταλάβετε
τι πράγμα μιλάω όταν λέω,

437
00:19:45,510 --> 00:19:48,720
oh hey, αυτό θα μπορούσε να είναι μια πραγματικά
καλό μέρος για να εφαρμόσει αυτό το είδος.

438
00:19:48,720 --> 00:19:52,870
Έτσι, όσοι από εσάς έχουν διαβάσει το
spec γνωρίζουμε ότι, ως μέρος της PSET σας,

439
00:19:52,870 --> 00:19:54,900
θα πάμε να πρέπει να
Αποστολή τύπο του είδους.

440
00:19:54,900 --> 00:19:58,670
Έτσι, αυτό μπορεί να είναι πολύ χρήσιμη
για πολλούς από εσάς σήμερα.

441
00:19:58,670 --> 00:20:01,760
>> Έτσι θα ξεκινήσετε με,
κατ 'ουσίαν, το πιο απλό τύπο

442
00:20:01,760 --> 00:20:04,580
του είδους, το είδος επιλογής.

443
00:20:04,580 --> 00:20:06,800
Το τυπικό αλγόριθμος για
πώς είχαμε πάει για αυτό

444
00:20:06,800 --> 00:20:10,460
is-- David πέρασε από όλα αυτά σε
διάλεξη, γι 'αυτό θα προχωρήσουμε γρήγορα κατά μήκος

445
00:20:10,460 --> 00:20:13,900
here-- είναι κατ 'ουσίαν, μπορείτε
έχουν έναν πίνακα τιμών.

446
00:20:13,900 --> 00:20:17,170
Και τότε θα βρείτε το
μικρότερη τιμή χωρίς διαλογή

447
00:20:17,170 --> 00:20:20,200
και μπορείτε να ανταλλάσσετε με αυτή την τιμή
η πρώτη αδιαχώριστα αξία.

448
00:20:20,200 --> 00:20:22,700
Και τότε απλά να το επαναλαμβάνω,
με το υπόλοιπο της λίστας σας.

449
00:20:22,700 --> 00:20:25,740
>> Και εδώ είναι μια οπτική εξήγηση
πώς αυτό θα μπορούσε να λειτουργήσει.

450
00:20:25,740 --> 00:20:30,460
Έτσι, για παράδειγμα, εάν επρόκειτο να ξεκινήσει
με μια σειρά από πέντε στοιχεία, ο δείκτης

451
00:20:30,460 --> 00:20:35,910
0 έως 4, με 3, 5, 2, 6, και 4 αξίες
τοποθετείται στο array-- έτσι τώρα,

452
00:20:35,910 --> 00:20:38,530
είμαστε ακριβώς πρόκειται να υποθέσουμε
ότι είναι όλοι αδιαχώριστα

453
00:20:38,530 --> 00:20:41,130
γιατί δεν έχουμε δοκιμαστεί διαφορετικά.

454
00:20:41,130 --> 00:20:44,130
>> Πώς, λοιπόν, ένα είδος επιλογής θα
το έργο είναι ότι ήθελα πρώτα

455
00:20:44,130 --> 00:20:46,800
τρέχει μέσα από το σύνολο
της συστοιχίας χωρίς διαλογή.

456
00:20:46,800 --> 00:20:49,120
Θα ξεχωρίσω τη μικρότερη τιμή.

457
00:20:49,120 --> 00:20:51,750
Στην περίπτωση αυτή, 3, δεξιά
τώρα, είναι το μικρότερο.

458
00:20:51,750 --> 00:20:52,680
Παίρνει έως 5.

459
00:20:52,680 --> 00:20:55,620
Όχι, 5 δεν είναι μεγαλύτερη than--
ή συγγνώμη, δεν είναι μικρότερη than-- 3.

460
00:20:55,620 --> 00:20:57,779
Έτσι, η ελάχιστη τιμή είναι ακόμα 3.

461
00:20:57,779 --> 00:20:58,695
Και τότε θα έχετε να 2.

462
00:20:58,695 --> 00:21:00,990
Ο υπολογιστής βλέπει, ω, 2 είναι λιγότερο από 3.

463
00:21:00,990 --> 00:21:02,750
2 θα πρέπει τώρα να είναι η ελάχιστη τιμή.

464
00:21:02,750 --> 00:21:06,630
Και έτσι 2 swaps με την εν λόγω πρώτη τιμή.

465
00:21:06,630 --> 00:21:10,702
>> Έτσι, μετά από ένα πέρασμα, θα δούμε πράγματι
ότι η 2 και το 3 είναι αντίστροφα.

466
00:21:10,702 --> 00:21:13,910
Και είμαστε ακριβώς πρόκειται να συνεχίσει να κάνει
αυτό πάλι με το υπόλοιπο της διάταξης.

467
00:21:13,910 --> 00:21:17,660
Έτσι θα πάμε απλά να τρέχει μέσα
τα τελευταία τέσσερα ευρετήρια της συστοιχίας.

468
00:21:17,660 --> 00:21:20,670
Θα δούμε ότι είναι 3
η επόμενη ελάχιστη τιμή.

469
00:21:20,670 --> 00:21:23,240
Έτσι θα πάμε να ανταλλάξουν ότι με 4.

470
00:21:23,240 --> 00:21:26,900
Και τότε είμαστε ακριβώς πρόκειται να κρατήσει
διατρέχει μέχρι, τελικά, θα

471
00:21:26,900 --> 00:21:33,730
φτάσουμε σε ένα ταξινομημένο πίνακα στον οποίο
2, 3, 4, 5, 6 και είναι όλα ταξινομημένο.

472
00:21:33,730 --> 00:21:37,530
Μήπως όλοι κατανοούν τη λογική
για το πώς λειτουργεί ένα είδος επιλογής;

473
00:21:37,530 --> 00:21:39,669
>> Απλά έχουν κάποιο είδος
από μια ελάχιστη τιμή.

474
00:21:39,669 --> 00:21:41,210
Είσαι παρακολούθηση του τι είναι αυτό.

475
00:21:41,210 --> 00:21:45,170
Και κάθε φορά που θα το βρείτε, μπορείτε να το ανταλλάξετε
με την πρώτη τιμή στην array--

476
00:21:45,170 --> 00:21:48,740
ή, δεν είναι η πρώτη value--
η επόμενη τιμή στη συστοιχία.

477
00:21:48,740 --> 00:21:50,150
Cool.

478
00:21:50,150 --> 00:21:55,460
>> Έτσι όπως εσείς το είδος της
είδε από μια σύντομη ματιά,

479
00:21:55,460 --> 00:21:58,450
θα πάμε να ψευδοκώδικα αυτό.

480
00:21:58,450 --> 00:22:02,510
Έτσι, αν έχετε παιδιά στο πίσω θέλετε να
σχηματίζουν μια ομάδα, ο καθένας σε ένα τραπέζι

481
00:22:02,510 --> 00:22:06,170
μπορεί να σχηματίσει ένα μικρό εταίρο, Πάω
για να σας δώσει τύπους σαν τρία λεπτά

482
00:22:06,170 --> 00:22:08,190
να μιλάμε μόνο μέσω
η λογική, στην αγγλική γλώσσα,

483
00:22:08,190 --> 00:22:14,161
για το πώς θα μπορέσουμε να εφαρμόσουν
ψευδοκώδικας για να γράψει ένα είδος επιλογής.

484
00:22:14,161 --> 00:22:14,910
Και υπάρχει καραμέλα.

485
00:22:14,910 --> 00:22:16,118
Παρακαλούμε έρθει και να πάρει την καραμέλα.

486
00:22:16,118 --> 00:22:19,520
Αν είστε στην πλάτη και θέλετε
καραμέλα, μπορώ να ρίξει καραμέλα σε σας.

487
00:22:19,520 --> 00:22:22,850
Στην πραγματικότητα, κάνει you-- δροσερό.

488
00:22:22,850 --> 00:22:23,552
Ω συγνώμη.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
ΕΝΤΆΞΕΙ.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Έτσι, αν θα θέλαμε να, όπως
μια κατηγορία, ο ψευδοκώδικας εγγραφής

493
00:25:27,140 --> 00:25:30,466
για το πώς θα μπορούσε κανείς να προσεγγίσει
Αυτό το πρόβλημα, απλά αισθανθείτε ελεύθερος.

494
00:25:30,466 --> 00:25:32,340
Θα πήγαινε γύρω και,
προκειμένου, να ζητήσει από τις ομάδες

495
00:25:32,340 --> 00:25:35,065
για την επόμενη γραμμή του
τι πρέπει να κάνουμε.

496
00:25:35,065 --> 00:25:37,840
Έτσι, αν εσείς θέλετε να ξεκινήσετε
μακριά, ποιο είναι το πρώτο πράγμα που

497
00:25:37,840 --> 00:25:40,600
πρέπει να κάνετε όταν προσπαθείτε να
εφαρμόσει έναν τρόπο για να λύσει αυτό το πρόγραμμα

498
00:25:40,600 --> 00:25:43,480
να ταξινομήσετε επιλεκτικά μια λίστα;

499
00:25:43,480 --> 00:25:46,349
Ας υποθέσουμε ότι
Έχουν μια σειρά, εντάξει;

500
00:25:46,349 --> 00:25:49,088
>> Κοινό: Θέλετε να δημιουργήσετε κάποια
είδος [δεν ακούγεται] ότι είστε

501
00:25:49,088 --> 00:25:50,420
που διατρέχει ολόκληρη σειρά σας.

502
00:25:50,420 --> 00:25:51,128
>> ANDI PENG: Δεξιά.

503
00:25:51,128 --> 00:25:54,100
Έτσι θα πάμε να θέλουν να επαναλάβει
μέσα από κάθε χώρο, έτσι δεν είναι;

504
00:25:54,100 --> 00:26:05,490
Τόσο μεγάλη.

505
00:26:05,490 --> 00:26:08,600
Αν εσείς θέλετε να μου δώσει το
επόμενη line-- ναι, στο πίσω μέρος.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> Κοινό: Ελέγξτε τους
όλα για το μικρότερο.

508
00:26:13,290 --> 00:26:14,248
>> ANDI PENG: Εκεί πάμε.

509
00:26:14,248 --> 00:26:17,438
Θέλουμε, λοιπόν, να περάσει και να ελέγξετε
δείτε ποια είναι η ελάχιστη τιμή είναι, σωστά;

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Πάω να συντομεύσει ότι για να «min».

512
00:26:24,840 --> 00:26:27,658
Τι εσείς θέλετε να κάνετε μετά
έχετε βρει την ελάχιστη τιμή;

513
00:26:27,658 --> 00:26:28,533
>> Κοινό: [δεν ακούγεται]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI PENG: Έτσι θα πάμε να θέλουν να
εναλλαγή με το πρώτο του εν λόγω πίνακα,

516
00:26:33,150 --> 00:26:33,650
έτσι δεν είναι;

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
Αυτή είναι η αρχή, Πάω να πω.

519
00:26:46,850 --> 00:26:47,220
Εντάξει.

520
00:26:47,220 --> 00:26:50,386
Έτσι τώρα που έχετε ανταλλάξει την πρώτη
μία, τι θέλεις να κάνω μετά από αυτό;

521
00:26:50,386 --> 00:26:54,840
Μέχρι τώρα γνωρίζουμε πως αυτό εδώ
πρέπει να είναι η μικρότερη τιμή, σωστά;

522
00:26:54,840 --> 00:26:58,310
Στη συνέχεια, έχετε ένα επιπλέον υπόλοιπο
του πίνακα που είναι αδιαχώριστα.

523
00:26:58,310 --> 00:27:01,569
Έτσι, αυτό που θέλουμε να κάνουμε εδώ, αν
παιδιά θέλουν να μου δώσει την επόμενη γραμμή;

524
00:27:01,569 --> 00:27:04,610
Κοινό: Άρα λοιπόν θέλετε να μετακινηθείτε
για το υπόλοιπο της διάταξης.

525
00:27:04,610 --> 00:27:05,276
ANDI PENG: Ναι.

526
00:27:05,276 --> 00:27:09,857
Και έτσι τι κάνει επανάληψη μέσω
είδος σημαίνει ότι θα πρέπει πιθανώς;

527
00:27:09,857 --> 00:27:10,440
Τι είδους of--

528
00:27:10,440 --> 00:27:12,057
>> Κοινό: Ω, μια επιπλέον μεταβλητή;

529
00:27:12,057 --> 00:27:13,890
ANDI PENG: Πιθανώς
ένα άλλο για το βρόχο, έτσι δεν είναι;

530
00:27:13,890 --> 00:27:28,914
Γι 'αυτό και πρόκειται πιθανώς να θέλουν
να επαναλάβει through-- μεγάλη.

531
00:27:28,914 --> 00:27:31,830
Και μετά θα πάμε για να πάει πίσω και να
πιθανώς να ελέγξει την ελάχιστη και πάλι,

532
00:27:31,830 --> 00:27:32,100
έτσι δεν είναι;

533
00:27:32,100 --> 00:27:34,975
Και θα πάμε να το επαναλαμβάνουμε
αυτό, επειδή οι θηλιές ακριβώς πρόκειται

534
00:27:34,975 --> 00:27:36,010
να συνεχίσει να τρέχει, έτσι δεν είναι;

535
00:27:36,010 --> 00:27:39,190
>> Έτσι, όπως μπορείτε να δείτε τα παιδιά, εμείς
μόνο να έχουν μια γενική ψευδοκώδικα

536
00:27:39,190 --> 00:27:41,480
για το πώς θέλουμε αυτό το πρόγραμμα για να δούμε.

537
00:27:41,480 --> 00:27:46,646
Αυτό το επαναλάβει εδώ, τι κάνουμε εμείς
συνήθως πρέπει να γράψετε σε κώδικα μας

538
00:27:46,646 --> 00:27:49,270
αν θέλουμε να μετακινηθείτε μέσα από μια
ποικιλία, το είδος της κατασκευής;

539
00:27:49,270 --> 00:27:51,030
Νομίζω Christabel
ήδη πει αυτό πριν.

540
00:27:51,030 --> 00:27:51,500
>> Κοινό: Ένας βρόχος for.

541
00:27:51,500 --> 00:27:52,160
>> ANDI PENG: Α για βρόχο;

542
00:27:52,160 --> 00:27:52,770
Ακριβώς.

543
00:27:52,770 --> 00:27:56,060
Έτσι, αυτό είναι πιθανώς
πρόκειται να είναι ένα για το βρόχο.

544
00:27:56,060 --> 00:27:59,240
Τι είναι ένας έλεγχος εδώ θα σημαίνει;

545
00:27:59,240 --> 00:28:02,536
Συνήθως, αν θέλετε να ελέγξετε
αν κάτι είναι κάτι else--

546
00:28:02,536 --> 00:28:03,270
>> Κοινό: Αν.

547
00:28:03,270 --> 00:28:06,790
>> ANDI PENG: Μια περίπτωση, σωστά;

548
00:28:06,790 --> 00:28:10,790
Και τότε η ανταλλαγή εδώ, θα
πάει πάνω αργότερα, γιατί ο David

549
00:28:10,790 --> 00:28:12,770
πέρασε από ότι σε διάλεξη καθώς και.

550
00:28:12,770 --> 00:28:14,580
Και τότε το δεύτερο επαναλάβει implies--

551
00:28:14,580 --> 00:28:15,120
>> Κοινό: Άλλη για το βρόχο.

552
00:28:15,120 --> 00:28:16,745
>> ANDI PENG: --another για το βρόχο, ακριβώς.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Έτσι, αν ψάχνουμε
σε αυτό σωστά, θα

555
00:28:22,000 --> 00:28:24,680
μπορεί να δει ότι είμαστε κατά πάσα πιθανότητα
Θα χρειαστείτε μια ένθετη βρόχο για

556
00:28:24,680 --> 00:28:28,330
με την προϋπόθεση δήλωση εκεί
και, στη συνέχεια, ένα πραγματικό κομμάτι του κώδικα που είναι

557
00:28:28,330 --> 00:28:31,360
πρόκειται να ανταλλάξουν τις αξίες.

558
00:28:31,360 --> 00:28:35,980
Έτσι έχω μόνο γενικά γραπτή
ένας κώδικας ψευδοκώδικας εδώ.

559
00:28:35,980 --> 00:28:38,910
Και τότε είμαστε στην πραγματικότητα θα
σε φυσικά, ως τάξη,

560
00:28:38,910 --> 00:28:40,700
προσπαθούν να εφαρμόσουν αυτή σήμερα.

561
00:28:40,700 --> 00:28:42,486
Ας πάμε πίσω σε αυτό το IDE.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> Ωχ.

564
00:28:50,230 --> 00:28:51,754
Γιατί είναι ότι not-- εκεί είναι.

565
00:28:51,754 --> 00:28:52,253
ΕΝΤΆΞΕΙ.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Λυπούμαστε, επιτρέψτε μου να προσπαθήσω να μεγεθύνετε σε λίγο περισσότερο.

568
00:28:57,500 --> 00:28:59,310
Εκεί πάμε.

569
00:28:59,310 --> 00:29:05,060
Όλα τα κάνω εδώ είναι που έχω δημιουργήσει
ένα πρόγραμμα που ονομάζεται "επιλογή / sort.c."

570
00:29:05,060 --> 00:29:10,860
Έχω δημιουργήσει μια σειρά από εννέα
αξίες, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
Επί του παρόντος, όπως μπορείτε
Βλέπετε, αυτοί είναι μη ταξινομημένες.

572
00:29:14,370 --> 00:29:17,880
n πρόκειται να είναι ο αριθμός ότι
σας λέει το ποσό των αξιών

573
00:29:17,880 --> 00:29:18,920
έχετε στη σειρά σας.

574
00:29:18,920 --> 00:29:20,670
Σε αυτή την περίπτωση, έχουμε εννέα τιμές.

575
00:29:20,670 --> 00:29:23,760
Και έχω απλά ένα βρόχο for εδώ
ότι εκτυπώνει το αδιαχώριστα πίνακα.

576
00:29:23,760 --> 00:29:28,370
>> Και στο τέλος, έχω επίσης πήρε για
βρόχο που εκτυπώνει μόνο φορά.

577
00:29:28,370 --> 00:29:32,070
Έτσι, θεωρητικά, εάν αυτό το πρόγραμμα
λειτουργεί σωστά, στο τέλος,

578
00:29:32,070 --> 00:29:35,670
θα πρέπει να δείτε ένα έντυπο για το βρόχο
στην οποία 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 είναι όλα σωστά στην τάξη.

580
00:29:39,310 --> 00:29:43,410
>> Έτσι έχουμε ψευδοκώδικας μας εδώ.

581
00:29:43,410 --> 00:29:46,090
Υπάρχει κάποιος που θέλει to-- Είμαι απλά
πρόκειται να πάει να ζητήσει volunteers--

582
00:29:46,090 --> 00:29:49,540
πες μου ακριβώς τι πρέπει να πληκτρολογήσετε αν
θέλουμε, πρώτα, απλά επαναλήψεις

583
00:29:49,540 --> 00:29:52,840
μέσα από την αρχή αυτής της διάταξης;

584
00:29:52,840 --> 00:29:55,204
Ποια είναι η γραμμή κώδικα είμαι
κατά πάσα πιθανότητα θα χρειαστεί εδώ;

585
00:29:55,204 --> 00:29:56,990
>> Κοινό: [δεν ακούγεται]

586
00:29:56,990 --> 00:29:59,010
>> ANDI PENG: Ναι, αισθάνομαι
δωρεάν to-- συγγνώμη, σας

587
00:29:59,010 --> 00:30:02,318
Δεν χρειάζεται να σταθεί αίσθηση up--
ελεύθερο να υψώσετε τη φωνή σας λίγο.

588
00:30:02,318 --> 00:30:08,190
>> Κοινό: Για int i ισούται με 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI PENG: Ναι, καλά.

590
00:30:10,690 --> 00:30:15,220
>> Κοινό: i είναι μικρότερο από το μήκος του πίνακα.

591
00:30:15,220 --> 00:30:19,630
>> ANDI PENG: Έτσι λάβετε
πειράζει εδώ, γιατί είμαστε

592
00:30:19,630 --> 00:30:23,060
δεν έχουν μια λειτουργία που
μας λέει το μήκος μιας συστοιχίας,

593
00:30:23,060 --> 00:30:25,790
Έχουμε ήδη ένα
αξία που αποθηκεύει αυτό.

594
00:30:25,790 --> 00:30:27,920
Σωστά;

595
00:30:27,920 --> 00:30:31,010
Ένα άλλο πράγμα που πρέπει να
σε mind-- σε μια σειρά

596
00:30:31,010 --> 00:30:33,940
εννέα αξίες, ποιες είναι οι δείκτες;

597
00:30:33,940 --> 00:30:38,720
Ας πούμε απλά ο πίνακας αυτός ήταν 0-3.

598
00:30:38,720 --> 00:30:41,500
Θα δείτε ότι το τελευταίο
δείκτης είναι στην πραγματικότητα 3.

599
00:30:41,500 --> 00:30:45,530
Δεν είναι 4, ακόμα κι αν υπάρχει
τέσσερις τιμές στη συστοιχία.

600
00:30:45,530 --> 00:30:49,866
>> Έτσι, εδώ, πρέπει να είμαστε πολύ προσεκτικοί
του πώς είναι η κατάστασή μας για το μήκος

601
00:30:49,866 --> 00:30:50,490
θα είναι.

602
00:30:50,490 --> 00:30:51,948
>> Κοινό: Δεν θα ήταν ν μείον 1;

603
00:30:51,948 --> 00:30:54,440
ANDI PENG: Δεν πρόκειται
n μείον 1, ακριβώς.

604
00:30:54,440 --> 00:30:57,379
Μήπως αυτό έχει νόημα, γιατί
n είναι μείον 1, ο καθένας;

605
00:30:57,379 --> 00:30:58,920
Είναι επειδή συστοιχίες είναι μηδέν-index.

606
00:30:58,920 --> 00:31:02,010
Αρχίζουν από το 0 και να τρέξει μέχρι ν μείον 1.

607
00:31:02,010 --> 00:31:03,210
Ναι, είναι λίγο δύσκολο.

608
00:31:03,210 --> 00:31:03,730
ΕΝΤΆΞΕΙ.

609
00:31:03,730 --> 00:31:05,929
Και μετά--

610
00:31:05,929 --> 00:31:08,054
Κοινό: Isnt'1 ότι
που έχουν ήδη ληφθεί μέριμνα όμως,

611
00:31:08,054 --> 00:31:11,400
από απλά δεν λέει "μικρότερη ή
ίσο με το "και απλά λέγοντας« λιγότερο από ό, τι; "

612
00:31:11,400 --> 00:31:13,108
>> ANDI PENG: Αυτό είναι ένα
πολύ καλή ερώτηση.

613
00:31:13,108 --> 00:31:13,630
Έτσι, ναι.

614
00:31:13,630 --> 00:31:17,410
Αλλά, επίσης, τον τρόπο με τον οποίο είμαστε
την εφαρμογή του δικαιώματος ελέγχου,

615
00:31:17,410 --> 00:31:19,120
θα πρέπει να συγκρίνετε δύο τιμές.

616
00:31:19,120 --> 00:31:21,009
Έτσι θέλετε πραγματικά να
αφήστε το "στο" άδειο.

617
00:31:21,009 --> 00:31:23,050
Γιατί αν συγκρίνουμε
αυτό, εσείς δεν πρόκειται

618
00:31:23,050 --> 00:31:25,530
έχει τίποτα μετά
να συγκρίνουν με, έτσι δεν είναι;

619
00:31:25,530 --> 00:31:27,460
Ναι.

620
00:31:27,460 --> 00:31:29,297
Έτσι i ++.

621
00:31:29,297 --> 00:31:30,380
Ας προσθέσουμε σε παρένθεση μας.

622
00:31:30,380 --> 00:31:30,880
Ωχ.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Εξαιρετική.

625
00:31:34,710 --> 00:31:39,117
Έτσι έχουμε την αρχή
του εξωτερικού βρόχου μας.

626
00:31:39,117 --> 00:31:41,450
Έτσι, τώρα πιθανόν να θέλετε να
δημιουργήσετε μια μεταβλητή για τη διατήρηση

627
00:31:41,450 --> 00:31:43,085
παρακολουθείτε τη μικρότερη τιμή, σωστά;

628
00:31:43,085 --> 00:31:45,751
Θέλει κανείς να μου δώσει το
γραμμή του κώδικα που θα το κάνει αυτό;

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
Τι χρειαζόμαστε αν θέλουμε
να θέλετε να αποθηκεύσετε κάτι;

631
00:31:53,570 --> 00:31:55,047
>> Δεξιά.

632
00:31:55,047 --> 00:31:57,630
Ίσως ένα καλύτερο όνομα γι 'αυτό
θα be-- "temp" εντελώς works--

633
00:31:57,630 --> 00:32:00,655
ίσως μια πιο εύστοχα ονομάστηκε θα είναι,
αν θέλουμε το μικρότερο value--

634
00:32:00,655 --> 00:32:01,624
>> Κοινό: Min.

635
00:32:01,624 --> 00:32:02,790
ANDI PENG: λεπτά, εκεί θα πάμε.

636
00:32:02,790 --> 00:32:05,230
min θα ήταν καλό.

637
00:32:05,230 --> 00:32:08,340
Και έτσι εδώ, τι κάνουμε εμείς
Θέλετε να γίνει η προετοιμασία για;

638
00:32:08,340 --> 00:32:09,620
Αυτό είναι λίγο δύσκολο.

639
00:32:09,620 --> 00:32:13,580
Επειδή αυτή τη στιγμή κατά τη
αρχή αυτής της διάταξης,

640
00:32:13,580 --> 00:32:15,730
δεν έχετε κοίταξε τίποτα, σωστά;

641
00:32:15,730 --> 00:32:19,200
Έτσι, αυτό που, αυτόματα, εάν
είμαστε ακριβώς στο i ισούται με 0,

642
00:32:19,200 --> 00:32:22,302
τι θέλουμε να προετοιμαστεί
πρώτη ελάχιστη τιμή για μας;

643
00:32:22,302 --> 00:32:22,802
Κοινό: i.

644
00:32:22,802 --> 00:32:24,790
ANDI PENG: i, ακριβώς.

645
00:32:24,790 --> 00:32:27,040
Christabel, γιατί θέλουμε
να γίνει η προετοιμασία για i;

646
00:32:27,040 --> 00:32:28,510
>> Κοινό: Επειδή, επίσης,
ξεκινάμε με 0.

647
00:32:28,510 --> 00:32:31,660
Έτσι, γιατί δεν έχουμε τίποτα να συγκρίνετε
να, η ελάχιστη θα καταλήξει να είναι 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI PENG: Ακριβώς.

649
00:32:32,451 --> 00:32:34,400
Έτσι, αυτή είναι ακριβώς σωστό.

650
00:32:34,400 --> 00:32:36,780
Επειδή δεν έχουμε στην πραγματικότητα
κοίταξε τίποτα ακόμα,

651
00:32:36,780 --> 00:32:38,680
δεν ξέρουμε τι ελάχιστη τιμή μας είναι.

652
00:32:38,680 --> 00:32:41,960
Θέλουμε να γίνει η προετοιμασία μόνο για να
i, η οποία, επί του παρόντος, είναι ακριβώς εδώ.

653
00:32:41,960 --> 00:32:44,750
Και καθώς συνεχίζουμε να
κινούνται προς αυτή την σειρά,

654
00:32:44,750 --> 00:32:48,122
θα δούμε ότι, με κάθε
επιπλέον άδεια, θ αυξάνει.

655
00:32:48,122 --> 00:32:49,830
Και έτσι σε εκείνο το σημείο,
i είναι κατά πάσα πιθανότητα θα

656
00:32:49,830 --> 00:32:52,329
να θέλουν να είναι το ελάχιστο,
επειδή πρόκειται να είναι ό, τι

657
00:32:52,329 --> 00:32:54,520
είναι η αρχή της αδιαχώριστα πίνακα.

658
00:32:54,520 --> 00:32:55,270
Cool.

659
00:32:55,270 --> 00:32:58,720
>> Έτσι, τώρα θέλουμε να προσθέσουμε
ένα για το βρόχο εδώ που είναι

660
00:32:58,720 --> 00:33:03,225
πρόκειται να επαναλάβει μέσω της
αδιαχώριστα, ή το υπόλοιπο αυτής της διάταξης.

661
00:33:03,225 --> 00:33:05,808
Θέλει κανείς να μου δώσει ένα
γραμμή του κώδικα που θα το κάνει αυτό;

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- τι χρειαζόμαστε εδώ κάτω;

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
Τι πρόκειται να πάει σε αυτό για βρόχο;

666
00:33:18,820 --> 00:33:19,465
Ναι.

667
00:33:19,465 --> 00:33:21,590
Κοινό: Έτσι θα θέλατε να
έχουν διαφορετική ακέραιος,

668
00:33:21,590 --> 00:33:25,080
επειδή είμαστε τρέχει μέσα από το υπόλοιπο
του πίνακα αντί του i, οπότε ίσως

669
00:33:25,080 --> 00:33:25,760
j.

670
00:33:25,760 --> 00:33:27,301
>> ANDI PENG: Ναι, ι ακούγεται καλό για μένα.

671
00:33:27,301 --> 00:33:27,850
Ίσο;

672
00:33:27,850 --> 00:33:33,930
>> Κοινό: Έτσι θα πρέπει να είναι i + 1, επειδή
ξεκινάτε την επόμενη τιμή.

673
00:33:33,930 --> 00:33:40,395
Και στη συνέχεια στο end-- έτσι και πάλι, το j είναι
λιγότερο από n μείον 1, και στη συνέχεια, j ++.

674
00:33:40,395 --> 00:33:41,103
ANDI PENG: Μεγάλη.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> Και στη συνέχεια εδώ, θα πάμε να θέλουν
για να ελέγξετε για να δείτε αν η κατάσταση μας έχει τηρηθεί,

677
00:33:52,750 --> 00:33:53,250
έτσι δεν είναι;

678
00:33:53,250 --> 00:33:55,740
Επειδή θέλετε να
αλλάξετε την ελάχιστη τιμή

679
00:33:55,740 --> 00:33:58,700
αν είναι στην πραγματικότητα μικρότερη από ό, τι
είστε το συγκρίνει με, έτσι δεν είναι;

680
00:33:58,700 --> 00:34:01,146
Λοιπόν, τι θα πάμε να θέλουν εδώ;

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Ελέγξτε για να δείτε.

683
00:34:04,897 --> 00:34:06,730
Τι είδους δήλωση
είμαστε κατά πάσα πιθανότητα θα

684
00:34:06,730 --> 00:34:08,389
ti θέλετε να χρησιμοποιήσετε, εάν
θέλετε να ελέγξετε κάτι;

685
00:34:08,389 --> 00:34:09,360
>> ΚΟΙΝΟ: Η εντολή if.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: Μια εντολή if.

687
00:34:10,485 --> 00:34:13,155
Έτσι if-- και τι πρόκειται να είναι
η κατάσταση που θέλουμε μέσα

688
00:34:13,155 --> 00:34:13,988
της εντολής if μας;

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> Κοινό: Εάν η τιμή του j
είναι μικρότερη από την τιμή των i--

691
00:34:22,960 --> 00:34:24,600
>> ANDI PENG: Ακριβώς.

692
00:34:24,600 --> 00:34:27,480
Έτσι if-- οπότε ο συγκεκριμένος πίνακας ονομάζεται "συστοιχία".

693
00:34:27,480 --> 00:34:27,980
Εξαιρετική.

694
00:34:27,980 --> 00:34:30,465
Έτσι, αν array-- τι ήταν αυτό;

695
00:34:30,465 --> 00:34:31,090
Αυτο ξαναπεστο.

696
00:34:31,090 --> 00:34:39,590
>> Κοινό: Εάν το όρισμα array-j είναι μικρότερη από
σειρά-i, τότε θα αλλάξει το λεπτό.

697
00:34:39,590 --> 00:34:41,590
Έτσι, το λεπτό θα είναι ι.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI PENG: Μήπως αυτό έχει νόημα;

700
00:34:47,249 --> 00:34:48,670
ΕΝΤΆΞΕΙ.

701
00:34:48,670 --> 00:34:52,929
Και τώρα εδώ κάτω, στην πραγματικότητα
θέλουν να εφαρμόσουν τη συμφωνία ανταλλαγής, έτσι δεν είναι;

702
00:34:52,929 --> 00:34:58,285
Έτσι, υπενθυμίζουν, στη διάλεξη, ότι ο Δαβίδ, όταν
προσπαθούσε να ανταλλάξουν the-- ό, τι ήταν

703
00:34:58,285 --> 00:34:59,996
it-- χυμό πορτοκαλιού και milk--

704
00:34:59,996 --> 00:35:01,150
>> Κοινό: Αυτό ήταν ακαθάριστο.

705
00:35:01,150 --> 00:35:02,816
>> ANDI PENG: Ναι, αυτό ήταν το είδος του ακαθάριστου.

706
00:35:02,816 --> 00:35:05,310
Αλλά ήταν μια αρκετά καλή
η έννοια του χρόνου επίδειξη.

707
00:35:05,310 --> 00:35:08,430
Έτσι σκεφτείτε τις αξίες σας εδώ.

708
00:35:08,430 --> 00:35:10,794
Έχετε μια σειρά
από λεπτό, μια σειρά από i,

709
00:35:10,794 --> 00:35:12,460
ή ό, τι προσπαθούμε να ανταλλάξουν εδώ.

710
00:35:12,460 --> 00:35:15,310
Και ίσως να μην μπορεί να τα ρίχνουμε σε
κάθε άλλο κατά την ίδια στιγμή, έτσι;

711
00:35:15,310 --> 00:35:17,180
Λοιπόν, τι θα πάμε
να χρειαστεί να δημιουργήσετε εδώ

712
00:35:17,180 --> 00:35:19,126
προκειμένου να ανταλλάξουν τις αξίες σωστά;

713
00:35:19,126 --> 00:35:19,820
>> Κοινό: Μια προσωρινή μεταβλητή.

714
00:35:19,820 --> 00:35:21,370
>> ANDI PENG: Μια προσωρινή μεταβλητή.

715
00:35:21,370 --> 00:35:22,570
Έτσι, ας κάνουμε int temp.

716
00:35:22,570 --> 00:35:25,681
Βλέπε, αυτό θα είναι μια καλύτερη
to-- χρόνο Πω πω, τι ήταν αυτό;

717
00:35:25,681 --> 00:35:26,180
ΕΝΤΆΞΕΙ.

718
00:35:26,180 --> 00:35:29,800
Έτσι, αυτό θα ήταν μια καλύτερη
χρόνο για να αναφέρουμε τη μεταβλητή "temp".

719
00:35:29,800 --> 00:35:30,730
Έτσι, ας κάνουμε int temp.

720
00:35:30,730 --> 00:35:32,563
Τι θα πάμε να
Set Temp ίσο με εδώ;

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
Κοινό: Ελάχιστη;

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
ANDI PENG: Είναι λίγο δύσκολο.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
Είναι πραγματικά δεν έχει σημασία στο τέλος.

727
00:35:44,880 --> 00:35:47,690
Δεν έχει σημασία τι
Για να επιλέξετε να ανταλλάξουν σε

728
00:35:47,690 --> 00:35:50,862
εφ 'όσον έχετε κάνει ότι είστε
την παρακολούθηση του τι είστε εναλλαγή.

729
00:35:50,862 --> 00:35:52,250
>> Κοινό: Θα μπορούσε να είναι σειρά-i.

730
00:35:52,250 --> 00:35:53,666
>> ANDI PENG: Ναι, ας κάνουμε σειρά-i.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
Και τότε ποια είναι η επόμενη γραμμή
του κώδικα θέλουμε να έχουμε εδώ;

733
00:35:59,305 --> 00:36:00,680
Κοινό: array-i ισούται με διάταξη-j.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI PENG: Και τέλος;

736
00:36:08,070 --> 00:36:12,070
Κοινό: array-j ισούται με σειρά-i.

737
00:36:12,070 --> 00:36:14,525
Κοινό: Ή διάταξη-j ισούται
array-temp-- ή, temp.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI PENG: OK.

740
00:36:19,430 --> 00:36:21,510
Ας τρέξει αυτή και να δούμε
αν πρόκειται να λειτουργήσει.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
Πού είναι αυτό που συμβαίνει;

743
00:36:39,335 --> 00:36:40,210
Ω, αυτό είναι ένα πρόβλημα.

744
00:36:40,210 --> 00:36:44,320
Δείτε, επί της γραμμής 40, είμαστε
προσπαθείτε να χρησιμοποιήσετε συστοιχία-ι;

745
00:36:44,320 --> 00:36:47,022
Αλλά από πού ι υπάρχουν μόνο μέσα;

746
00:36:47,022 --> 00:36:48,402
>> ΚΟΙΝΟ: Στο βρόχο for.

747
00:36:48,402 --> 00:36:49,110
ANDI PENG: Δεξιά.

748
00:36:49,110 --> 00:36:51,730
Λοιπόν, τι θα πάμε να πρέπει να κάνουμε;

749
00:36:51,730 --> 00:36:53,170
>> Κοινό: Ορίστε το εξωτερικό the--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
Κοινό: Ναι, υποθέτω ότι έχετε
να χρησιμοποιήσει άλλη μία εντολή if, έτσι δεν είναι;

752
00:37:00,610 --> 00:37:05,230
Έτσι, όπως, αν ο minimum--
Εντάξει, επιτρέψτε μου να πιστεύω.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI PENG: Παιδιά, δοκιμάστε
να ρίξετε μια ματιά Ας

755
00:37:09,990 --> 00:37:11,270
Βλέπετε, αυτό είναι κάτι που μπορούμε να κάνουμε εδώ;

756
00:37:11,270 --> 00:37:11,811
>> Κοινό: OK.

757
00:37:11,811 --> 00:37:15,900
Έτσι, αν η ελάχιστη δεν ισούται
j-- οπότε αν το ελάχιστο είναι ακόμα i--

758
00:37:15,900 --> 00:37:17,570
τότε δεν θα πρέπει να ανταλλάξουν.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI PENG: Θεωρεί ότι η ίση εγώ;

761
00:37:24,712 --> 00:37:25,920
Τι θέλω να πω εδώ;

762
00:37:25,920 --> 00:37:30,494
>> Κοινό: Ή ναι, αν η
ελάχιστο δεν είναι ίσο με i, ναι.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI PENG: OK.

765
00:37:40,210 --> 00:37:42,040
Λοιπόν ότι λύνει, το είδος του, τα προβλήματά μας.

766
00:37:42,040 --> 00:37:47,265
Αλλά αυτό ακόμα δεν λύνει το
το πρόβλημα του τι θα συμβεί αν j-- από το j

767
00:37:47,265 --> 00:37:49,890
δεν υπάρχει έξω από αυτό, τι
δεν θα θέλουμε να κάνουμε με αυτό;

768
00:37:49,890 --> 00:37:50,698
Κηρύξει έξω;

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Ας προσπαθήσουμε τρέχει αυτό.

771
00:38:02,730 --> 00:38:04,435
Ωχ.

772
00:38:04,435 --> 00:38:06,200
Είδος μας δεν λειτουργεί.

773
00:38:06,200 --> 00:38:10,060
>> Όπως μπορείτε να δείτε, η αρχική μας
σειρά είχε αυτές τις αξίες.

774
00:38:10,060 --> 00:38:14,800
Και μετά θα πρέπει να έχει
ήταν σε 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Δεν λειτουργεί.

776
00:38:15,530 --> 00:38:16,030
Ααα.

777
00:38:16,030 --> 00:38:17,184
Τι κάνουμε?

778
00:38:17,184 --> 00:38:17,850
Κοινό: Debug.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI PENG: Εντάξει, μπορούμε να προσπαθήσουμε αυτό.

781
00:38:23,370 --> 00:38:25,030
Μπορούμε να debug.

782
00:38:25,030 --> 00:38:26,042
Σμίκρυνση λίγο.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Ας ορίσετε breakpoint μας.

785
00:38:33,656 --> 00:38:37,280
Ας πάμε like-- ΟΚ.

786
00:38:37,280 --> 00:38:40,444
>> Έτσι, επειδή γνωρίζουμε ήδη ότι
Αυτές οι γραμμές, 15 έως 22,

787
00:38:40,444 --> 00:38:43,610
Οι working-- γιατί όλα τα κάνω είναι
απλά επανάληψη και μέσω printing--

788
00:38:43,610 --> 00:38:45,406
Μπορώ να προχωρήσει και να παραλείψετε αυτό.

789
00:38:45,406 --> 00:38:47,280
Ας ξεκινήσουμε από τη γραμμή 25.

790
00:38:47,280 --> 00:38:48,712
Oop, επιτρέψτε μου να απαλλαγούμε από αυτό.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> Κοινό: Έτσι, το σημείο διακοπής του
όπου η αποσφαλμάτωση ξεκινά;

793
00:38:54,057 --> 00:38:54,890
ANDI PENG: ή σταματά.

794
00:38:54,890 --> 00:38:55,670
Κοινό: Ή στάσεις.

795
00:38:55,670 --> 00:38:55,930
ANDI PENG: Ναι.

796
00:38:55,930 --> 00:38:58,640
Μπορείτε να ορίσετε πολλαπλά σημεία διακοπής και
μπορεί απλά να πηδούν από το ένα στο άλλο.

797
00:38:58,640 --> 00:39:01,590
Αλλά σε αυτή την περίπτωση δεν γνωρίζουμε
όπου συμβαίνει το σφάλμα.

798
00:39:01,590 --> 00:39:03,780
Γι 'αυτό ακριβώς θέλουμε να
ξεκινούν από την κορυφή προς τα κάτω.

799
00:39:03,780 --> 00:39:05,020
Ναι.

800
00:39:05,020 --> 00:39:05,550
ΕΝΤΆΞΕΙ.

801
00:39:05,550 --> 00:39:08,460
>> Έτσι, η γραμμή αυτή εδώ, μπορούμε να παρέμβει.

802
00:39:08,460 --> 00:39:11,499
Μπορείτε να δείτε εδώ κάτω,
έχουμε μια σειρά.

803
00:39:11,499 --> 00:39:13,290
Αυτοί είναι οι αξίες
που είναι στη συστοιχία.

804
00:39:13,290 --> 00:39:16,360
Βλέπετε ότι, πώς δείκτη 0, το
αντιστοιχεί στο value-- OH,

805
00:39:16,360 --> 00:39:17,526
Πάω να προσπαθήσω να μεγεθύνετε.

806
00:39:17,526 --> 00:39:20,650
Συγγνώμη, αυτό είναι πραγματικά δύσκολο
να see-- στο ευρετήριο πίνακα 0,

807
00:39:20,650 --> 00:39:24,090
έχουμε μια τιμή 4 και
τότε ούτω καθεξής και ούτω καθεξής.

808
00:39:24,090 --> 00:39:25,670
Έχουμε τοπικές μεταβλητές μας.

809
00:39:25,670 --> 00:39:28,570
Αυτή τη στιγμή i είναι ίσο με
0, η οποία θέλουμε να είναι.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> Και έτσι ας κρατήσουμε την ενίσχυση μέσα.

812
00:39:33,690 --> 00:39:36,850
Ελάχιστο μας είναι ίση με 0,
το οποίο θέλουμε επίσης να είναι.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
Και τότε μπαίνουμε δεύτερη μας
βρόχο, αν array-j είναι μικρότερη από array-i,

815
00:39:45,560 --> 00:39:46,380
η οποία δεν ήταν.

816
00:39:46,380 --> 00:39:48,130
Έτσι, είδες πώς
ότι παρακάμπτονται αυτό;

817
00:39:48,130 --> 00:39:52,430
>> Κοινό: Έτσι, αν θα πρέπει να το
ελάχιστο, όλα that-- δεν θα πρέπει να

818
00:39:52,430 --> 00:39:55,424
είναι μέσα στο πρώτο για το βρόχο;

819
00:39:55,424 --> 00:39:57,340
ANDI PENG: Όχι, γιατί
Εξακολουθείτε να θέλετε να δοκιμάσετε.

820
00:39:57,340 --> 00:40:00,329
Θέλετε να κάνετε μια σύγκριση κάθε
χρόνο, ακόμα και μετά την εκτέλεση μέσα από αυτό.

821
00:40:00,329 --> 00:40:02,620
Δεν θέλουν απλά να το κάνω
στο πρώτο πέρασμα-μέσω.

822
00:40:02,620 --> 00:40:05,240
Θέλετε να το κάνετε με
κάθε επιπλέον πέρασμα και πάλι.

823
00:40:05,240 --> 00:40:07,198
Έτσι θέλετε να ελέγξετε για
κατάστασή σας μέσα.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Έτσι, είμαστε ακριβώς πρόκειται να
συνεχίσει να τρέχει από εδώ.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Θα σας δώσω μια υπόδειξη παιδιά.

828
00:40:18,420 --> 00:40:23,910
Έχει να κάνει με το γεγονός ότι, όταν
έχετε τον έλεγχο υπό όρους σας,

829
00:40:23,910 --> 00:40:26,600
δεν είστε έλεγχο
για τη σωστή δείκτη.

830
00:40:26,600 --> 00:40:32,510
Έτσι τώρα έχετε τον έλεγχο για
ευρετήριο πίνακα του j είναι μικρότερη από σειρά

831
00:40:32,510 --> 00:40:33,970
δείκτη i.

832
00:40:33,970 --> 00:40:36,580
Αλλά τι κάνεις επάνω στο
Η αρχή του για βρόχο;

833
00:40:36,580 --> 00:40:38,260
Δεν είσαι ρύθμιση j ισούται με i;

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Ναι, έτσι μπορούμε πραγματικά
βγείτε από το πρόγραμμα εντοπισμού σφαλμάτων εδώ.

836
00:40:45,415 --> 00:40:47,040
Έτσι, ας ρίξουμε μια ματιά σε ψευδοκώδικα μας.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- θα πάμε να
ξεκινούν από i ισούται με 0.

839
00:40:52,580 --> 00:40:54,760
Εμείς πάμε για να πάει μέχρι ν μείον 1.

840
00:40:54,760 --> 00:40:58,040
Ας δούμε, δεν έχουμε αυτό το δικαίωμα;

841
00:40:58,040 --> 00:40:59,580
Ναι, αυτό ήταν σωστό.

842
00:40:59,580 --> 00:41:02,080
>> Άρα λοιπόν εδώ μέσα, είμαστε
πρόκειται να δημιουργήσουμε μια ελάχιστη τιμή

843
00:41:02,080 --> 00:41:03,630
και να ορίσετε ότι ισούται με i.

844
00:41:03,630 --> 00:41:04,950
Μήπως να το κάνουμε αυτό;

845
00:41:04,950 --> 00:41:06,270
Ναι, το έκανε αυτό.

846
00:41:06,270 --> 00:41:10,430
Τώρα στον εσωτερικό βρόχο για μας, είμαστε
πρόκειται να κάνει ι θ ισούται με n μείον 1.

847
00:41:10,430 --> 00:41:11,950
Μήπως να το κάνουμε αυτό;

848
00:41:11,950 --> 00:41:15,540
Πράγματι, το κάναμε.

849
00:41:15,540 --> 00:41:19,922
>> Έτσι όμως, αυτό που είμαστε συγκρίνοντας εδώ;

850
00:41:19,922 --> 00:41:20,925
>> Κοινό: ι συν 1.

851
00:41:20,925 --> 00:41:21,716
ANDI PENG: Ακριβώς.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
Και μετά θα πάμε να θέλουν να ορίσετε
ελάχιστη σας ίσο με j + 1, καθώς και.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Έτσι πήγα μέσα από αυτό πολύ γρήγορα.

856
00:41:32,640 --> 00:41:36,190
Έχετε παιδιά να κατανοήσουν
Γι 'αυτό είναι j + 1;

857
00:41:36,190 --> 00:41:36,890
ΕΝΤΆΞΕΙ.

858
00:41:36,890 --> 00:41:40,700
>> Έτσι, σε σειρά σας, σε
η πρώτη σας περάσει,

859
00:41:40,700 --> 00:41:44,850
για βρόχο σας, για int
i ισούται με 0, ας

860
00:41:44,850 --> 00:41:46,740
υποθέσετε ότι αυτό δεν έχει αλλάξει ακόμη.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
Έχουμε μια σειρά από εντελώς,
μόλις τέσσερις αδιαχώριστα στοιχεία, σωστά;

863
00:41:56,760 --> 00:42:00,760
Έτσι θέλουμε να προετοιμάσει i ισούται με 0.

864
00:42:00,760 --> 00:42:03,650
Και εγώ πρόκειται απλά
τρέχει μέσα από αυτό το βρόχο.

865
00:42:03,650 --> 00:42:08,560
Και έτσι στο πρώτο πέρασμα, θα πάμε
να προετοιμάσει μια μεταβλητή που ονομάζεται "λεπτό"

866
00:42:08,560 --> 00:42:11,245
ότι είναι επίσης ίσο με i, επειδή
δεν έχουμε μια ελάχιστη τιμή.

867
00:42:11,245 --> 00:42:12,870
Έτσι ώστε να είναι σήμερα ίση με 0, καθώς και.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
Και μετά θα πάμε για να περάσει.

870
00:42:17,640 --> 00:42:19,270
Και θέλουμε να επαναλάβει και πάλι.

871
00:42:19,270 --> 00:42:22,900
Τώρα που έχουμε βρει ό, τι ελάχιστο μας
είναι, θέλουμε να μετακινηθείτε μέσα

872
00:42:22,900 --> 00:42:25,190
ξανά για να δείτε αν είναι σύγκριση, σωστά;

873
00:42:25,190 --> 00:42:40,440
Έτσι, ι, εδώ, πρόκειται
στην ισότητα i, η οποία είναι 0.

874
00:42:40,440 --> 00:42:46,320
Και στη συνέχεια, αν συστοιχία ι συν θ, η οποία
είναι αυτός που είναι δίπλα πάνω, ως λιγότερο

875
00:42:46,320 --> 00:42:49,270
από ό, τι οι τρέχοντες κατώτατοι σας
αξίας είναι, θέλετε να ανταλλάξετε.

876
00:42:49,270 --> 00:42:56,850
>> Έτσι, ας πούμε έχουμε
πήρε, όπως, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Αυτή τη στιγμή, i είναι ίσο με
0 και j είναι ίσο με 0.

878
00:43:01,610 --> 00:43:05,210
Και αυτό είναι ελάχιστη αξία μας.

879
00:43:05,210 --> 00:43:09,950
Αν σειρά-ι συν i-- οπότε αν το ένα
αυτό είναι το ένα μετά ψάχνουμε

880
00:43:09,950 --> 00:43:13,450
είναι μεγαλύτερο από το προηγούμενο αυτό,
πρόκειται να γίνει η ελάχιστη.

881
00:43:13,450 --> 00:43:18,120
>> Έτσι, εδώ βλέπουμε ότι 5
δεν είναι μικρότερη από εκείνη.

882
00:43:18,120 --> 00:43:19,730
Γι 'αυτό πρόκειται να μην είναι 5.

883
00:43:19,730 --> 00:43:23,580
Βλέπουμε ότι το 1 είναι μικρότερη από 2, σωστά;

884
00:43:23,580 --> 00:43:32,970
Μέχρι τώρα γνωρίζουμε ότι οι ελάχιστες μας είναι
πρόκειται να είναι η τιμή του δείκτη κατά 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Ναι;

886
00:43:34,030 --> 00:43:39,170
Και στη συνέχεια, όταν μπορείτε να πάρετε εδώ κάτω,
μπορείτε να ανταλλάξετε τις σωστές τιμές.

887
00:43:39,170 --> 00:43:42,610
>> Έτσι, όταν παιδιά ήταν έχοντας μόλις το j
πριν, δεν ήσασταν κοιτάζοντας το ένα

888
00:43:42,610 --> 00:43:43,260
μετά από αυτό.

889
00:43:43,260 --> 00:43:44,520
Μπορείτε κοιτούσαν
η ίδια αξία, η οποία

890
00:43:44,520 --> 00:43:46,290
Γι 'αυτό ακριβώς δεν είχε κάνει τίποτα.

891
00:43:46,290 --> 00:43:49,721
Μήπως αυτό έχει νόημα για όλους,
Γι 'αυτό απαιτείται η συν 1 εκεί;

892
00:43:49,721 --> 00:43:50,220
ΕΝΤΆΞΕΙ.

893
00:43:50,220 --> 00:43:53,345
Τώρα ας τρέχει μέσα από αυτό να κάνει
ότι το υπόλοιπο του κώδικα είναι η σωστή.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Γιατί συμβαίνει;

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Αχ, αυτό είναι το λεπτό εδώ.

898
00:44:16,364 --> 00:44:17,780
Ήμασταν συγκρίνοντας την λάθος τιμή.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
Ωχ όχι.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Ω ναι, εδώ κάτω είμαστε
εναλλαγή λάθος τιμές, καθώς και.

903
00:44:33,482 --> 00:44:34,940
Επειδή ψάχναμε στο i και j.

904
00:44:34,940 --> 00:44:36,440
Αυτοί είναι εκείνοι που είχαν τον έλεγχο.

905
00:44:36,440 --> 00:44:39,160
Είμαστε πραγματικά θέλουν να ανταλλάξουν το
ελάχιστο, το τρέχον ελάχιστο,

906
00:44:39,160 --> 00:44:40,550
με ό, τι αυτό που είναι έξω.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
Και όπως εσείς μπορείτε να δείτε κάτω
Εδώ, έχουμε ένα ταξινομημένο πίνακα.

909
00:45:05,402 --> 00:45:07,110
Απλά είχε να κάνει με
το γεγονός ότι, όταν

910
00:45:07,110 --> 00:45:09,350
είχαμε τον έλεγχο της
αξίες μας σύγκρισης,

911
00:45:09,350 --> 00:45:11,226
Εμείς δεν έψαχναν τις σωστές τιμές.

912
00:45:11,226 --> 00:45:13,850
Ψάχναμε στο ίδιο αυτό
εδώ, στην πραγματικότητα δεν το αλλάζουν.

913
00:45:13,850 --> 00:45:17,135
Θα πρέπει να εξετάσουμε το ένα δίπλα
σε αυτό και, στη συνέχεια, μπορείτε να ανταλλάξετε.

914
00:45:17,135 --> 00:45:19,260
Έτσι, αυτό είναι ό, τι ήταν το είδος του
υποκλοπών κωδικό μας πριν.

915
00:45:19,260 --> 00:45:22,460
Και τι έκανα εδώ είναι το παν
το πρόγραμμα εντοπισμού σφαλμάτων θα μπορούσε να κάνει για σας

916
00:45:22,460 --> 00:45:23,810
Έκανα μόνο για το
του σκάφους, γιατί είναι πιο εύκολο

917
00:45:23,810 --> 00:45:26,320
για να δούμε, αντί να προσπαθούν
για να μεγεθύνετε το πρόγραμμα εντοπισμού σφαλμάτων.

918
00:45:26,320 --> 00:45:29,391
Μήπως αυτό έχει νόημα για όλους;

919
00:45:29,391 --> 00:45:29,890
Cool.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Εντάξει.

922
00:45:35,410 --> 00:45:41,070
Μπορούμε να προχωρήσουμε σε μιλάμε για
ασυμπτωτική σημειογραφία, η οποία

923
00:45:41,070 --> 00:45:44,580
είναι ακριβώς ένα φανταχτερό τρόπο λέγοντας ότι η
runtimes όλων αυτών των ειδών.

924
00:45:44,580 --> 00:45:47,650
Έτσι ξέρω Δαβίδ, στη διάλεξη,
έθιξε χρόνους εκτέλεσης.

925
00:45:47,650 --> 00:45:52,124
Και πήγε όλο το τύπο
για τον υπολογισμό των χρόνων εκτέλεσης.

926
00:45:52,124 --> 00:45:53,040
Μην ανησυχείτε γι 'αυτό.

927
00:45:53,040 --> 00:45:54,660
Εάν είστε πραγματικά περίεργος
σχετικά με τον τρόπο που λειτουργεί,

928
00:45:54,660 --> 00:45:55,810
διστάσετε να μου μιλήσει μετά το τμήμα.

929
00:45:55,810 --> 00:45:57,560
Μπορούμε να περπατήσετε μέσα
Οι τύποι μαζί.

930
00:45:57,560 --> 00:46:00,689
Αλλά όλοι εσείς έχετε πραγματικά
γνωρίζουμε είναι ότι n τετράγωνο πάνω από 2

931
00:46:00,689 --> 00:46:01,980
είναι το ίδιο πράγμα όπως n τετράγωνο.

932
00:46:01,980 --> 00:46:04,710
Επειδή το μεγαλύτερο αριθμό,
ο εκθέτης, μεγαλώνει περισσότερο.

933
00:46:04,710 --> 00:46:06,590
Και έτσι για τους σκοπούς μας,
μας νοιάζει

934
00:46:06,590 --> 00:46:09,470
είναι ότι η γιγαντιαία αριθμός που μεγαλώνει.

935
00:46:09,470 --> 00:46:13,340
>> Έτσι ποια είναι η καλύτερη περίπτωση
Διάρκεια της επιλογής του είδους;

936
00:46:13,340 --> 00:46:15,830
Εάν πρόκειται να έχουμε
για να μετακινηθείτε σε μια λίστα

937
00:46:15,830 --> 00:46:18,712
και, στη συνέχεια, διέτρεξε
το υπόλοιπο του εν λόγω καταλόγου,

938
00:46:18,712 --> 00:46:20,420
πόσες φορές είναι
Σκοπεύετε να πιθανώς,

939
00:46:20,420 --> 00:46:24,612
στη χειρότερη case-- στο
καλύτερη περίπτωση, sorry-- τρέχει μέσα;

940
00:46:24,612 --> 00:46:27,070
Ίσως η καλύτερη ερώτηση είναι
να ρωτήσω, ποια είναι η χειρότερη περίπτωση

941
00:46:27,070 --> 00:46:28,153
εκτέλεσης του είδους επιλογής.

942
00:46:28,153 --> 00:46:29,366
Κοινό: n τετράγωνο.

943
00:46:29,366 --> 00:46:30,740
ANDI PENG: Είναι n τετράγωνο, δεξιά.

944
00:46:30,740 --> 00:46:36,986
Έτσι, ένας εύκολος τρόπος για να σκεφτώ αυτό είναι σαν,
κάθε φορά που θα έχετε δύο ένθετα για βρόχους,

945
00:46:36,986 --> 00:46:38,110
πρόκειται να n τετράγωνο.

946
00:46:38,110 --> 00:46:40,386
Διότι όχι μόνο είστε
διατρέχει και πάλι,

947
00:46:40,386 --> 00:46:42,260
θα πρέπει να πάμε πίσω
γύρω και διασχίζουν

948
00:46:42,260 --> 00:46:44,980
και πάλι μέσα για κάθε τιμή.

949
00:46:44,980 --> 00:46:48,640
Έτσι, σε αυτή την περίπτωση, τρέχετε n
n φορές τετράγωνο, το οποίο is-- συγγνώμη,

950
00:46:48,640 --> 00:46:50,505
n n φορές, το οποίο ισούται με το Ν τετράγωνο.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> Και είδος είναι επίσης ένα κομμάτι
μοναδικό υπό την έννοια

953
00:46:56,360 --> 00:46:59,774
ότι δεν έχει σημασία, εφόσον αυτά
οι τιμές είναι ήδη σε τάξη.

954
00:46:59,774 --> 00:47:01,440
Είναι ακόμα πρόκειται να τρέχει μέσα ούτως ή άλλως.

955
00:47:01,440 --> 00:47:03,872
Ας πούμε απλά αυτό ήταν 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Ανεξάρτητα από το αν ήταν ή όχι σε
τάξη, ακόμα θα διέτρεχε

957
00:47:07,080 --> 00:47:08,620
και εξακολουθεί να ελέγξει την ελάχιστη τιμή.

958
00:47:08,620 --> 00:47:10,100
Θα έχουν κάνει το
ίδιο αριθμό των ελέγχων

959
00:47:10,100 --> 00:47:12,780
κάθε φορά, ακόμα και αν
δεν αγγίζει τίποτα.

960
00:47:12,780 --> 00:47:16,940
>> Έτσι, σε μια τέτοια περίπτωση, το καλύτερο και το χειρότερο
runtimes είναι πραγματικά ισοδύναμες.

961
00:47:16,940 --> 00:47:19,160
Έτσι, η αναμενόμενη αυτονομία
του είδους επιλογής,

962
00:47:19,160 --> 00:47:23,790
το οποίο έχουμε ορίσει με το σύμβολο
του θήτα, θήτα, στην περίπτωση αυτή,

963
00:47:23,790 --> 00:47:24,790
επίσης θα n τετράγωνο.

964
00:47:24,790 --> 00:47:26,480
Και τα τρία αυτά θα n τετράγωνο.

965
00:47:26,480 --> 00:47:29,653
Είναι σαφές σε όλους σχετικά με το γιατί
ο χρόνος εκτέλεσης είναι ν τετράγωνο;

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Εντάξει.

968
00:47:33,980 --> 00:47:39,120
Έτσι, είμαι απλώς πρόκειται να τρέξει γρήγορα
μέσα από το υπόλοιπο του είδους.

969
00:47:39,120 --> 00:47:41,137
Ο αλγόριθμος για
φούσκα sort-- θυμάστε,

970
00:47:41,137 --> 00:47:43,220
Αυτό ήταν η πρώτη
David πήγε πάνω στη διάλεξη.

971
00:47:43,220 --> 00:47:46,000
Ουσιαστικά, θα μπείτε
καθ 'όλη τη λίστα

972
00:47:46,000 --> 00:47:48,950
και εσείς απλά swap--
συγκρίνουν δύο σε έναν χρόνο.

973
00:47:48,950 --> 00:47:51,350
Και αν κάποιος είναι μεγαλύτερη,
από ό, τι ακριβώς τους swap.

974
00:47:51,350 --> 00:47:53,590
Έτσι, εφόσον αυτά είναι μεγαλύτερα, θα ανταλλάξουν.

975
00:47:53,590 --> 00:47:56,180
Έχω επίσημες εδώ.

976
00:47:56,180 --> 00:47:59,100
>> Έτσι, ας υποθέσουμε ότι είχατε 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Θα ήθελα να συγκρίνουν το 8 και 6.

978
00:48:00,571 --> 00:48:01,570
Μπορείτε Θα πρέπει να τα ανταλλάξουν.

979
00:48:01,570 --> 00:48:02,610
Θα συγκρίνετε τις 8 και 4.

980
00:48:02,610 --> 00:48:03,609
Μπορείτε Θα πρέπει να τα ανταλλάξουν.

981
00:48:03,609 --> 00:48:07,000
Αν πρέπει να ανταλλάξουν τα 8 και
το 2, να αλλάξει αυτούς.

982
00:48:07,000 --> 00:48:10,760
Έτσι, σε μια τέτοια αίσθηση, μπορείτε να δείτε,
παίζεται επί μακρά χρονική περίοδο,

983
00:48:10,760 --> 00:48:13,730
πώς το είδος των αξιών φούσκα
τα άκρα, η οποία είναι ο λόγος που το ονομάζουμε

984
00:48:13,730 --> 00:48:15,320
bubble sort.

985
00:48:15,320 --> 00:48:19,950
>> Θα τρέξει μόνο μέσω και πάλι σε
δεύτερο πέρασμα μας, και τρίτο πέρασμα μας,

986
00:48:19,950 --> 00:48:21,150
και το τέταρτο πέρασμα μας.

987
00:48:21,150 --> 00:48:25,820
Ουσιαστικά, φούσκα τρέχει μόνο είδος
μέχρι να μην κάνει πλέον καμία swaps.

988
00:48:25,820 --> 00:48:31,109
Έτσι, με αυτή την έννοια, αυτό είναι μόνο
η γενική ψευδοκώδικα για αυτό.

989
00:48:31,109 --> 00:48:32,650
Μην ανησυχείτε, όλα αυτά θα είναι σε απευθείας σύνδεση.

990
00:48:32,650 --> 00:48:34,990
Δεν έχουμε πραγματικά να πάει πάνω από αυτό.

991
00:48:34,990 --> 00:48:38,134
>> Εμείς απλά προετοιμάσει ένα μετρητή
μεταβλητή που ξεκινά από το 0.

992
00:48:38,134 --> 00:48:39,800
Και έχουμε επαναλάβει όλη την παράταξη.

993
00:48:39,800 --> 00:48:43,420
Και αν μία τιμή is-- εάν αυτό
η τιμή είναι μεγαλύτερη από την τιμή,

994
00:48:43,420 --> 00:48:44,610
θα πάμε να τους swap.

995
00:48:44,610 --> 00:48:46,860
Και τότε είστε απλά
πρόκειται να συνεχίσω.

996
00:48:46,860 --> 00:48:47,970
Και θα πάμε να μετρήσει.

997
00:48:47,970 --> 00:48:50,845
Και είστε ακριβώς πρόκειται να συνεχίσει να κάνει
αυτό, ενώ ο μετρητής είναι μεγαλύτερος

998
00:48:50,845 --> 00:48:53,345
από 0, που σημαίνει ότι
κάθε φορά που θα χρειαστεί να ανταλλάξουν,

999
00:48:53,345 --> 00:48:55,220
ξέρετε ότι θέλετε να πάτε
πίσω και ελέγξτε και πάλι.

1000
00:48:55,220 --> 00:48:59,510
Θέλετε να κρατήσει τον έλεγχο μέχρι να γνωρίζετε
ότι δεν έχετε να ανταλλάξουν πια.

1001
00:48:59,510 --> 00:49:05,570
>> Λοιπόν, τι είναι το καλύτερο και το χειρότερο
περίπτωση runtimes για bubble sort;

1002
00:49:05,570 --> 00:49:09,300
Και hint-- αυτό είναι πραγματικά διαφορετικό
από την ταξινόμηση με επιλογή, με την έννοια

1003
00:49:09,300 --> 00:49:11,810
ότι οι δύο αυτές απαντήσεις δεν είναι το ίδιο.

1004
00:49:11,810 --> 00:49:14,709
Σκεφτείτε τι θα συνέβαινε σε
μια περίπτωση κατά την οποία είχε ήδη διευθετηθεί.

1005
00:49:14,709 --> 00:49:16,500
Και σκεφτείτε τι
θα συνέβαινε αν ήταν

1006
00:49:16,500 --> 00:49:18,372
στην περίπτωση κατά την οποία δεν ήταν ταξινομημένο.

1007
00:49:18,372 --> 00:49:20,580
Και μπορείτε να εκτελέσετε το είδος του
μέσω της γιατί αυτό συμβαίνει.

1008
00:49:20,580 --> 00:49:22,954
Θα σας δώσω ρε παιδιά, όπως, 30
δευτερόλεπτα για να σκεφτούμε γι 'αυτό.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> ΕΝΤΆΞΕΙ.

1011
00:49:53,540 --> 00:49:57,462
Υπάρχει κάποιος που έχει μια εικασία σε αυτό που η
χειρότερη περίπτωση εκτέλεσης του bubble sort είναι;

1012
00:49:57,462 --> 00:49:57,962
Ναι.

1013
00:49:57,962 --> 00:50:07,810
>> Κοινό: Θα ήταν, όπως, n φορές
n μείον 1 ή κάτι τέτοιο;

1014
00:50:07,810 --> 00:50:10,650
Όπως, κάθε φορά που τρέχει,
είναι ακριβώς, όπως, ένα λιγότερο ανταλλαγής

1015
00:50:10,650 --> 00:50:10,960
πως ό, τι ήταν.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI PENG: Ναι, έτσι
είσαι εντελώς δεξιά.

1017
00:50:12,668 --> 00:50:15,940
Και αυτό είναι μια περίπτωση κατά την οποία σας
απάντηση ήταν στην πραγματικότητα πιο περίπλοκο

1018
00:50:15,940 --> 00:50:17,240
από αυτό που πρέπει να δώσουμε.

1019
00:50:17,240 --> 00:50:19,772
Έτσι, πρόκειται να είμαι run--
πρόκειται να διαγράψετε όλα αυτά εδώ.

1020
00:50:19,772 --> 00:50:20,480
Είναι όλοι καλά;

1021
00:50:20,480 --> 00:50:21,869
Μπορώ να σβήσω αυτό;

1022
00:50:21,869 --> 00:50:22,368
ΕΝΤΆΞΕΙ.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Θα πάμε να τρέχει μέσα από n
φορές την πρώτη φορά, έτσι δεν είναι;

1025
00:50:30,320 --> 00:50:33,200
Και θα πάμε να τρέχει μέσα
n μείον 1 δεύτερη φορά, σωστά;

1026
00:50:33,200 --> 00:50:37,130
Και μετά θα πάμε να κρατήσει
πρόκειται, Ν ορυχείο 2, κλπ.

1027
00:50:37,130 --> 00:50:40,210
Ο David έκανε αυτό σε μια διάλεξη, όπου,
αν αθροιστούν όλες αυτές τις αξίες,

1028
00:50:40,210 --> 00:50:48,080
μπορείτε να πάρετε κάτι που είναι like-- yeah--
πάνω από 2, το οποίο ουσιαστικά μειώνει μόνο

1029
00:50:48,080 --> 00:50:49,784
μέχρι ν τετράγωνο.

1030
00:50:49,784 --> 00:50:51,700
Θα πάμε για να πάρετε μια
Περίεργο κλάσμα εκεί.

1031
00:50:51,700 --> 00:50:53,892
Και έτσι απλά να ξέρετε ότι
το ν τετράγωνο πάντα

1032
00:50:53,892 --> 00:50:55,350
υπερισχύει το κλάσμα.

1033
00:50:55,350 --> 00:50:58,450
Και στην προκειμένη περίπτωση, το χειρότερο
runtime θα n τετράγωνο.

1034
00:50:58,450 --> 00:51:00,210
Αν ήταν σε φθίνουσα
Προκειμένου, νομίζω, θα

1035
00:51:00,210 --> 00:51:02,530
πρέπει να κάνει μια συμφωνία ανταλλαγής κάθε φορά.

1036
00:51:02,530 --> 00:51:05,170
>> Ποια θα ήταν, ενδεχομένως,
η καλύτερη περίπτωση εκτέλεσης;

1037
00:51:05,170 --> 00:51:08,580
Ας πούμε, αν η λίστα ήταν ήδη
προκειμένου, ποια θα είναι και ο χρόνος είναι;

1038
00:51:08,580 --> 00:51:09,565
>> Κοινό: n.

1039
00:51:09,565 --> 00:51:10,690
ANDI PENG: Είναι n, ακριβώς.

1040
00:51:10,690 --> 00:51:11,600
Και γιατί είναι ν?

1041
00:51:11,600 --> 00:51:13,850
Κοινό: Επειδή απλά
πρέπει να ελέγξετε σε κάθε φορά.

1042
00:51:13,850 --> 00:51:14,770
ANDI PENG: Ακριβώς.

1043
00:51:14,770 --> 00:51:17,150
Έτσι, με τον καλύτερο δυνατό χρόνο εκτέλεσης,
αν ο κατάλογος αυτός ήταν ήδη

1044
00:51:17,150 --> 00:51:20,270
sorted-- ας πούμε 1, 2, 3, 4-- σας
θα πήγαινε μέσα, θα ελέγχει,

1045
00:51:20,270 --> 00:51:21,720
θα δείτε, ω, όλοι τηγάνι έξω.

1046
00:51:21,720 --> 00:51:22,636
Δεν είχα να ανταλλάξουν.

1047
00:51:22,636 --> 00:51:23,370
Τελείωσα.

1048
00:51:23,370 --> 00:51:26,500
Έτσι, στην περίπτωση αυτή, είναι ακριβώς n
ή ο αριθμός των βημάτων που μόλις

1049
00:51:26,500 --> 00:51:29,870
Έπρεπε να κάνουν check-in στον πρώτο κατάλογο.

1050
00:51:29,870 --> 00:51:33,990
>> Και μετά, τώρα χτύπησε
ταξινόμηση με εισαγωγή, όπου

1051
00:51:33,990 --> 00:51:39,260
ο αλγόριθμος είναι ουσιαστικά να χάσμα
ότι σε μια διαλογή και χωρίς διαλογή τμήμα.

1052
00:51:39,260 --> 00:51:42,810
Και τότε ένα προς ένα,
οι τιμές είναι χωρίς διαλογή

1053
00:51:42,810 --> 00:51:46,880
εισάγονται σε κατάλληλα τους
θέσεις στην αρχή της λίστας.

1054
00:51:46,880 --> 00:51:52,120
>> Έτσι, για παράδειγμα, έχουμε ένα
κατάλογο των 3, 5, 2, 6, 4 και πάλι.

1055
00:51:52,120 --> 00:51:54,750
Γνωρίζουμε ότι είναι επί του παρόντος
αδιαχώριστα, γιατί έχουμε μόνο

1056
00:51:54,750 --> 00:51:57,030
άρχισε να ψάχνει σε αυτό.

1057
00:51:57,030 --> 00:52:00,610
Θα ρίξουμε μια ματιά και να γνωρίζουμε ότι
η πρώτη τιμή είναι ταξινομημένο, έτσι δεν είναι;

1058
00:52:00,610 --> 00:52:04,190
Αν ψάχνετε απλά σε μια σειρά από
Size One, ξέρετε ότι είναι ταξινομημένο.

1059
00:52:04,190 --> 00:52:08,230
>> Έτσι, τότε γνωρίζουμε ότι η
άλλα τέσσερα είναι αδιαχώριστα.

1060
00:52:08,230 --> 00:52:10,980
Έχουμε περάσει και να βλέπουμε αυτή την τιμή.

1061
00:52:10,980 --> 00:52:11,730
Ας πάμε πίσω.

1062
00:52:11,730 --> 00:52:13,130
Δείτε αυτή την τιμή 5;

1063
00:52:13,130 --> 00:52:14,110
Θα ρίξουμε μια ματιά σε αυτό.

1064
00:52:14,110 --> 00:52:15,204
Θα το συγκρίνουμε με 3.

1065
00:52:15,204 --> 00:52:17,870
Γνωρίζουμε ότι είναι μεγαλύτερη από ό, τι
3, έτσι ξέρουμε ότι αυτό είναι ταξινομημένο.

1066
00:52:17,870 --> 00:52:22,940
Έτσι τώρα ξέρουμε ότι οι δύο πρώτες
κατατάσσονται και τα τρία τελευταία δεν είναι.

1067
00:52:22,940 --> 00:52:24,270
>> Θα ρίξουμε μια ματιά στο 2.

1068
00:52:24,270 --> 00:52:25,720
Εμείς πρώτα να το ελέγξετε με 5.

1069
00:52:25,720 --> 00:52:26,700
Είναι λιγότερο από 5;

1070
00:52:26,700 --> 00:52:27,240
Δεν είναι.

1071
00:52:27,240 --> 00:52:29,510
Έτσι πρέπει να συνεχίσουμε κοιτάζοντας προς τα κάτω.

1072
00:52:29,510 --> 00:52:30,940
Στη συνέχεια, μπορείτε να ελέγξετε 2 εκτός 3.

1073
00:52:30,940 --> 00:52:31,850
Είναι λιγότερο από ό, τι;

1074
00:52:31,850 --> 00:52:32,350
Κανένα.

1075
00:52:32,350 --> 00:52:35,430
Έτσι, ξέρετε το 2 πρέπει να εισαχθεί
στην μπροστινή και 3 και 5

1076
00:52:35,430 --> 00:52:38,200
και οι δύο πρέπει να ωθείται προς τα έξω.

1077
00:52:38,200 --> 00:52:42,190
Κάνετε αυτό και πάλι με 6 και 4.

1078
00:52:42,190 --> 00:52:48,962
Και εμείς απλά να διατηρήσουν τον έλεγχο, κατ 'ουσίαν,
όπου απλά δείτε, έλεγχος, έλεγχος.

1079
00:52:48,962 --> 00:52:51,170
Και μέχρι να είναι προς τη σωστή
τη θέση, το είδος ακριβώς

1080
00:52:51,170 --> 00:52:54,890
τοποθετήστε το στη σωστή θέση,
η οποία είναι όπου το όνομα προήλθε.

1081
00:52:54,890 --> 00:52:59,830
>> Έτσι, αυτό είναι ακριβώς ο αλγόριθμος,
pseudocode per se, το είδος,

1082
00:52:59,830 --> 00:53:04,990
σχετικά με το πώς θα εφαρμόσουν
ένα είδος εισαγωγής.

1083
00:53:04,990 --> 00:53:05,954
Ψευδοκώδικας είναι εδώ.

1084
00:53:05,954 --> 00:53:06,620
Είναι όλα σε απευθείας σύνδεση.

1085
00:53:06,620 --> 00:53:10,720
Μην ανησυχείτε αν σας παιδιά
προσπαθεί να αντιγράψει αυτό κάτω.

1086
00:53:10,720 --> 00:53:14,500
Έτσι, για άλλη μια φορά, το ίδιο ποιες question--
θα ήταν το καλύτερο και το χειρότερο runtimes

1087
00:53:14,500 --> 00:53:16,120
για την ταξινόμηση με εισαγωγή;

1088
00:53:16,120 --> 00:53:17,750
Είναι πολύ παρόμοια με την τελευταία ερώτηση.

1089
00:53:17,750 --> 00:53:20,479
Θα σας δώσω ρε παιδιά, όπως, 30
δευτερόλεπτα για να σκεφτούμε γι 'αυτό, καθώς και.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> ΟΚ Υπάρχει κάποιος που θέλει να
δώσε μου το χειρότερο χρόνου εκτέλεσης;

1092
00:53:50,071 --> 00:53:50,570
Ναι.

1093
00:53:50,570 --> 00:53:51,490
>> Κοινό: n τετράγωνο.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI PENG: Είναι n τετράγωνο.

1095
00:53:52,573 --> 00:53:53,730
Και γιατί ν τετράγωνο;

1096
00:53:53,730 --> 00:53:57,562
>> Κοινό: Επειδή σε
αντίστροφη σειρά, έχετε

1097
00:53:57,562 --> 00:54:02,619
να περάσουν από n n φορές, πράγμα που is--

1098
00:54:02,619 --> 00:54:03,660
ANDI PENG: Ναι, ακριβώς.

1099
00:54:03,660 --> 00:54:06,610
Έτσι ίδιο πράγμα όπως και το είδος φούσκα.

1100
00:54:06,610 --> 00:54:08,720
Εάν αυτή η λίστα είναι σε
φθίνουσα σειρά, είστε

1101
00:54:08,720 --> 00:54:11,240
Θα πρέπει να ελέγξετε πρώτα μία φορά.

1102
00:54:11,240 --> 00:54:13,470
Και στη συνέχεια, με κάθε
πρόσθετη αξία, είστε

1103
00:54:13,470 --> 00:54:16,390
θα πρέπει να το ελέγξετε κατά
κάθε τιμή, σωστά;

1104
00:54:16,390 --> 00:54:20,290
Και έτσι συνολικά, θα πάμε για να κάνει
ένα n φορές πάσα άλλη ν Pass,

1105
00:54:20,290 --> 00:54:21,750
n είναι τετράγωνο.

1106
00:54:21,750 --> 00:54:22,860
Τι γίνεται στην καλύτερη περίπτωση;

1107
00:54:22,860 --> 00:54:24,360
Ναι.

1108
00:54:24,360 --> 00:54:28,840
>> Κοινό: n μείον 1, επειδή η
πρώτο είναι ήδη στο τετράγωνο.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI PENG: Λοιπόν, κοντά.

1110
00:54:30,270 --> 00:54:31,850
Η απάντηση είναι στην πραγματικότητα n.

1111
00:54:31,850 --> 00:54:37,189
Διότι, ενώ το πρώτο είναι
ταξινομημένο, δεν μπορεί να actually--

1112
00:54:37,189 --> 00:54:38,980
εμείς απλά lucked έξω, σε
το παράδειγμα αυτό, ότι 2

1113
00:54:38,980 --> 00:54:40,930
έτυχε να είναι ο μικρότερος αριθμός.

1114
00:54:40,930 --> 00:54:43,680
Αλλά αυτό δεν θα είναι πάντα η περίπτωση.

1115
00:54:43,680 --> 00:54:48,040
Εάν 2 είναι ήδη ταξινομημένο στην αρχή
αλλά θα δούμε και υπάρχει εδώ 1,

1116
00:54:48,040 --> 00:54:49,144
το 1 πρόκειται να το χτύπημα.

1117
00:54:49,144 --> 00:54:51,060
Και αυτό πρόκειται να καταλήξει
μέχρι να ανεβαίνει ούτως ή άλλως.

1118
00:54:51,060 --> 00:54:56,250
>> Έτσι, στην καλύτερη περίπτωση,
στην πραγματικότητα είναι ακριβώς πρόκειται να είναι n.

1119
00:54:56,250 --> 00:54:59,090
Εάν έχετε 1, 2, 3,
4, 5, 6, 7, 8, είστε

1120
00:54:59,090 --> 00:55:00,940
πρόκειται να τρέξει μέσα
ότι ολόκληρη η λίστα φορά

1121
00:55:00,940 --> 00:55:03,430
για να ελέγξετε για να δείτε αν όλα είναι μια χαρά.

1122
00:55:03,430 --> 00:55:07,390
Είναι σαφές σε όλους σε λειτουργία
φορές από την επιλογή, καθώς;

1123
00:55:07,390 --> 00:55:09,960
Ξέρω ότι περνάω
Αυτά είναι πραγματικά γρήγορα.

1124
00:55:09,960 --> 00:55:13,330
Αλλά απλά να ξέρετε ότι αν γνωρίζετε το
γενικές έννοιες, θα πρέπει να είναι καλό.

1125
00:55:13,330 --> 00:55:16,070
ΕΝΤΆΞΕΙ.

1126
00:55:16,070 --> 00:55:19,790
Γι 'αυτό θα σας δώσω τα παιδιά ίσως, όπως,
ένα λεπτό για να μιλήσουμε με τους γείτονές σας

1127
00:55:19,790 --> 00:55:21,890
σχετικά με το τι είναι μερικά μόνο
από τις βασικές διαφορές

1128
00:55:21,890 --> 00:55:23,540
μεταξύ αυτών των τύπων των ειδών.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Θα πάμε πάνω ότι σύντομα.

1131
00:56:25,570 --> 00:56:26,444
Κοινό: Ω, εντάξει.

1132
00:56:26,444 --> 00:56:27,320
ANDI PENG: Ναι.

1133
00:56:27,320 --> 00:56:28,380
ΕΝΤΆΞΕΙ.

1134
00:56:28,380 --> 00:56:33,420
Cool, ας συνέλθει εκ νέου σε μια τάξη.

1135
00:56:33,420 --> 00:56:34,330
ΕΝΤΆΞΕΙ.

1136
00:56:34,330 --> 00:56:37,579
Έτσι, αυτό ήταν το είδος του ένα
ανοιχτή ερώτηση, με την έννοια

1137
00:56:37,579 --> 00:56:39,120
ότι υπάρχουν πολλά απαντήσεις σε αυτά.

1138
00:56:39,120 --> 00:56:40,746
Και θα πάμε πάνω από κάποια από αυτά για λίγο.

1139
00:56:40,746 --> 00:56:43,411
Ήθελα απλώς να σας πάρει τα παιδιά
σκεφτόμαστε τι διαφοροποιούνται

1140
00:56:43,411 --> 00:56:44,530
και οι τρεις τύποι των ειδών.

1141
00:56:44,530 --> 00:56:47,440
Και άκουσα, επίσης, μια μεγάλη
question-- τι κάνει ταξινόμηση με συγχώνευση κάνω;

1142
00:56:47,440 --> 00:56:50,110
Μεγάλη ερώτηση, γιατί αυτό είναι
τι είμαστε καλύπτει την επόμενη.

1143
00:56:50,110 --> 00:56:52,850
>> Έτσι, ταξινόμηση με συγχώνευση είναι η
ένα είδος που να λειτουργεί

1144
00:56:52,850 --> 00:56:56,100
πολύ διαφορετικό από τα άλλα είδη.

1145
00:56:56,100 --> 00:56:58,180
Όπως εσείς να see--
έκανε ο David κάνει αυτό το demo

1146
00:56:58,180 --> 00:57:01,130
όπου είχε όλα τα δροσερά
θορύβους του βλέποντας πώς να συγχωνεύσει

1147
00:57:01,130 --> 00:57:04,010
Ταξινόμηση έτρεξε, όπως, απείρως
ταχύτερα από τους άλλους δύο τύπους;

1148
00:57:04,010 --> 00:57:04,510
ΕΝΤΆΞΕΙ.

1149
00:57:04,510 --> 00:57:07,580
Έτσι, αυτό είναι επειδή συγχώνευσης
Ταξινόμηση υλοποιεί αυτό το χάσμα

1150
00:57:07,580 --> 00:57:11,020
και να κατακτήσει την έννοια που έχουμε
μίλησε για πολλά στη διάλεξη.

1151
00:57:11,020 --> 00:57:14,550
Υπό αυτή την έννοια που ήθελαν να εργαστούν
εξυπνότερα, όχι σκληρότερα, όταν διαιρείτε

1152
00:57:14,550 --> 00:57:18,120
και να κατακτήσουν τα προβλήματα, και να σπάσει τους
προς τα κάτω, και στη συνέχεια να τα βάλει μαζί,

1153
00:57:18,120 --> 00:57:19,930
καλά πράγματα συμβαίνουν πάντα.

1154
00:57:19,930 --> 00:57:21,960
>> Έτσι, με τον τρόπο που συγχωνεύονται
Ταξινόμηση λειτουργεί ουσιαστικά

1155
00:57:21,960 --> 00:57:24,660
είναι ότι χωρίζει μια
αδιαχώριστα σειρά κατά το ήμισυ.

1156
00:57:24,660 --> 00:57:26,500
Και τότε πήρε δύο ημίχρονα των συστοιχιών.

1157
00:57:26,500 --> 00:57:28,220
Και ταξινομεί ακριβώς αυτά τα δύο μισά.

1158
00:57:28,220 --> 00:57:31,750
Κρατά μόνο τη διαίρεση κατά το ήμισυ, σε
ήμισυ, κατά το ήμισυ, έως ότου όλα ταξινομημένο

1159
00:57:31,750 --> 00:57:33,680
και, στη συνέχεια, αναδρομικά
βάζει όλα μαζί.

1160
00:57:33,680 --> 00:57:36,550
>> Έτσι, αυτό είναι πραγματικά αφηρημένη.

1161
00:57:36,550 --> 00:57:38,750
Έτσι, αυτό είναι απλά ένα κομμάτι του ψευδοκώδικα.

1162
00:57:38,750 --> 00:57:41,040
Μήπως αυτό έχει νόημα σε
ο τρόπος που τρέχει;

1163
00:57:41,040 --> 00:57:43,870
Έτσι, ας πούμε ότι έχετε ένα
σειρά από n στοιχεία, σωστά;

1164
00:57:43,870 --> 00:57:45,450
Εάν n είναι μικρότερη από 2, μπορείτε να επιστρέψετε.

1165
00:57:45,450 --> 00:57:49,040
Επειδή ξέρετε ότι αν υπάρχει
μόνο ένα πράγμα, πρέπει να ταξινομηθούν.

1166
00:57:49,040 --> 00:57:52,600
Αλλιώς, μπορείτε να ταξινομήσετε το αριστερό μισό,
και, στη συνέχεια, μπορείτε να ταξινομήσετε το δεξί μισό,

1167
00:57:52,600 --> 00:57:54,140
και στη συνέχεια θα συγχωνευθούν.

1168
00:57:54,140 --> 00:57:56,979
>> Έτσι, ενώ φαίνεται ότι πραγματικά εύκολη,
στην πραγματικότητα, να σκεφτόμαστε ότι είναι

1169
00:57:56,979 --> 00:58:00,270
είδος δύσκολο. Επειδή είστε όπως,
Λοιπόν, αυτό είναι το είδος του τρεξίματος στον εαυτό της.

1170
00:58:00,270 --> 00:58:00,769
Σωστά;

1171
00:58:00,769 --> 00:58:02,430
Είναι τρέχει στον εαυτό της.

1172
00:58:02,430 --> 00:58:05,479
Έτσι, με αυτή την έννοια, ο Δαβίδ άγγιξε
κατά την αναδρομή στην τάξη.

1173
00:58:05,479 --> 00:58:07,270
Και αυτή είναι μια έννοια
θα μιλήσουμε για περισσότερα.

1174
00:58:07,270 --> 00:58:11,430
Είναι ότι αυτό, αυτές οι δύο γραμμές
εδώ, στην πραγματικότητα είναι μόνο το πρόγραμμα

1175
00:58:11,430 --> 00:58:13,860
λέγοντάς του να τρέξει η ίδια
με διαφορετική είσοδο.

1176
00:58:13,860 --> 00:58:17,230
Έτσι, αντί να τρέξει μόνο με
το σύνολο των n στοιχεία,

1177
00:58:17,230 --> 00:58:20,530
μπορείτε να το σπάσει σε η
αριστερό μισό και το δεξιό ήμισυ

1178
00:58:20,530 --> 00:58:22,680
και στη συνέχεια να εκτελέσετε ξανά.

1179
00:58:22,680 --> 00:58:26,050
>> Και τότε θα δούμε οπτικά,
επειδή είμαι ένας οπτικός τύπος.

1180
00:58:26,050 --> 00:58:27,270
Λειτουργεί καλύτερα για μένα.

1181
00:58:27,270 --> 00:58:29,890
Έτσι θα δούμε σε ένα οπτικό παράδειγμα εδώ.

1182
00:58:29,890 --> 00:58:36,237
>> Ας πούμε ότι έχουμε μια σειρά, έξι
στοιχεία, 3, 5, 2, 6, 4, 1, δεν ταξινομούνται.

1183
00:58:36,237 --> 00:58:37,820
Εντάξει, υπάρχουν πολλά σε αυτή τη σελίδα.

1184
00:58:37,820 --> 00:58:43,179
Έτσι, αν εσείς μπορείτε να δείτε το
το πρώτο βήμα εδώ, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
μπορείτε να τεμαχιστεί σε δύο ημιμόρια.

1186
00:58:44,220 --> 00:58:45,976
Έχετε 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Γνωρίζετε ότι αυτά σας aren't--
Δεν ξέρω αν είναι ταξινομημένο ή μη,

1188
00:58:48,850 --> 00:58:52,517
έτσι ώστε να κρατήσει το σπάσιμο τους κάτω, στη μέση,
σε ένα δεύτερο, κατά το ήμισυ, μέχρι τελικά,

1189
00:58:52,517 --> 00:58:53,600
έχετε μόνο ένα στοιχείο.

1190
00:58:53,600 --> 00:58:56,790
Και ένα στοιχείο ταξινομείται πάντα, σωστά;

1191
00:58:56,790 --> 00:59:01,560
>> Γνωρίζουμε, λοιπόν, ότι το 3, 5, 2, 4, 6,
1, από μόνες τους, ταξινομούνται.

1192
00:59:01,560 --> 00:59:05,870
Και τώρα μπορούμε να τα βάλει μαζί πίσω.

1193
00:59:05,870 --> 00:59:07,510
Γνωρίζουμε, λοιπόν, το 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Έχουμε βάλει μαζί εκείνους.

1195
00:59:08,510 --> 00:59:09,617
Γνωρίζουμε ότι είναι ταξινομημένο.

1196
00:59:09,617 --> 00:59:10,450
Τα 2 είναι ακόμα εκεί.

1197
00:59:10,450 --> 00:59:11,830
Μπορούμε να βάλουμε το 4 και το 6 μαζί.

1198
00:59:11,830 --> 00:59:13,996
Γνωρίζουμε ότι αυτό είναι ταξινομημένο,
έτσι βάλαμε ότι μαζί.

1199
00:59:13,996 --> 00:59:14,940
Και το 1 είναι εκεί.

1200
00:59:14,940 --> 00:59:18,720
>> Και τότε θα εξετάσουμε μόνο
Αυτά τα δύο μισά ακριβώς εδώ.

1201
00:59:18,720 --> 00:59:21,300
Έχετε το 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Μπορείτε να συγκρίνετε μόνο η
αρχή των πάντων.

1203
00:59:23,465 --> 00:59:26,340
Επειδή ξέρετε ότι αυτό είναι ταξινομημένο
και ξέρετε ότι αυτό είναι ταξινομημένο.

1204
00:59:26,340 --> 00:59:29,360
Μέχρι τότε δεν χρειάζεται καν να
συγκρίνετε το 5, που μόλις συγκρίνετε τις 3.

1205
00:59:29,360 --> 00:59:32,070
Και το 2 είναι μικρότερη από 3, έτσι
Ξέρετε 2 πρέπει να πάτε στο τέλος.

1206
00:59:32,070 --> 00:59:33,120
>> Το ίδιο πράγμα εκεί.

1207
00:59:33,120 --> 00:59:34,740
Το 1 πρέπει να πάτε εδώ.

1208
00:59:34,740 --> 00:59:37,330
Και στη συνέχεια, όταν θα πάτε να βάλετε
αυτές οι δύο τιμές μαζί,

1209
00:59:37,330 --> 00:59:39,950
ξέρετε ότι αυτό διαλέγεται και
ξέρετε ότι αυτό είναι ταξινομημένο.

1210
00:59:39,950 --> 00:59:43,240
Έτσι, τότε το 1 και το
2, το 1 είναι μικρότερη από 2.

1211
00:59:43,240 --> 00:59:45,570
Αυτό σας λέει ότι το 1
θα πρέπει να πάτε στο τέλος αυτής της

1212
00:59:45,570 --> 00:59:47,480
χωρίς καν να κοιτάζει 3 ή 5.

1213
00:59:47,480 --> 00:59:50,100
Και τότε το 4, μπορείτε απλά
ελέγξτε, πηγαίνει δεξιά εδώ.

1214
00:59:50,100 --> 00:59:51,480
Δεν χρειάζεται να εξετάσουμε το 5.

1215
00:59:51,480 --> 00:59:52,570
Το ίδιο πράγμα με το 6.

1216
00:59:52,570 --> 00:59:55,860
Γνωρίζετε ότι το 6-- ακριβώς
δεν πρέπει να εξεταστούν.

1217
00:59:55,860 --> 00:59:57,870
>> Και έτσι με αυτό τον τρόπο, είστε
μόνο εξοικονόμηση εαυτό σας

1218
00:59:57,870 --> 00:59:59,526
πολλά βήματα όταν είστε σύγκριση.

1219
00:59:59,526 --> 01:00:02,150
Δεν πρέπει να συγκρίνουμε κάθε
στοιχείο έναντι άλλων στοιχείων.

1220
01:00:02,150 --> 01:00:05,230
Απλά συγκρίνετε με αυτά
ότι θα πρέπει να το συγκρίνετε με.

1221
01:00:05,230 --> 01:00:06,870
Έτσι, αυτό είναι το είδος της μια αφηρημένη έννοια.

1222
01:00:06,870 --> 01:00:10,540
Μην ανησυχείτε αν δεν είναι
αρκετά χτύπημα σας αμέσως ακόμα.

1223
01:00:10,540 --> 01:00:14,740
Αλλά γενικά, αυτό είναι
πώς ένα είδος συγχώνευσης λειτουργεί.

1224
01:00:14,740 --> 01:00:17,750
Ερωτήσεις, γρήγορες ερωτήσεις,
πριν προχωρήσω;

1225
01:00:17,750 --> 01:00:18,550
Ναι.

1226
01:00:18,550 --> 01:00:22,230
>> Κοινό: Έτσι σας είπε ότι έχετε λάβει
η 1, και στη συνέχεια το 4, και το 6

1227
01:00:22,230 --> 01:00:23,860
και να τους θέσει σε.

1228
01:00:23,860 --> 01:00:26,800
Έτσι δεν είναι those-- δεν
κοιτάτε τους

1229
01:00:26,800 --> 01:00:28,544
ως χωριστά στοιχεία, όχι ως το σύνολο;

1230
01:00:28,544 --> 01:00:29,210
ANDI PENG: Ναι.

1231
01:00:29,210 --> 01:00:32,020
Έτσι τι συμβαίνει
είναι ότι βασικά

1232
01:00:32,020 --> 01:00:33,650
δημιουργούν ένα ολοκαίνουργιο σειρά.

1233
01:00:33,650 --> 01:00:36,690
Έτσι, ξέρετε ότι, εδώ, έχω
δύο σειρές μεγέθους 3, σωστά;

1234
01:00:36,690 --> 01:00:39,600
Έτσι ξέρετε ότι ταξινομημένο πίνακα μου
πρέπει να έχει έξι στοιχεία.

1235
01:00:39,600 --> 01:00:42,270
Έτσι, μπορείτε απλά να δημιουργήσετε ένα
νέα ποσότητα μνήμης.

1236
01:00:42,270 --> 01:00:44,270
Έτσι είστε κάτι σαν
είναι σπάταλη της μνήμης,

1237
01:00:44,270 --> 01:00:46,186
αλλά αυτό δεν έχει σημασία
επειδή είναι τόσο μικρό.

1238
01:00:46,186 --> 01:00:48,590
Έτσι θα δούμε την 1
και κοιτάς το 2.

1239
01:00:48,590 --> 01:00:50,770
Και ξέρετε ότι το 1 είναι μικρότερη από 2.

1240
01:00:50,770 --> 01:00:53,840
Έτσι ξέρετε ότι 1 θα πρέπει να πάει στο
η αρχή όλων εκείνων.

1241
01:00:53,840 --> 01:00:55,850
>> Δεν χρειάζεται καν να
εξετάσουμε το 3 και το 5.

1242
01:00:55,850 --> 01:00:57,400
Έτσι, ξέρετε 1 πηγαίνει εκεί.

1243
01:00:57,400 --> 01:00:59,300
Στη συνέχεια, μπορείτε βασικά μπριζόλα από το 1.

1244
01:00:59,300 --> 01:01:00,370
Είναι, όπως, νεκρός για εμάς.

1245
01:01:00,370 --> 01:01:03,690
Στη συνέχεια, έχουμε μόνο 2,
3, 5, και στη συνέχεια 4 και 6.

1246
01:01:03,690 --> 01:01:06,270
Και τότε ξέρετε ότι μπορείτε
συγκρίνουν το 4 και το 2,

1247
01:01:06,270 --> 01:01:07,560
Ω, η 2 θα πρέπει να πάει εκεί.

1248
01:01:07,560 --> 01:01:09,685
Έτσι θα γδούπο το 2 κάτω, να το κόψουν.

1249
01:01:09,685 --> 01:01:12,060
Έτσι, τότε θα πρέπει το 3
και το 5 στο 4 και στο 6.

1250
01:01:12,060 --> 01:01:14,650
Και απλά να κρατήσει μακριά κοπής
μέχρι να τους βάλει στην σειρά.

1251
01:01:14,650 --> 01:01:17,110
>> Κοινό: Έτσι είστε πάντα απλά
συγκρίνοντας την [δεν ακούγεται];

1252
01:01:17,110 --> 01:01:17,710
>> ANDI PENG: Ακριβώς.

1253
01:01:17,710 --> 01:01:19,590
Έτσι, με αυτή την έννοια, είστε
ακριβώς συγκρίνοντας, κατ 'ουσίαν,

1254
01:01:19,590 --> 01:01:21,240
έναν αριθμό έναντι του άλλου αριθμού.

1255
01:01:21,240 --> 01:01:22,990
Και επειδή ξέρετε
ότι είναι ταξινομημένο, μπορείτε

1256
01:01:22,990 --> 01:01:24,350
Δεν χρειάζεται να κοιτάξετε μέσα
όλους τους αριθμούς.

1257
01:01:24,350 --> 01:01:25,870
Απλά πρέπει να εξετάσουμε την πρώτη.

1258
01:01:25,870 --> 01:01:27,582
Και τότε μπορείτε να γδούπο μόνο
τα κάτω, επειδή ξέρετε

1259
01:01:27,582 --> 01:01:29,640
ανήκουν και οι οποίοι πρέπει να ανήκουν.

1260
01:01:29,640 --> 01:01:31,030
Ναι.

1261
01:01:31,030 --> 01:01:32,920
Καλή ερώτηση.

1262
01:01:32,920 --> 01:01:35,290
>> Και τότε, αν κάποιος από εσάς
είναι λίγο φιλόδοξο,

1263
01:01:35,290 --> 01:01:38,660
διστάσετε να δούμε αυτόν τον κώδικα.

1264
01:01:38,660 --> 01:01:40,680
Αυτό είναι στην πραγματικότητα ο
φυσική εφαρμογή

1265
01:01:40,680 --> 01:01:42,150
για το πώς θα γράφαμε ταξινόμηση με συγχώνευση.

1266
01:01:42,150 --> 01:01:44,070
Και μπορείτε να δείτε, είναι πολύ μικρή.

1267
01:01:44,070 --> 01:01:46,310
Αλλά οι ιδέες πίσω
αυτό είναι αρκετά περίπλοκη.

1268
01:01:46,310 --> 01:01:50,865
Έτσι, εάν αισθάνεστε σαν σχέδιο αυτό έξω
στο σπίτι σας απόψε, μην διστάσετε να.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> ΕΝΤΆΞΕΙ.

1271
01:01:54,740 --> 01:01:58,070
Έτσι ο Δαβίδ και πήγε πάνω από αυτό στη διάλεξη.

1272
01:01:58,070 --> 01:02:00,660
Ποια είναι η καλύτερη περίπτωση
runtimes, χειρότερη περίπτωση χρόνων εκτέλεσης,

1273
01:02:00,660 --> 01:02:05,680
και τα αναμενόμενα χρόνους εκτέλεσης της συγχώνευσης του είδους;

1274
01:02:05,680 --> 01:02:07,260
Ένα ζευγάρι δευτερόλεπτα για να σκεφτούμε.

1275
01:02:07,260 --> 01:02:11,198
Αυτό είναι αρκετά δύσκολο, αλλά το είδος του
διαισθητική αν το σκεφτείς.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Εντάξει.

1278
01:02:23,054 --> 01:02:25,269
>> Κοινό: Είναι η χειρότερη περίπτωση n log n;

1279
01:02:25,269 --> 01:02:26,060
ANDI PENG: Ακριβώς.

1280
01:02:26,060 --> 01:02:29,380
Και γιατί είναι n log n.

1281
01:02:29,380 --> 01:02:32,230
>> Κοινό: Δεν είναι επειδή
γίνεται εκθετικά πιο γρήγορα,

1282
01:02:32,230 --> 01:02:35,390
έτσι είναι σαν συνάρτηση του ότι
αντί απλώς να είναι απλώς ν

1283
01:02:35,390 --> 01:02:37,529
τετράγωνο ή κάτι τέτοιο;

1284
01:02:37,529 --> 01:02:38,320
ANDI PENG: Ακριβώς.

1285
01:02:38,320 --> 01:02:40,750
Έτσι, ο λόγος για τον οποίο η
Runtime σε αυτό είναι n log

1286
01:02:40,750 --> 01:02:44,310
n είναι because-- τι είσαι
κάνει σε όλα αυτά τα βήματα;

1287
01:02:44,310 --> 01:02:46,190
Είσαι απλά κόψιμο στο μισό, σωστά;

1288
01:02:46,190 --> 01:02:48,750
Και έτσι, όταν κάνουμε το
συνδεθείτε, το μόνο που θα κάνει

1289
01:02:48,750 --> 01:02:53,150
μοιράζει ένα πρόβλημα στη μέση,
σε ένα δεύτερο, κατά το ήμισυ, σε περισσότερα μέρη.

1290
01:02:53,150 --> 01:02:56,430
Και με αυτή την έννοια, μπορείτε να το είδος
από την εξάλειψη του γραμμικού μοντέλου

1291
01:02:56,430 --> 01:02:57,510
ότι έχουμε χρησιμοποιήσει.

1292
01:02:57,510 --> 01:03:00,254
Γιατί όταν εσείς μπριζόλα
τα πράγματα στη μέση, αυτό είναι ένα αρχείο καταγραφής.

1293
01:03:00,254 --> 01:03:02,420
Αυτό είναι μόνο η μαθηματική
τρόπος εκπροσωπούν.

1294
01:03:02,420 --> 01:03:06,310
>> Και στη συνέχεια, τέλος, στο τέλος, είστε
απλά κάνοντας ένα τελευταίο πέρασμα από

1295
01:03:06,310 --> 01:03:07,930
να θέσει όλα αυτά με τη σειρά, έτσι δεν είναι;

1296
01:03:07,930 --> 01:03:10,330
Και έτσι, αν απλά πρέπει να
ελέγχει ένα πράγμα, αυτό είναι ν.

1297
01:03:10,330 --> 01:03:13,420
Και έτσι είστε το είδος του
πολλαπλασιάζοντας τα δύο μαζί.

1298
01:03:13,420 --> 01:03:17,660
Έτσι είναι σαν να έχεις αυτόν τον τελικό
ελέγξτε για Ν εδώ κάτω με ένα αρχείο καταγραφής των n

1299
01:03:17,660 --> 01:03:18,390
μέχρι εδώ.

1300
01:03:18,390 --> 01:03:21,060
Και αν πολλαπλασιάσετε
τους, ότι είναι n log n.

1301
01:03:21,060 --> 01:03:26,100
>> Και έτσι η καλύτερη περίπτωση και το χειρότερο
υπόθεσης και αναμένεται όλοι n log n.

1302
01:03:26,100 --> 01:03:27,943
Είναι, επίσης, όπως και ένα άλλο είδος.

1303
01:03:27,943 --> 01:03:30,090
Είναι σαν είδος επιλογής
με την έννοια ότι το

1304
01:03:30,090 --> 01:03:32,131
Δεν έχει σημασία τι σας
κατάλογος είναι, είναι ακριβώς πρόκειται

1305
01:03:32,131 --> 01:03:34,801
να κάνουν το ίδιο πράγμα κάθε φορά.

1306
01:03:34,801 --> 01:03:35,300
ΕΝΤΆΞΕΙ.

1307
01:03:35,300 --> 01:03:39,950
Έτσι, όπως μπορείτε να δείτε τα παιδιά, ακόμη και αν
τα είδη που έχουμε πάει through-- n

1308
01:03:39,950 --> 01:03:41,660
τετράγωνο, δεν είναι πολύ αποτελεσματική.

1309
01:03:41,660 --> 01:03:47,060
Και ακόμα και αυτή η log η είναι
δεν είναι η πιο αποτελεσματική.

1310
01:03:47,060 --> 01:03:49,720
Αν εσείς είστε περίεργοι,
υπάρχει μηχανισμοί ταξινόμησης

1311
01:03:49,720 --> 01:03:54,310
που είναι τόσο αποτελεσματική ώστε να είναι
σχεδόν ουσιαστικά επίπεδη στο χρόνο εκτέλεσης.

1312
01:03:54,310 --> 01:03:55,420
>> Έχετε κάποιο ημερολόγιο του n.

1313
01:03:55,420 --> 01:03:58,190
Έχετε κάποιο log n του αρχείου καταγραφής.

1314
01:03:58,190 --> 01:04:00,330
Εμείς δεν αγγίζουν τους
σε αυτή την κατηγορία αυτή τη στιγμή.

1315
01:04:00,330 --> 01:04:02,663
Αλλά αν εσείς είστε περίεργοι,
διστάσετε να google, τι είναι

1316
01:04:02,663 --> 01:04:04,392
Τα πιο αποτελεσματικούς μηχανισμούς διαλογής.

1317
01:04:04,392 --> 01:04:06,350
Δεν ξέρω, υπάρχουν
μερικά πραγματικά αστεία αυτά,

1318
01:04:06,350 --> 01:04:09,860
like-- υπάρχει κάποια πραγματικά
αστεία αυτά που κάνουν οι άνθρωποι.

1319
01:04:09,860 --> 01:04:12,210
Και αναρωτιέστε πώς
Σκέφτηκες ποτέ ότι.

1320
01:04:12,210 --> 01:04:15,730
Έτσι google, αν έχετε κάποια ανταλλακτικά
ώρα, για, ποια είναι μερικά αστεία τρόπους

1321
01:04:15,730 --> 01:04:17,730
ότι people-- καθώς
αποτελεσματική ways-- άνθρωποι

1322
01:04:17,730 --> 01:04:20,371
ήταν σε θέση να εφαρμόσουν τα είδη.

1323
01:04:20,371 --> 01:04:20,870
ΕΝΤΆΞΕΙ.

1324
01:04:20,870 --> 01:04:22,880
Και εδώ είναι απλά ένα πρακτικό μικρό διάγραμμα.

1325
01:04:22,880 --> 01:04:26,850
Ξέρω ότι όλοι σας, πριν από την κουίζ 0,
θα είναι στο δωμάτιό σας, προσπαθώντας πιθανώς

1326
01:04:26,850 --> 01:04:27,960
να απομνημονεύσετε αυτό.

1327
01:04:27,960 --> 01:04:30,940
Έτσι, αυτό είναι ωραίο εκεί για σας παιδιά.

1328
01:04:30,940 --> 01:04:37,120
Απλά μην ξεχάσετε τη λογική που made--
γιατί αυτοί οι αριθμοί συνέβαιναν.

1329
01:04:37,120 --> 01:04:39,870
Εάν είστε πάντα χαθεί, απλά κάνει
βεβαιωθείτε ότι γνωρίζετε ποια είναι τα είδη.

1330
01:04:39,870 --> 01:04:40,820
Και μπορείτε να εκτελέσετε μέσα
τους στο μυαλό σας

1331
01:04:40,820 --> 01:04:42,903
να καταλάβω γιατί εκείνοι
απαντήσεις είναι οι απαντήσεις.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Εντάξει.

1334
01:04:47,600 --> 01:04:49,680
Έτσι θα πάμε να προχωρήσουμε
σε, τελικά, να αναζήτηση.

1335
01:04:49,680 --> 01:04:51,638
Διότι όπως εκείνους από εσάς
που έχουν διαβάσει το PSET,

1336
01:04:51,638 --> 01:04:55,175
αναζήτηση είναι επίσης μέρος του
το πρόβλημα αυτής της εβδομάδας θέτει.

1337
01:04:55,175 --> 01:04:57,300
Θα σας ζητηθεί να εφαρμόσουν
δύο τύποι των αναζητήσεων.

1338
01:04:57,300 --> 01:05:00,070
Το ένα είναι ένα γραμμικό αναζήτησης και
το ένα είναι ένα δυαδική αναζήτηση.

1339
01:05:00,070 --> 01:05:01,760
>> Έτσι, η γραμμική αναζήτηση είναι αρκετά εύκολο.

1340
01:05:01,760 --> 01:05:04,070
Απλά θέλετε να αναζητήσετε στοιχείου
από μια λίστα για να δείτε αν μπορείτε να το πάρετε.

1341
01:05:04,070 --> 01:05:05,444
Απλά πρέπει να επαναλαμβάνεται σε.

1342
01:05:05,444 --> 01:05:08,170
Και αν αυτό ισοδυναμεί με κάτι,
μπορείτε να το επιστρέψετε απλά, σωστά;

1343
01:05:08,170 --> 01:05:10,890
Αλλά αυτό που είμαστε πιο
ενδιαφέρονται να μιλάμε για

1344
01:05:10,890 --> 01:05:14,550
είναι δυαδική αναζήτηση, δεξιά, η οποία είναι η
διαίρει και βασίλευε μηχανισμό ο οποίος

1345
01:05:14,550 --> 01:05:18,190
Ο David έκανε επίδειξη στη διάλεξη.

1346
01:05:18,190 --> 01:05:20,810
>> Θυμηθείτε το παράδειγμα τηλεφωνικό κατάλογο
ότι κρατά ανατροφή,

1347
01:05:20,810 --> 01:05:23,960
αυτός που έχει το είδος της πάλευε
ένα κομμάτι σε αυτό το παρελθόν έτος,

1348
01:05:23,960 --> 01:05:27,530
όπου μπορείτε να διαιρέσετε το πρόβλημα στη μέση,
κατά το ήμισυ, κατά το ήμισυ, ξανά και ξανά,

1349
01:05:27,530 --> 01:05:30,730
μέχρι να βρείτε αυτό που ψάχνετε;

1350
01:05:30,730 --> 01:05:33,727
Και έχετε το
εκτέλεσης του και αυτό.

1351
01:05:33,727 --> 01:05:35,810
Και μπορείτε να δείτε, είναι
σημαντικά πιο αποτελεσματική

1352
01:05:35,810 --> 01:05:39,080
από κάθε άλλο είδος της αναζήτησης.

1353
01:05:39,080 --> 01:05:41,880
>> Έτσι ο τρόπος που θα πάει για
εφαρμογή μιας δυαδικής αναζήτησης

1354
01:05:41,880 --> 01:05:46,510
είναι, αν είχαμε μια σειρά,
0 δείκτης να 6, επτά στοιχεία,

1355
01:05:46,510 --> 01:05:49,790
μπορούμε να δούμε στη μέση, right--
Συγγνώμη, αν η ερώτησή μας first--

1356
01:05:49,790 --> 01:05:53,840
αν θέλουμε να θέσουμε το ερώτημα του, το κάνει
η συστοιχία περιλαμβάνει το στοιχείο του 7,

1357
01:05:53,840 --> 01:05:56,840
προφανώς, όντας ανθρώπους, και έχουν
όπως μια μικρή συστοιχία, είναι εύκολο για μας

1358
01:05:56,840 --> 01:05:58,210
να πω ναι.

1359
01:05:58,210 --> 01:06:05,750
Αλλά ο τρόπος για να εφαρμόσει ένα δυαδικό
Η αναζήτηση θα ήταν να δούμε στη μέση.

1360
01:06:05,750 --> 01:06:08,020
>> Γνωρίζουμε ότι ο δείκτης είναι 3
η μέση, γιατί εμείς

1361
01:06:08,020 --> 01:06:09,270
Γνωρίζω ότι υπάρχουν επτά στοιχεία.

1362
01:06:09,270 --> 01:06:10,670
Ποιες 7 διαιρείται δια 2;

1363
01:06:10,670 --> 01:06:12,850
Μπορείτε να κόβεις ότι επιπλέον 1.

1364
01:06:12,850 --> 01:06:14,850
Έχετε 3 στη μέση.

1365
01:06:14,850 --> 01:06:17,590
Έτσι, είναι σειρά 3 ισούται με το 7;

1366
01:06:17,590 --> 01:06:18,900
Δεν ειναι σωστο?

1367
01:06:18,900 --> 01:06:21,050
Αλλά μπορούμε να κάνουμε ένα ζευγάρι των ελέγχων.

1368
01:06:21,050 --> 01:06:25,380
Είναι συστοιχία 3 λιγότερο από 7 ή
Είναι σειρά από 3 μεγαλύτερο από 7?

1369
01:06:25,380 --> 01:06:27,240
>> Και ξέρουμε ότι είναι λιγότερο από το 7.

1370
01:06:27,240 --> 01:06:30,259
Γνωρίζουμε, λοιπόν, ότι, ω, θα πρέπει να
δεν είναι στο αριστερό μισό.

1371
01:06:30,259 --> 01:06:32,300
Γνωρίζουμε ότι πρέπει να είναι
στο δεξιό μισό, σωστά;

1372
01:06:32,300 --> 01:06:34,662
Οπότε μπορούμε απλά να κόψουν το ήμισυ του πίνακα.

1373
01:06:34,662 --> 01:06:36,370
Δεν χρειάζεται καν να
κοιτάξουμε πια.

1374
01:06:36,370 --> 01:06:38,711
Επειδή γνωρίζουμε ότι
εξάμηνο του problem-- μας

1375
01:06:38,711 --> 01:06:41,210
γνωρίζουμε ότι η απάντηση είναι
το δεξί μισό του προβλήματός μας.

1376
01:06:41,210 --> 01:06:42,580
Γι 'αυτό και μόλις δούμε ότι τώρα.

1377
01:06:42,580 --> 01:06:44,860
>> Έτσι τώρα κοιτάμε το
μέσα του ό, τι έχει απομείνει.

1378
01:06:44,860 --> 01:06:46,880
Ότι ο δείκτης 5.

1379
01:06:46,880 --> 01:06:50,200
Εμείς κάνουμε πάλι το ίδιο επιταγή
και βλέπουμε ότι είναι μικρότερα.

1380
01:06:50,200 --> 01:06:52,050
Έτσι, βλέπουμε στα αριστερά του ότι.

1381
01:06:52,050 --> 01:06:53,430
Και τότε θα δούμε ότι η επιταγή.

1382
01:06:53,430 --> 01:06:57,600
Είναι η τιμή σε σειρά
Δείκτης 4 ίσο με 7;

1383
01:06:57,600 --> 01:06:58,260
Είναι.

1384
01:06:58,260 --> 01:07:03,580
Έτσι, μπορούμε να επιστρέψουμε αλήθεια, επειδή
βρήκαμε την τιμή στην λίστα μας.

1385
01:07:03,580 --> 01:07:06,738
Μήπως ο τρόπος που πέρασε
που έχουν νόημα για όλους;

1386
01:07:06,738 --> 01:07:08,760
ΕΝΤΆΞΕΙ.

1387
01:07:08,760 --> 01:07:11,670
Θα σας δώσω τα παιδιά ίσως, όπως,
τρία, τέσσερα λεπτά για να καταλάβω

1388
01:07:11,670 --> 01:07:13,270
πώς να pseudocode αυτό.

1389
01:07:13,270 --> 01:07:18,070
>> Φανταστείτε λοιπόν Σου ζήτησα να γράψει ένα
λειτουργία που ονομάζεται αναζήτησης () που επέστρεψε

1390
01:07:18,070 --> 01:07:20,640
μια τιμή, μια τιμή Boolean,
αυτό ήταν αλήθεια ή false-- όπως,

1391
01:07:20,640 --> 01:07:22,970
αλήθεια αν βρεθεί η
τιμή, ψευδή αν δεν το έκανε.

1392
01:07:22,970 --> 01:07:25,230
Και τότε θα ήταν
πέρασε στην αξία σας

1393
01:07:25,230 --> 01:07:28,410
έψαχναν σε αξίες, οι οποίες
είναι η array-- OH, εγώ σίγουρα θέσει

1394
01:07:28,410 --> 01:07:29,410
ότι σε λάθος μέρος.

1395
01:07:29,410 --> 01:07:29,580
ΕΝΤΆΞΕΙ.

1396
01:07:29,580 --> 01:07:31,829
Anyways, ότι θα πρέπει να έχουν
ήταν στα δεξιά της αξίες.

1397
01:07:31,829 --> 01:07:36,280
Και τότε int n είναι ο αριθμός
των στοιχείων του εν λόγω πίνακα.

1398
01:07:36,280 --> 01:07:39,430
Πώς θα πάτε για την προσπάθεια
να pseudocode αυτό το πρόβλημα μέσα;

1399
01:07:39,430 --> 01:07:41,630
Θα σας δώσω παιδιά, όπως
τρία λεπτά για να το κάνουμε αυτό.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Όχι, νομίζω ότι υπάρχει only--
Ναι, υπάρχει ένα δικαίωμα εδώ.

1402
01:08:02,595 --> 01:08:03,261
Κοινό: Μπορώ;

1403
01:08:03,261 --> 01:08:04,388
ANDI PENG: Ναι, έχεις.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Είναι αυτό εργασίας;

1406
01:08:11,050 --> 01:08:12,290
ΟΚ κομπλε.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> ΕΝΤΆΞΕΙ.

1409
01:10:44,720 --> 01:10:47,630
Όλα τα παιδιά σωστά, είμαστε
πρόκειται να χαλιναγωγήσει.

1410
01:10:47,630 --> 01:10:49,730
ΕΝΤΆΞΕΙ.

1411
01:10:49,730 --> 01:10:54,020
Έτσι υποθέσουμε ότι έχουμε αυτό το υπέροχο
λίγο συστοιχία με τιμές n σε αυτό.

1412
01:10:54,020 --> 01:10:55,170
Δεν είχα τη χάραξη των γραμμών.

1413
01:10:55,170 --> 01:10:58,649
Αλλά πώς θα πάει για
προσπαθώντας να γράψω αυτό;

1414
01:10:58,649 --> 01:11:00,440
Υπάρχει κάποιος που θέλει να
να μου δώσει την πρώτη γραμμή;

1415
01:11:00,440 --> 01:11:02,814
Αν θέλετε να μου δώσετε το
πρώτη γραμμή αυτού του ψευδοκώδικα.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> Κοινό: [δεν ακούγεται]

1418
01:11:08,430 --> 01:11:10,138
Κοινό: Θα θέλατε
να επαναλάβει through--

1419
01:11:10,138 --> 01:11:11,094
Κοινό: Ακριβώς ένα άλλο για βρόχο;

1420
01:11:11,094 --> 01:11:11,760
Κοινό: --για.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI PENG: Έτσι, αυτό και μόνο είναι λίγο δύσκολο.

1423
01:11:17,780 --> 01:11:23,130
Σκεφτείτε about-- θέλετε
να συνεχίσει να τρέχει αυτό το βρόχο

1424
01:11:23,130 --> 01:11:27,950
ξανά και ξανά μέχρι πότε;

1425
01:11:27,950 --> 01:11:30,819
>> Κοινό: Μέχρι την [δεν ακούγεται]
τιμή είναι ίση με αυτή την τιμή.

1426
01:11:30,819 --> 01:11:31,610
ANDI PENG: Ακριβώς.

1427
01:11:31,610 --> 01:11:33,900
Έτσι μπορείτε πραγματικά ακριβώς write--
μπορούμε να απλοποιήσει ακόμη περισσότερο.

1428
01:11:33,900 --> 01:11:35,630
Μπορούμε να κάνουμε μόνο ένα βρόχο, ενώ, σωστά;

1429
01:11:35,630 --> 01:11:39,380
Έτσι, μπορείτε να έχετε μόνο loop--
ξέρουμε ότι είναι μια στιγμή.

1430
01:11:39,380 --> 01:11:42,850
Αλλά για τώρα, θα πάω
να πει "θηλιά" - μέσα από αυτό;

1431
01:11:42,850 --> 01:11:46,640
Loop until-- ό, τι είναι
που λήγει την κατάσταση μας;

1432
01:11:46,640 --> 01:11:47,510
Νομίζω ότι άκουσα.

1433
01:11:47,510 --> 01:11:48,530
Άκουσα κάποιον να το πω.

1434
01:11:48,530 --> 01:11:51,255
>> Κοινό: Οι τιμές ισούται μέση.

1435
01:11:51,255 --> 01:11:52,255
ANDI PENG: το πω και πάλι.

1436
01:11:52,255 --> 01:11:54,470
Κοινό: Ή, έως ότου η
αξία ψάχνετε

1437
01:11:54,470 --> 01:11:58,470
είναι ίσο με την μέση τιμή.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI PENG: Τι θα συμβεί αν δεν είναι εκεί;

1439
01:12:00,280 --> 01:12:03,113
Τι θα συμβεί αν η αξία ψάχνετε
για να μην είναι στην πραγματικότητα σε αυτήν την σειρά;

1440
01:12:03,113 --> 01:12:05,890
Κοινό: Μπορείτε να επιστρέψετε 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI PENG: Αλλά αυτό που θέλουμε να
βρόχο μέχρι αν έχουμε μια κατάσταση;

1442
01:12:08,850 --> 01:12:09,350
Ναι.

1443
01:12:09,350 --> 01:12:11,239
>> Κοινό: Μέχρι υπάρχει μόνο μία τιμή;

1444
01:12:11,239 --> 01:12:13,530
ANDI PENG: Μπορείτε βρόχο
until-- ώστε να γνωρίζετε ότι είστε

1445
01:12:13,530 --> 01:12:15,714
πρόκειται να έχουν μια μέγιστη τιμή, σωστά;

1446
01:12:15,714 --> 01:12:18,130
Και ξέρετε ότι θα πάμε
να έχουν μια ελάχιστη τιμή, σωστά;

1447
01:12:18,130 --> 01:12:20,379
Επειδή, επίσης, ότι αυτό είναι κάτι
Ξέχασα να πω πριν,

1448
01:12:20,379 --> 01:12:22,640
ότι κάτι που είναι
κρίσιμη για την δυαδική αναζήτηση

1449
01:12:22,640 --> 01:12:24,182
είναι ότι η σειρά σας είναι ήδη ταξινομημένο.

1450
01:12:24,182 --> 01:12:26,973
Επειδή δεν υπάρχει τρόπος να γίνει
Αυτό κι αν είναι απλά τυχαίες τιμές.

1451
01:12:26,973 --> 01:12:29,190
Δεν ξέρω αν κάποιος είναι
μεγαλύτερο από το άλλο, έτσι δεν είναι;

1452
01:12:29,190 --> 01:12:32,720
>> Έτσι ξέρετε ότι max σας και
λεπτά σας εδώ, έτσι δεν είναι;

1453
01:12:32,720 --> 01:12:35,590
Αν πρόκειται να την προσαρμογή
max σας σε λεπτά και τα mid--

1454
01:12:35,590 --> 01:12:38,470
ας υποθέσουμε σας
μέσα τιμή είναι σωστή here--

1455
01:12:38,470 --> 01:12:43,910
θα πάμε να βασικά
βρόχο μέχρι το ελάχιστο ποσό σας είναι

1456
01:12:43,910 --> 01:12:47,510
περίπου το ίδιο με το μέγιστο σας, δεξιά, ή
αν max σας δεν είναι το ίδιο με το λεπτό σου.

1457
01:12:47,510 --> 01:12:48,040
Σωστά;

1458
01:12:48,040 --> 01:12:51,340
Γιατί όταν συμβεί αυτό, ξέρετε ότι
έχετε χτυπήσει τελικά την ίδια αξία.

1459
01:12:51,340 --> 01:12:59,135
Έτσι θέλετε να βρόχο μέχρι λεπτά σας
είναι μικρότερη ή ίση to-- ουπς,

1460
01:12:59,135 --> 01:13:01,510
όχι λιγότερο από ή ίσο με,
ο άλλος τρόπος around-- max είναι.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Μήπως αυτό έχει νόημα;

1463
01:13:16,160 --> 01:13:18,810
Πήρα μερικές προσπάθειες για να πάρει αυτό το δικαίωμα.

1464
01:13:18,810 --> 01:13:21,869
Αλλά βρόχο μέχρι Μέγιστη τιμή σας
είναι ουσιαστικά σχεδόν λιγότερο

1465
01:13:21,869 --> 01:13:23,410
από ή ίσο με το ελάχιστο σου, σωστά;

1466
01:13:23,410 --> 01:13:25,201
Αυτό είναι όταν ξέρεις
ότι έχετε συγκλίνει.

1467
01:13:25,201 --> 01:13:29,290
Κοινό: Πότε θα το μέγιστο
αξία είναι μικρότερη από την ελάχιστη;

1468
01:13:29,290 --> 01:13:31,040
ANDI PENG: Εάν έχετε κρατήσει
προσαρμόζοντάς τον, η οποία

1469
01:13:31,040 --> 01:13:32,380
είναι αυτό που πρόκειται
πρέπει να κάνουμε σε αυτό.

1470
01:13:32,380 --> 01:13:33,460
Βγάζει νόημα αυτό?

1471
01:13:33,460 --> 01:13:35,750
Ελάχιστη και μέγιστη είναι μόνο
ακέραιοι που είναι πιθανόν

1472
01:13:35,750 --> 01:13:39,260
πρόκειται να θέλουν να δημιουργήσουν για να κρατήσει
παρακολουθείτε όπου ψάχνουμε.

1473
01:13:39,260 --> 01:13:41,790
Επειδή υπάρχει η συστοιχία
ανεξάρτητα από το τι κάνουμε.

1474
01:13:41,790 --> 01:13:45,030
Όπως, δεν είμαστε πραγματικά σωματικά
κόβοντας τη σειρά, έτσι δεν είναι;

1475
01:13:45,030 --> 01:13:47,261
Είμαστε ακριβώς προσαρμογή
όπου ψάχνουμε.

1476
01:13:47,261 --> 01:13:48,136
Βγάζει νόημα αυτό?

1477
01:13:48,136 --> 01:13:48,472
>> Κοινό: Ναι.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI PENG: OK.

1479
01:13:49,110 --> 01:13:57,090
Έτσι, αν αυτή είναι η προϋπόθεση για την θηλιά μας,
Τι θέλουμε μέσα από αυτό το βρόχο;

1480
01:13:57,090 --> 01:13:58,700
Τι πρόκειται να θέλουν να κάνουν;

1481
01:13:58,700 --> 01:14:02,390
Έτσι τώρα, έχουμε
ένα μέγιστο και ένα λεπτό, δεξιά,

1482
01:14:02,390 --> 01:14:04,962
πιθανότατα δημιουργήθηκε εδώ κάπου.

1483
01:14:04,962 --> 01:14:07,170
Εμείς πάμε για να θελήσει πιθανώς
να βρούμε μια μέση, έτσι δεν είναι;

1484
01:14:07,170 --> 01:14:08,450
Πώς θα πάμε να είναι
είναι σε θέση να βρει τη μέση;

1485
01:14:08,450 --> 01:14:09,491
Ποια είναι η mathematical--

1486
01:14:09,491 --> 01:14:11,079
Κοινό: Max συν min διαιρείται δια 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI PENG: Ακριβώς.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Βγάζει νόημα αυτό?

1490
01:14:21,620 --> 01:14:25,780
Και εσείς δεν βλέπω το λόγο γιατί
Δεν έκανε ακριβώς use-- γιατί το κάναμε αυτό

1491
01:14:25,780 --> 01:14:27,850
αντί να κάνει ακριβώς n διαιρείται με 2;

1492
01:14:27,850 --> 01:14:30,310
Είναι επειδή η είναι η αξία
ότι πρόκειται να παραμείνει το ίδιο.

1493
01:14:30,310 --> 01:14:30,979
Σωστά;

1494
01:14:30,979 --> 01:14:34,020
Αλλά όπως έχουμε προσαρμόσει τις ελάχιστες μας και
μέγιστες τιμές, πρόκειται να αλλάξει.

1495
01:14:34,020 --> 01:14:36,040
Και ως αποτέλεσμα, το μεσαίο μας
πρόκειται να αλλάξει πάρα πολύ.

1496
01:14:36,040 --> 01:14:37,873
Έτσι, γι 'αυτό θέλουμε
για να κάνουμε αυτό το δικαίωμα εδώ.

1497
01:14:37,873 --> 01:14:38,510
ΕΝΤΆΞΕΙ.

1498
01:14:38,510 --> 01:14:41,600
>> Και τότε, τώρα που
έχουμε βρει our-- ναι.

1499
01:14:41,600 --> 01:14:44,270
>> Κοινό: Απλά μια γρήγορη question--
όταν λέτε min και max,

1500
01:14:44,270 --> 01:14:46,410
μήπως έχουμε υποθέσει ότι
είναι ήδη ταξινομημένο;

1501
01:14:46,410 --> 01:14:48,400
>> ANDI PENG: Ναι, αυτό είναι πραγματικά ένα
Προϋπόθεση για μια δυαδική αναζήτηση,

1502
01:14:48,400 --> 01:14:49,816
ότι θα πρέπει να ξέρετε ότι είναι ταξινομημένο.

1503
01:14:49,816 --> 01:14:53,660
Αυτός είναι ο λόγος ταξινόμησης, γράφετε στο σας
πρόβλημα που πριν δυαδική αναζήτηση σας.

1504
01:14:53,660 --> 01:14:55,910
ΕΝΤΆΞΕΙ.

1505
01:14:55,910 --> 01:14:58,876
Έτσι τώρα που ξέρουμε πού μέσο μας
είναι, τι θέλετε να κάνετε εδώ;

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> Κοινό: Θέλουμε να συγκρίνετε
ότι στο άλλο.

1508
01:15:04,319 --> 01:15:05,110
ANDI PENG: Ακριβώς.

1509
01:15:05,110 --> 01:15:12,280
Έτσι θα πάμε να συγκρίνετε
μέσα στην τιμή, έτσι δεν είναι;

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
Και τι σημαίνει αυτό πείτε
μας όταν συγκρίνουμε;

1512
01:15:18,670 --> 01:15:22,226
Τι θέλουμε να κάνουμε μετά;

1513
01:15:22,226 --> 01:15:25,389
>> Κοινό: Αν η τιμή είναι μεγαλύτερη
από τα μέσα της δεκαετίας, θέλουμε να το κόψει.

1514
01:15:25,389 --> 01:15:26,180
ANDI PENG: Ακριβώς.

1515
01:15:26,180 --> 01:15:33,940
Έτσι, αν η τιμή είναι μεγαλύτερη
από τα μέσα της δεκαετίας, είμαστε

1516
01:15:33,940 --> 01:15:36,550
Πρόκειται να θελήσετε να αλλάξετε αυτές
ελάχιστο και Maxes, σωστά;

1517
01:15:36,550 --> 01:15:38,980
Τι θέλουμε να αλλάξουμε;

1518
01:15:38,980 --> 01:15:42,145
Έτσι, αν γνωρίζουμε ότι η τιμή είναι κάπου
εδώ, τι κάνουμε εμείς για να αλλάξουμε;

1519
01:15:42,145 --> 01:15:44,758
Θέλουμε να αλλάξουμε μας
ελάχιστο να είναι μέσα, σωστά;

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
Και τότε τι άλλο, αν είναι σε αυτό το
ήμισυ, τι θέλουμε να αλλάξουμε;

1522
01:15:54,292 --> 01:15:55,306
>> Κοινό: κατ 'ανώτατο όριο σας.

1523
01:15:55,306 --> 01:15:55,972
ANDI PENG: Ναι.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
Και τότε είστε ακριβώς πρόκειται
να κρατήσει looping, σωστά;

1526
01:16:04,680 --> 01:16:08,920
Γιατί τώρα, μετά από μία επανάληψη
μέσα, έχεις ένα μέγιστο εδώ.

1527
01:16:08,920 --> 01:16:10,760
Και στη συνέχεια, μπορείτε να υπολογίσετε εκ νέου ένα μέσα.

1528
01:16:10,760 --> 01:16:11,990
Και τότε μπορείτε να συγκρίνετε.

1529
01:16:11,990 --> 01:16:14,766
Και θα πάμε να συνεχίσω
μέχρι τα λεπτά και τα Maxes

1530
01:16:14,766 --> 01:16:15,890
έχουν ουσιαστικά συγκλίνει.

1531
01:16:15,890 --> 01:16:17,890
Και αυτό είναι όταν ξέρεις ότι
έχετε χτυπήσει το τέλος της.

1532
01:16:17,890 --> 01:16:20,280
Και είτε το έχεις βρει
ή δεν έχετε σε αυτό το σημείο.

1533
01:16:20,280 --> 01:16:23,170
>> Μήπως αυτό έχει νόημα για όλους;

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
ΕΝΤΆΞΕΙ.

1536
01:16:26,770 --> 01:16:27,900
Αυτό είναι πολύ σημαντικό,
επειδή θα έχετε

1537
01:16:27,900 --> 01:16:29,760
να γράψω αυτό τον κωδικό σας απόψε.

1538
01:16:29,760 --> 01:16:32,660
Αλλά εσείς έχετε μια αρκετά καλή
αίσθηση του τι θα έπρεπε να κάνετε,

1539
01:16:32,660 --> 01:16:34,051
το οποίο είναι καλό.

1540
01:16:34,051 --> 01:16:34,550
ΕΝΤΆΞΕΙ.

1541
01:16:34,550 --> 01:16:38,840
Έτσι έχουμε περίπου επτά
λεπτά αριστερό μέρος.

1542
01:16:38,840 --> 01:16:43,170
Έτσι θα πάμε να μιλήσουμε για
αυτό το chipset που θα κάνουμε.

1543
01:16:43,170 --> 01:16:46,410
Έτσι, η PSET διαιρείται σε δύο ίσα μέρη.

1544
01:16:46,410 --> 01:16:50,230
Το πρώτο εξάμηνο περιλαμβάνει
εφαρμογή εύρεσης

1545
01:16:50,230 --> 01:16:54,210
στην οποία μπορείτε να γράψετε μια γραμμική αναζήτηση, μια
δυαδική αναζήτηση, και ένας αλγόριθμος ταξινόμησης.

1546
01:16:54,210 --> 01:16:56,690
>> Έτσι, αυτό είναι το πρώτο
φορά σε PSET όπου

1547
01:16:56,690 --> 01:17:00,050
θα δίνουμε εσείς αυτό που ονομάζεται
Κώδικα Διαχείρισης του Δικτύου, η οποία είναι ο κωδικός

1548
01:17:00,050 --> 01:17:02,740
ότι έχουμε προ-γραπτά,
αλλά μόλις έφυγε μερικά κομμάτια off

1549
01:17:02,740 --> 01:17:04,635
για να ολοκληρώσετε το γράψιμο.

1550
01:17:04,635 --> 01:17:07,510
Έτσι ρε παιδιά, όταν κοιτάς αυτό
κωδικό, μπορείτε να πάρετε πραγματικά φοβισμένη.

1551
01:17:07,510 --> 01:17:08,630
Αν θέλετε, Ααα, εγώ απλά
Δεν ξέρω τι κάνει,

1552
01:17:08,630 --> 01:17:11,670
Δεν ξέρω, όπως, φαίνεται ότι
τόσο περίπλοκη, Ααα, να χαλαρώσετε.

1553
01:17:11,670 --> 01:17:12,170
Είναι εντάξει.

1554
01:17:12,170 --> 01:17:12,930
Διαβάστε το spec.

1555
01:17:12,930 --> 01:17:16,920
Το spec θα σας εξηγήσει ακριβώς
τι κάνουν όλα αυτά τα προγράμματα.

1556
01:17:16,920 --> 01:17:20,560
>> Για παράδειγμα, generate.c είναι ένα πρόγραμμα
ότι θα έρθει με το chipset σας.

1557
01:17:20,560 --> 01:17:24,060
Δεν χρειάζεται πραγματικά να το αγγίξει, αλλά
θα πρέπει να καταλάβουν τι κάνει.

1558
01:17:24,060 --> 01:17:28,550
Και generate.c, το μόνο που κάνουν είναι είναι
είτε τη δημιουργία τυχαίων αριθμών

1559
01:17:28,550 --> 01:17:32,400
ή μπορείτε να του δώσετε ένα σπόρο, σαν ένα
προσχεδιασμένο αριθμό που παίρνει,

1560
01:17:32,400 --> 01:17:34,140
και παράγει περισσότερους αριθμούς.

1561
01:17:34,140 --> 01:17:37,170
Έτσι, υπάρχει ένας συγκεκριμένος τρόπος για να
εφαρμογή generate.c στην οποία

1562
01:17:37,170 --> 01:17:42,760
μπορείτε να κάνετε απλά μια δέσμη των αριθμών
για να μπορείτε να δοκιμάσετε άλλες μεθόδους σας.

1563
01:17:42,760 --> 01:17:45,900
>> Έτσι, αν θέλετε, για
παράδειγμα, ελέγξτε εύρημα σας,

1564
01:17:45,900 --> 01:17:48,970
που θα ήθελαν να τρέχουν generate.c,
παράγουν μια δέσμη των αριθμών,

1565
01:17:48,970 --> 01:17:50,880
και στη συνέχεια να εκτελέσετε τη λειτουργία βοηθοί σας.

1566
01:17:50,880 --> 01:17:53,930
Λειτουργία σας είναι βοηθοί όπου είστε
στην πραγματικότητα φυσικά να γράφετε κώδικα.

1567
01:17:53,930 --> 01:17:59,330
Και σκεφτείτε βοηθοί ως αρχείο βιβλιοθήκης
είστε γραπτώς ότι εύρημα καλεί.

1568
01:17:59,330 --> 01:18:02,950
Και έτσι μέσα helpers.c, θα
κάνει την αναζήτηση και τη διαλογή.

1569
01:18:02,950 --> 01:18:06,500
>> Και τότε θα πάμε σε ουσιαστικά
απλά να τους βάλω όλους μαζί.

1570
01:18:06,500 --> 01:18:10,350
Το spec θα σας πει πώς να
θέσουμε ότι στη γραμμή εντολών.

1571
01:18:10,350 --> 01:18:14,880
Και θα είστε σε θέση να εξετάσουμε αν
Δεν το είδος και την αναζήτηση εργασίας σας.

1572
01:18:14,880 --> 01:18:15,870
Cool.

1573
01:18:15,870 --> 01:18:18,720
Έχει κανείς ήδη ξεκινήσει και
αντιμετώπισαν προβλήματα ή ερωτήσεις

1574
01:18:18,720 --> 01:18:20,520
έχουν τώρα με αυτό;

1575
01:18:20,520 --> 01:18:21,020
ΕΝΤΆΞΕΙ.

1576
01:18:21,020 --> 01:18:21,476
>> Κοινό: Περιμένετε.

1577
01:18:21,476 --> 01:18:21,932
Έχω μία ερώτηση.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI PENG: Ναι.

1579
01:18:22,844 --> 01:18:28,390
>> Κοινό: Έτσι άρχισα να κάνω
η γραμμική αναζήτηση σε helpers.c

1580
01:18:28,390 --> 01:18:29,670
και δεν ήταν πραγματικά λειτουργεί.

1581
01:18:29,670 --> 01:18:34,590
Στη συνέχεια, όμως αργότερα, έμαθα απλά
πρέπει να το διαγράψετε και να κάνει δυαδική αναζήτηση.

1582
01:18:34,590 --> 01:18:36,991
Έτσι, έχει σημασία αν δεν λειτουργεί;

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI PENG: Σύντομη απάντηση είναι όχι.

1585
01:18:41,510 --> 01:18:42,642
Αλλά δεδομένου ότι είμαστε not--

1586
01:18:42,642 --> 01:18:44,350
Κοινό: Αλλά κανείς δεν είναι
στην πραγματικότητα τον έλεγχο.

1587
01:18:44,350 --> 01:18:46,058
ANDI PENG: Είμαστε ποτέ
Θα δείτε ότι.

1588
01:18:46,058 --> 01:18:49,590
Αλλά ίσως θέλετε να κάνετε
βέβαιος αναζήτησή σας λειτουργεί.

1589
01:18:49,590 --> 01:18:51,700
Διότι, αν γραμμική σας
Η αναζήτηση δεν λειτουργεί,

1590
01:18:51,700 --> 01:18:54,410
τότε οι πιθανότητες είναι δυαδική σας
Η αναζήτηση δεν πρόκειται να λειτουργεί τόσο καλά.

1591
01:18:54,410 --> 01:18:56,646
Επειδή έχετε παρόμοια
λογική και στις δύο από αυτές.

1592
01:18:56,646 --> 01:18:58,020
Και όχι, δεν έχει τόση σημασία.

1593
01:18:58,020 --> 01:19:01,300
Έτσι, οι μόνοι που θα στραφούν
σε είδος και είναι δυαδική αναζήτηση.

1594
01:19:01,300 --> 01:19:02,490
Ναι.

1595
01:19:02,490 --> 01:19:06,610
>> Και, επίσης, πολλά παιδιά ήταν
προσπαθεί να συγκεντρώσει helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Δεν είστε πραγματικά επιτρέπονται
για να το κάνουμε αυτό, γιατί helpers.c

1597
01:19:09,550 --> 01:19:11,200
δεν έχει μια κύρια λειτουργία.

1598
01:19:11,200 --> 01:19:13,550
Και έτσι θα πρέπει μόνο
είναι στην πραγματικότητα κατάρτιση

1599
01:19:13,550 --> 01:19:18,670
να δημιουργήσει και να βρει, επειδή βρίσκουν κλήσεις
helpers.c και οι λειτουργίες μέσα σε αυτό.

1600
01:19:18,670 --> 01:19:20,790
Έτσι ώστε να κάνει debugging
ένας πόνος στην άκρη.

1601
01:19:20,790 --> 01:19:22,422
Αλλά αυτό είναι ό, τι πρέπει να κάνουμε.

1602
01:19:22,422 --> 01:19:23,880
Κοινό: Απλά κάνει όλα, έτσι δεν είναι;

1603
01:19:23,880 --> 01:19:27,290
ANDI PENG: Μπορείτε μόνο
κάνει όλους καθώς, ναι.

1604
01:19:27,290 --> 01:19:28,060
ΕΝΤΆΞΕΙ.

1605
01:19:28,060 --> 01:19:32,570
Έτσι ώστε να είναι σε σχέση με το τι
η PSET ζητά από όλους σας να κάνετε.

1606
01:19:32,570 --> 01:19:35,160
Εάν έχετε οποιεσδήποτε ερωτήσεις, αισθάνονται
ελεύθερη να με ρωτήσει αφού το τμήμα.

1607
01:19:35,160 --> 01:19:37,580
Θα είμαι εδώ για, όπως, 20 λεπτά.

1608
01:19:37,580 --> 01:19:40,500
>> Και ναι, οι PSET του
Πραγματικά δεν είναι τόσο άσχημα.

1609
01:19:40,500 --> 01:19:41,680
Εσείς θα πρέπει να είναι εντάξει.

1610
01:19:41,680 --> 01:19:43,250
Αυτά, απλώς ακολουθήστε τις κατευθυντήριες γραμμές.

1611
01:19:43,250 --> 01:19:47,840
Είδος έχουν μια αίσθηση της, λογικά, τι
θα πρέπει να συμβαίνει και θα είστε μια χαρά.

1612
01:19:47,840 --> 01:19:48,690
Να μην είστε πάρα πολύ φοβισμένοι.

1613
01:19:48,690 --> 01:19:50,220
Υπάρχει μια πολύ κώδικα
ήδη γραμμένο εκεί.

1614
01:19:50,220 --> 01:19:53,011
Μην να είναι πάρα πολύ φοβισμένος αν δεν το κάνετε
καταλαβαίνουν τι όλα αυτά μέσα.

1615
01:19:53,011 --> 01:19:54,749
Αν είναι πολλά, είναι εντελώς καλά.

1616
01:19:54,749 --> 01:19:55,790
Και να έρθουν σε ώρες γραφείου.

1617
01:19:55,790 --> 01:19:57,520
Θα σας βοηθήσουμε να ρίξετε μια ματιά.

1618
01:19:57,520 --> 01:20:00,810
>> Κοινό: Με το επιπλέον
λειτουργίες, δεν βλέπουμε εκείνους επάνω;

1619
01:20:00,810 --> 01:20:03,417
>> ANDI PENG: Ναι, αυτά είναι στον κώδικα.

1620
01:20:03,417 --> 01:20:05,750
Στο παιχνίδι του 15, ένα δεύτερο του
είναι ήδη γραμμένο για εσάς.

1621
01:20:05,750 --> 01:20:09,310
Έτσι, οι λειτουργίες αυτές είναι
ήδη στον κώδικα.

1622
01:20:09,310 --> 01:20:12,020
Ναι.

1623
01:20:12,020 --> 01:20:12,520
Εντάξει.

1624
01:20:12,520 --> 01:20:14,000
Λοιπόν, καλή τύχη.

1625
01:20:14,000 --> 01:20:15,180
Είναι ένα αηδιαστικό ημέρα.

1626
01:20:15,180 --> 01:20:19,370
Έτσι, ελπίζουμε ότι εσείς δεν αισθάνεστε πάρα πολύ
άσχημα για την διαμονή τους στο εσωτερικό και κωδικοποίησης.

1627
01:20:19,370 --> 01:20:22,133